跳转至

P5312 竞赛实验班

题面

原题链接 click

题解

看到“排序”操作，自然想到使用一棵权值线段树维护有序数列。
不难发现序列状态一定是：前面一段有序数列 \(\mathrm{xor}\) 上某个数（称为有序段），后面一段无序数列（称为无序段）。
然后我们发现：

  • \(1\) 操作就是在无序段中插一个数；
  • \(2\) 就是有序段区间和以及无序段区间和；
  • \(3\) 操作就是有序段全局 \(\mathrm{xor}\)；
  • \(4\) 操作就是把有序段内 \(\mathrm{xor}\) 的懒标记下放，并把无序段并入有序段。

而这些操作都是权值线段树容易维护的（注意，每个结点内要开数组维护区间内某二进制位为 \(1\) 的数的个数，所以多一个 \(\log\)）。
总复杂度 \(O(n\log^2A)\)，空间 \(O(n\log A)\) 压线通过。

Code 
#include<bits/stdc++.h>
using namespace std;
namespace ds1{
    int Tag;
    struct node{
        int ls,rs;
        int d,tag;
        int cnt;
        long long sum;
        int a[30];
    };
    node s[3280005];
    int cnt;
    inline void build(){
        cnt=1;
        s[1]={0,0,30,0,0,0,{0}};
    }
    inline void down(int p){
        if(!s[p].tag) return;
        if(s[p].tag&(1<<s[p].d-1)){
            swap(s[p].ls,s[p].rs);
        }
        for(int i=0;i<30;i++){
            if(s[p].tag&(1<<i)){
                s[s[p].ls].sum-=((long long)s[s[p].ls].a[i])<<i;
                s[s[p].ls].a[i]=s[s[p].ls].cnt-s[s[p].ls].a[i];
                s[s[p].ls].sum+=((long long)s[s[p].ls].a[i])<<i;
                s[s[p].rs].sum-=((long long)s[s[p].rs].a[i])<<i;
                s[s[p].rs].a[i]=s[s[p].rs].cnt-s[s[p].rs].a[i];
                s[s[p].rs].sum+=((long long)s[s[p].rs].a[i])<<i;
            }
        }
        s[s[p].ls].tag^=s[p].tag; s[s[p].rs].tag^=s[p].tag;
        s[p].tag=0;
    }
    inline void up(int p){
        s[p].tag=0; s[p].cnt=s[s[p].ls].cnt+s[s[p].rs].cnt;
        s[p].sum=s[s[p].ls].sum+s[s[p].rs].sum;
        for(int i=0;i<30;i++) s[p].a[i]=s[s[p].ls].a[i]+s[s[p].rs].a[i];
    }
    void update1(int p,int l,int r,int x){
        if(x>r||x<l) return;
        if(l==r){
            s[p].cnt++; s[p].sum+=x;
            for(int i=0;i<30;i++){
                s[p].a[i]+=(x>>i)&1;
            }
            return;
        }
        if(s[p].ls==0){
            s[p].tag=0;
            s[p].ls=++cnt; s[p].rs=++cnt;
            s[s[p].ls]={0,0,s[p].d-1,0,0,0,{0}};
            s[s[p].rs]={0,0,s[p].d-1,0,0,0,{0}};
        }
        down(p);
        int m=l+r>>1;
        update1(s[p].ls,l,m,x); update1(s[p].rs,m+1,r,x);
        up(p);
    }
    inline void update2(){
        s[1].tag^=Tag;
        for(int i=0;i<30;i++){
            if(Tag&(1<<i)){
                s[1].sum-=((long long)s[1].a[i])<<i;
                s[1].a[i]=s[1].cnt-s[1].a[i];
                s[1].sum+=((long long)s[1].a[i])<<i;
            }
        }
        Tag=0;
    }
    inline void update3(int x){
        Tag^=x;
    }
    inline long long sol(int p,int ss){
        long long res=s[p].sum;
        for(int i=0;i<30;i++){
            if(ss&(1<<i)){
                res-=((long long)s[p].a[i])<<i;
                res+=((long long)s[p].cnt-s[p].a[i])<<i;
            }
        }
        return res;
    }
    long long query(int p,int l,int r,int x){
        if(x==s[p].cnt) return sol(p,Tag);
        if(x==0) return 0;
        if(l==r) return 1ll*(l^Tag)*x;
        down(p);
        int m=l+r>>1;
        if(s[s[p].ls].cnt>=x) return query(s[p].ls,l,m,x);
        else return sol(s[p].ls,Tag)+query(s[p].rs,m+1,r,x-s[s[p].ls].cnt);
    }
}
int pos;
namespace ds2{
    int a[200005][30];
    int re[200005];
    int n,tag;
    inline long long getans(int d){
        long long ans=0;
        for(int i=0;i<30;i++){
            if(tag&(1<<i)){
                ans+=((long long)(d-a[d][i]))<<i;
            }else ans+=((long long)(a[d][i]))<<i;
        }
        return ans;
    }
    inline void add(int x){
        x^=tag; 
        n++; re[n]=x;
        for(int i=0;i<30;i++){
            a[n][i]=a[n-1][i]+((x>>i)&1);
        }
    }
    inline void updxor(int u){
        tag^=u;
    }
    inline void del(){
        pos++; ds1::update1(1,0,(1<<30)-1,re[pos]^tag);
    }
}
int n,q;
inline void upd1(int u){
    ds2::add(u);
}
inline long long qry2(int l,int r){
    if(l>pos) return ds2::getans(r)-ds2::getans(l-1);
    if(r<=pos){
        return ds1::query(1,0,(1<<30)-1,r)-ds1::query(1,0,(1<<30)-1,l-1);
    }
    return ds1::query(1,0,(1<<30)-1,pos)-ds1::query(1,0,(1<<30)-1,l-1)+ds2::getans(r)-ds2::getans(pos);
}
inline void upd3(int d){
    ds2::updxor(d);
    ds1::update3(d);
}
inline void upd4(){
    ds1::update2();
    while(pos<ds2::n) ds2::del();
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int tmp; cin>>tmp; ds2::add(tmp);
    }
    ds1::build();
    cin>>q;
    while(q--){
        int tp,x,y; cin>>tp;
        if(tp==2){
            cin>>x>>y; cout<<qry2(x,y)<<'\n';
        }else if(tp==1){
            cin>>x; upd1(x);
        }else if(tp==3){
            cin>>x; upd3(x);
        }else if(tp==4){
            upd4();
        }
    }
    return 0;
}