【ZOJ4053】Couleur（主席树，set，启发式）

题意：

有n个位置，每个位置上的数字是a[i]，现在有强制在线的若干个单点删除操作，每次删除的位置都不同，要求每次删除之后求出最大的连续区间逆序对个数

n<=1e5,1<=a[i]<=n

思路：

对于每次删除操作我们可以考虑被删除的数字的贡献

比如区间[l,r]内删除了x这个位置，被分成了[l,x-1]与[x+1,r]两个区间

未删除之前区间总逆序对数可以分为4个部分：[l,x-1]内部，[x+1,r]内部，跨区间，一端为x

一个优秀的结论是内部区间和跨区间部分可以选择两端区间内较小的一段进行暴力枚举计算（启发式），这样每个位置均摊被用到了logn次

然后用总的逆序对数减去其他3部分就是较大区间内部的逆序对数

逆序对部分等价于求某个区间内在[l,r]之间数字的个数，显然使用主席树进行预处理

现在还要维护区间的插入，删除与最大值，这个如果只使用一个splay似乎很难维护多个关键字

大佬new表示并不需要splay，只需要使用set维护被删除的点，就能很快找出被删除的位置处于哪个区间

然而我并不会set，只能照他打一遍了，真是屈辱

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second s

 #define MP make_pair

 #define N   110000

 #define MOD 1000000007

 #define eps 1e-8

 #define pi acos(-1)

 #define oo 1e9

 struct node

 {

     int l,r,s;

 }t[N*];

 struct data

 {

     ll x;

     int l,r;

 };

 ll Ans[N],f[N],ans;

 int a[N],root[N],cnt,n;

 set<int>st;

 typedef set<int>::iterator iter;

 struct setcmp

 {

     bool operator()(const data &x,const data &y)

     {

         return x.x>y.x||(x.x==y.x&&x.l<y.l)||(x.x==y.x&&x.l==y.l&&x.r<y.r);

     }

 };

 set<data,setcmp>S;

 ll query(int l,int r,int x,int y,int L,int R)

 {

     if(l>r||x>y) return ;

     if(x<=l&&r<=y) return t[R].s-t[L].s;

     int mid=(l+r)>>;

     ll ans=;

     if(x<=mid) ans+=query(l,mid,x,y,t[L].l,t[R].l);

     if(y>mid) ans+=query(mid+,r,x,y,t[L].r,t[R].r);

     return ans;

 }

 void update(int l,int r,int x,int &p)

 {

     t[++cnt]=t[p];

     p=cnt;

     t[p].s++;

     if(l==r) return;

     int mid=(l+r)>>;

     if(x<=mid) update(l,mid,x,t[p].l);

      else update(mid+,r,x,t[p].r);

 }

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 int main()

 {

     freopen("zoj4053.in","r",stdin);

     freopen("zoj4053.out","w",stdout);

     int cas;

     scanf("%d",&cas);

     while(cas--)

     {

          scanf("%d",&n);

         for(int i=;i<=n;i++) scanf("%d",&a[i]);

         cnt=;

         ans=;

         st.clear();

         st.insert();

         st.insert(n+);

         S.clear();

         for(int i=;i<=n;i++)

         {

             root[i]=root[i-];

             update(,n,a[i],root[i]);

         }

         ll ans=;

         for(int i=;i<=n;i++) ans+=query(,n,a[i]+,n,root[],root[i-]);

         S.insert((data){ans,,n});

         f[]=ans;

         for(int i=;i<=n;i++)

         {

             ans=(*S.begin()).x;

             Ans[i]=ans;

             ll x;

             scanf("%lld",&x);

             x^=ans;

             iter p=st.lower_bound(x);

             int r=*p;

             p--;

             int l=*p;

             l++; r--;

             S.erase(S.lower_bound((data){f[l],l,r}));

             ans=f[l];

             ll t1=;

             ll t2=;

             if(x-l<r-x)

             {

                 for(int i=l;i<x;i++)

                 {

                     t1+=query(,n,,a[i]-,root[i],root[x-]);

                     ans-=query(,n,,a[i]-,root[i],root[r]);

                 }

                 ans-=query(,n,,a[x]-,root[x],root[r]);

                 t2=ans;

             }

              else

              {

                  for(int i=x+;i<=r;i++)

                  {

                      t2+=query(,n,a[i]+,n,root[x],root[i-]);

                      ans-=query(,n,a[i]+,n,root[l-],root[i-]);

                  }

                  ans-=query(,n,a[x]+,n,root[l-],root[x-]);

                  t1=ans;

              }

              if(<=x-)

              {

                      S.insert((data){t1,l,x-});

                     f[l]=t1;

              }

              if(x+<=r)

              {

                  S.insert((data){t2,x+,r});

                  f[x+]=t2;

              }

              st.insert(x);

         }

         for(int i=;i<n;i++) printf("%lld ",Ans[i]);

         printf("%lld\n",Ans[n]); 

     }

     return ;

 }

巴特西

【ZOJ4053】Couleur（主席树，set，启发式）

最新文章

热门文章