线段树_逆序数

题目链接

• 分析：
  对于输入序列ipt[]，每次先查询[ipt[i] + 1, max]区间和（在输入点之前比它大的数的个数）加到answer里边；然后对ipt[i]处加一。
  这个题是求循环序列中逆序数最小的，那么当树中有n个数的时候，在需要插入数时就把第一个数删去。下边是自己的写法，比较麻烦
• 总结：
  本身不难，但是这个题目在处理逆序数时候是循环的，所以会涉及到删除操作（减一）

const int MAXN = 5100;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

int tree[MAXN << 2];

void pushUP(int l, int r, int rt)
{
    tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]);
}

void build(int l, int r, int rt)
{
    if (l == r)
    {
        tree[rt] = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushUP(l, r, rt);
}

void update(int p, int add, int l, int r, int rt)
{
    if (l == r)
    {
        tree[rt] += add;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m)
        update(p, add, lson);
    else
        update(p, add, rson);
    pushUP(l, r, rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return tree[rt];
    int ret = 0, m = (l + r) >> 1;
    if (L <= m)
        ret += query(L, R, lson);
    if (R > m)
        ret += query(L, R, rson);
    return ret;
}

int ipt[MAXN];

int main()
{
//    freopen("in.txt", "r", stdin);
    int num;
    while (~RI(num))
    {
        build(0, num, 1);
        REP(i, num)
        {
            RI(ipt[i]);
        }

        int t = 0, ans = INF, l = 0, r = -1;
        REP(i, 2 * num - 1)
        {
            if (r - l + 1 == num)
            {
                ans = min(ans, t);
                if (ipt[l] >= 1)
                    t -= query(0, ipt[l] - 1, 0, num - 1, 1);
                update(ipt[l], -1, 0, num - 1, 1);
                l++;
            }
            if (ipt[i % num] <= num - 1)
                t += query(ipt[i % num], num - 1, 0, num - 1, 1);
            update(ipt[i % num], 1, 0, num - 1, 1);
            r++;
        }

        WI(ans);
    }
    return 0;
}

实际上考虑一下当num个数都插入到线段树中时，这时候删除的数都处于序列的一段。那么就没必要每次都在进行线段树操作了，知道端点的值而且树种的值是0-num的树，那么对于0到ipt[i] - 1之间的数都是减少的逆序数；对于ipt[i] + 1到num - 1的数每一个都加一。

const int MAXN = 5100;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

int tree[MAXN << 2];

void pushUP(int l, int r, int rt)
{
    tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]);
}

void build(int l, int r, int rt)
{
    if (l == r)
    {
        tree[rt] = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushUP(l, r, rt);
}

void update(int p, int add, int l, int r, int rt)
{
    if (l == r)
    {
        tree[rt] += add;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m)
        update(p, add, lson);
    else
        update(p, add, rson);
    pushUP(l, r, rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return tree[rt];
    int ret = 0, m = (l + r) >> 1;
    if (L <= m)
        ret += query(L, R, lson);
    if (R > m)
        ret += query(L, R, rson);
    return ret;
}

int ipt[MAXN];

int main()
{
//    freopen("in.txt", "r", stdin);
    int num;
    while (~RI(num))
    {
        build(0, num, 1);
        REP(i, num)
        {
            RI(ipt[i]);
        }

        int ans = 0, l = 0, r = -1, Min = INF;
        REP(i, num)
        {
            if (ipt[i] <= num - 1)
                ans += query(ipt[i], num - 1, 0, num - 1, 1);
            update(ipt[i], 1, 0, num - 1, 1);
        }
        Min = min(Min, ans);
        REP(i, num - 1)
        {
            ans += -2 * ipt[i] + num - 1;
            Min = min(Min, ans);
        }

        WI(Min);
    }
    return 0;
}

线段树_逆序数,布布扣,bubuko.com

线段树_逆序数

原文：http://blog.csdn.net/wty__/article/details/21187001