标签归档:主席树

[zoj4053][icpc 2018 Qingdao Online]Couleur

Link

Solution

假设将区间$[l,r]$中间的$p$ ban掉,并且知道$[l,r]$的逆序堆数,容易计算出$[l,p-1]$和$[p+1,r]$之间,以及他们分别和$p$产生的逆序数。
用启发式的思想,每次将这两个区间中小的那个遍历,在另一个区间的主席树中查询,最终复杂度为$O(n\log^2n)$

Tips

赛场上没有过这道题,是因为偷懒直接把问题一般化,得到$O(n\sqrt {n\log n})$的做法,最终自闭。

Code

const int XN=1e5+11;

struct SegTree {
    struct Node {
        Node *son[2];
        long long cnt;

        Node():cnt(0) {
            son[0]=son[1]=null;
        }

        Node(void*):cnt(0) {
            son[0]=son[1]=this;
        }

        void *operator new(size_t flag) {
            static Node *pool=(Node*)malloc(XN*20*sizeof(Node)),*mem=pool++;
            return flag?mem++:mem=pool;
        }

        void Up() {
            cnt=son[0]->cnt+son[1]->cnt;
        }

    }*root[XN];
    int n,L,R;
    static Node *null;

    SegTree(int L,int R):n(0),L(L),R(R) {
        root[0]=null;
    }

    void Append(int v) {
        ++n;
        Modify(root[n]=root[n-1],L,R,v);
    }

    long long Query(int lbd,int rbd,int l,int r) {
        return lbd<=rbd && l<=r?Query(root[lbd-1],root[rbd],L,R,l,r):0;
    }

    static void Modify(Node *&pos,int L,int R,int goal) {
        pos=new Node(*pos);
        if(L==R)
            pos->cnt++;
        else {
            int M=(L+R)/2;
            if(goal<=M)
                Modify(pos->son[0],L,M,goal);
            else
                Modify(pos->son[1],M+1,R,goal);
            pos->Up();
        }
    }

    static long long Query(Node *pl,Node *pr,int L,int R,int l,int r) {
        if(L==l && R==r)
            return pr->cnt-pl->cnt;
        else {
            int M=(L+R)/2;
            if(r<=M)
                return Query(pl->son[0],pr->son[0],L,M,l,r);
            else if(M+1<=l)
                return Query(pl->son[1],pr->son[1],M+1,R,l,r);
            else
                return Query(pl->son[0],pr->son[0],L,M,l,M)
                      +Query(pl->son[1],pr->son[1],M+1,R,M+1,r);
        }
    }
}seg(-1,-1);

SegTree::Node *SegTree::null=new SegTree::Node((void*)0);

int a[XN];

void Work() {
    SegTree::Node::operator new(0);
    int n;fin>>n;
    new(&seg) SegTree(1,n);
    long long last=0;
    std::set<int> unav;
    std::multiset<long long> S;
    for(int i=1;i<=n;++i) {
        fin>>a[i];
        last+=seg.Query(1,i-1,a[i]+1,n);
        seg.Append(a[i]);
    }
    unav.insert(0);
    unav.insert(n+1);
    static std::multiset<long long>::iterator its[XN];
    its[1]=S.insert(last);
    for(int lop=1;lop<=n;++lop) {
        fout<<last<<(lop==n?'\n':' ');
        long long p;fin>>p;p^=last;
        std::set<int>::iterator pt=unav.upper_bound(p);
        int r=(*pt)-1,l=(*--pt)+1;
        unav.insert(p);
        long long tot=*its[l];
        S.erase(its[l]);
        tot-=seg.Query(l,p-1,a[p]+1,n)+seg.Query(p+1,r,1,a[p]-1);
        if(p-l>r-p) {
            long long ic=0,lc=0;
            for(int i=p+1;i<=r;++i) {
                lc+=seg.Query(l,p-1,a[i]+1,n);
                ic+=seg.Query(p+1,i-1,a[i]+1,n);
            }
            its[l]=S.insert(tot-lc-ic);
            its[p+1]=S.insert(ic);
        } else {
            long long ic=0,rc=0;
            for(int i=l;i<=p-1;++i) {
                rc+=seg.Query(p+1,r,1,a[i]-1);
                ic+=seg.Query(l,i-1,a[i]+1,n);
            }
            its[l]=S.insert(ic);
            its[p+1]=S.insert(tot-rc-ic);
        }
        last=*S.rbegin();
    }
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}