BZOJ3295 [Cqoi2011]动态逆序对 树状数组套线段树

yts1999 posted @ 2015年8月05日 20:49 in 树套树 with tags bzoj 树套树 树状数组 线段树 , 521 阅读

又因为访问空指针下的元素RE了。。。

/**************************************************************
    Problem: 3295
    User: yts1999
    Language: C++
    Result: Accepted
    Time:3768 ms
    Memory:75556 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
 
struct Treenode {
    Treenode *lc,*rc;
    int sum;
    Treenode() {
        lc = rc = NULL;
        sum = 0;
    }
};
 
Treenode *a[30],*b[30];
int tota,totb,n;
int num[100010],pl[100010],a1[100010],a2[100010],t[100010];
Treenode *root[100010];
 
int lowbit(int x) {
    return x & -x;
}
 
int getans(int x) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        ans += t[i];
    return ans;
}
 
void modify(Treenode *&k,int l,int r,int x) {
    if (k == NULL)
        k = new Treenode;
    k->sum++;
    if (l == r)
        return;
    int mid = (l + r) / 2;
    if (x <= mid)
        modify(k->lc,l,mid,x);
    else
        modify(k->rc,mid + 1,r,x);
}
 
int querymore(int x,int y,int num) {
    tota = totb = 0;
    int tmp = 0;
    x--;
    for (int i = x; i > 0; i -= lowbit(i))
        a[++tota] = root[i];
    for (int i = y; i > 0; i -= lowbit(i))
        b[++totb] = root[i];
    for (int l = 1,r = n; l != r;) {
        int mid = (l + r) / 2;
        if (num <= mid) {
            for (int i = 1; i <= tota; i++)
                if (a[i] != NULL && a[i]->rc != NULL)
                    tmp -= a[i]->rc->sum;
            for (int i = 1; i <= totb; i++)
                if (b[i] != NULL && b[i]->rc != NULL)
                    tmp += b[i]->rc->sum;
            for (int i = 1; i <= tota; i++)
                if (a[i] != NULL)
                    a[i] = a[i]->lc;
            for (int i = 1; i <= totb; i++)
                if (b[i] != NULL)
                    b[i] = b[i]->lc;
            r = mid;
        }
        else {
            for (int i = 1; i <= tota; i++)
                if (a[i] != NULL)
                    a[i] = a[i]->rc;
            for (int i = 1; i <= totb; i++)
                if (b[i] != NULL)
                    b[i] = b[i]->rc;
            l = mid + 1;
        }
    }
    return tmp;
}
 
int queryless(int x,int y,int num) {
    tota = totb = 0;
    int tmp = 0;
    x--;
    for (int i = x; i > 0; i -= lowbit(i))
        a[++tota] = root[i];
    for (int i = y; i > 0; i -= lowbit(i))
        b[++totb] = root[i];
    for (int l = 1,r = n; l != r;) {
        int mid = (l + r) / 2;
        if (num > mid) {
            for (int i = 1; i <= tota; i++)
                if (a[i] != NULL && a[i]->lc != NULL)
                    tmp -= a[i]->lc->sum;
            for (int i = 1; i <= totb; i++)
                if (b[i] != NULL && b[i]->lc != NULL)
                    tmp += b[i]->lc->sum;
            for (int i = 1; i <= tota; i++)
                if (a[i] != NULL)
                    a[i] = a[i]->rc;
            for (int i = 1; i <= totb; i++)
                if (b[i] != NULL)
                    b[i] = b[i]->rc;
            l = mid + 1;
        }
        else {
            for (int i = 1; i <= tota; i++)
                if (a[i] != NULL)
                    a[i] = a[i]->lc;
            for (int i = 1; i <= totb; i++)
                if (b[i] != NULL)
                    b[i] = b[i]->lc;
            r = mid;
        }
    }
    return tmp;
}
 
int main() {
    int m;
    scanf("%d%d",&n,&m);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d",&num[i]);
        pl[num[i]] = i;
        a1[i] = getans(n) - getans(num[i]);
        ans += a1[i];
        for (int j = num[i]; j <= n; j += lowbit(j))
            t[j]++;
    }
    memset(t,0,sizeof(t));
    for (int i = n; i >= 1; i--) {
        a2[i] = getans(num[i] - 1);
        for (int j = num[i]; j <= n; j += lowbit(j))
            t[j]++;
    }
    for (int i = 1; i <= m; i++) {
        printf("%lld\n",ans);
        int x;
        scanf("%d",&x);
        x = pl[x];
        ans -= (a1[x] + a2[x] - querymore(1,x - 1,num[x]) - queryless(x + 1,n,num[x]));
        for (int j = x; j <= n; j += lowbit(j))
            modify(root[j],1,n,num[x]);
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter