【分块】【树状数组】bzoj3787 Gty的文艺妹子序列

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 using namespace std;
  5 int n,m,op,sum;
  6 struct BIT
  7 {
  8     int d[50001];
  9     void add_node(int p,const int &v)
 10     {for(;p<=n;p+=(p&(-p))) d[p]+=v;}
 11     int query(int p)
 12     {int res=0; for(;p;p-=(p&(-p))) res+=d[p]; return res;}
 13 }T[230],S;
 14 struct BIT2
 15 {
 16     int d[230];
 17     void add_node(int p,const int &v)
 18     {for(;p<=sum;p+=(p&(-p))) d[p]+=v;}
 19     void add_range(const int &L,const int &R,const int &v)
 20     {add_node(L,v); if(R!=sum) add_node(R+1,-v);}
 21     int query(int p)
 22     {int res=0; for(;p;p-=(p&(-p))) res+=d[p]; return res;}
 23 }Xs[230],Ys[230];
 24 int sz,l[230],x,y,r[230],a[50001],num[50001],f[230][230],ans;
 25 void makeblock()
 26 {
 27     sz=(int)(sqrt(n)/sqrt(log2(n))); if(!sz) sz=1;
 28     for(sum=1;sum*sz<n;++sum)
 29       {
 30         l[sum]=r[sum-1]+1; r[sum]=sum*sz;
 31         for(int i=l[sum];i<=r[sum];++i) num[i]=sum;
 32       }
 33     l[sum]=r[sum-1]+1; r[sum]=n;
 34     for(int i=l[sum];i<=r[sum];++i) num[i]=sum;
 35 }
 36 void init_BITs()
 37 {
 38     for(int i=1;i<=sum;++i)
 39       {
 40         T[i]=T[i-1];
 41         for(int j=l[i];j<=r[i];++j) T[i].add_node(a[j],1);
 42       }
 43 }
 44 void init_anss()
 45 {
 46     for(int i=1;i<=sum;++i)
 47       {
 48         memset(S.d,0,sizeof(S.d)); int pos=0,res=0;
 49         for(int j=i;j<=sum;++j)
 50           {
 51             for(int k=l[j];k<=r[j];++k)
 52               {
 53                 ++pos;
 54                 S.add_node(a[k],1);
 55                 res+=(pos-S.query(a[k]));
 56               }
 57             f[i][j]=res;
 58           }
 59       } memset(S.d,0,sizeof(S.d));
 60 }
 61 int getMore(const int &L,const int &R,const int &v)
 62 {return sz*(R-L+1)-(T[R].query(v)-T[L-1].query(v));}
 63 int getLess(const int &L,const int &R,const int &v)
 64 {return T[R].query(v-1)-T[L-1].query(v-1);}
 65 void Query()
 66 {
 67     if(num[x]+1>=num[y])
 68       {
 69         int pos=0; ans=0;
 70         for(int i=x;i<=y;i++)
 71           {
 72             pos++;
 73             S.add_node(a[i],1);
 74             ans+=(pos-S.query(a[i]));
 75           }
 76         for(int i=x;i<=y;i++) S.add_node(a[i],-1);
 77         printf("%d\n",ans);
 78       }
 79     else
 80       {
 81         int pos=r[num[x]]-x+1;
 82         ans=f[num[x]+1][num[y]-1]+Xs[num[x]+1].query(num[y]-1)+Ys[num[y]-1].query(num[x]+1);
 83         for(int i=r[num[x]];i>=x;--i)
 84           {
 85             ans+=(getLess(num[x]+1,num[y]-1,a[i])+S.query(a[i]-1));
 86             S.add_node(a[i],1);
 87           }
 88         for(int i=l[num[y]];i<=y;++i)
 89           {
 90             pos++;
 91             S.add_node(a[i],1);
 92             ans+=(pos-S.query(a[i])+getMore(num[x]+1,num[y]-1,a[i]));
 93           }
 94         for(int i=x;i<=r[num[x]];++i) S.add_node(a[i],-1);
 95         for(int i=l[num[y]];i<=y;++i) S.add_node(a[i],-1);
 96         printf("%d\n",ans);
 97       }
 98 }
 99 void Update()
100 {
101     int Pre=0,Nex=0; int &xB=num[x];
102     for(int i=l[xB];i<x;++i) if(a[i]>a[x]) --Pre;
103     for(int i=l[xB];i<x;++i) if(a[i]>y) ++Pre;
104     for(int i=x+1;i<=r[xB];++i) if(a[i]<a[x]) --Nex;
105     for(int i=x+1;i<=r[xB];++i) if(a[i]<y) ++Nex;
106     int t1=T[xB-1].query(a[x]);
107     int t2=T[xB-1].query(y);
108     for(int i=1;i<=xB;++i)
109       {
110         Xs[i].add_range(xB,sum,-((xB-i)*sz-(t1-T[i-1].query(a[x]))));
111         Xs[i].add_range(xB,sum,(xB-i)*sz-(t2-T[i-1].query(y))+Pre);
112       }
113     t1=T[xB].query(a[x]-1);
114     t2=T[xB].query(y-1);
115     for(int j=xB;j<=sum;++j)
116       {
117         Ys[j].add_range(1,xB,t1-T[j].query(a[x]-1));
118         Ys[j].add_range(1,xB,T[j].query(y-1)-t2+Nex);
119       }
120     for(int i=xB;i<=sum;++i)
121       {
122         T[i].add_node(a[x],-1);
123         T[i].add_node(y,1);
124       }
125     a[x]=y;
126 }
127 int main()
128 {
129     scanf("%d",&n);
130     for(int i=1;i<=n;++i) scanf("%d",&a[i]);
131     makeblock(); init_BITs(); init_anss();
132     scanf("%d",&m);
133     for(;m;--m)
134       {
135         scanf("%d%d%d",&op,&x,&y); x^=ans; y^=ans;
136         if(!op) Query();
137         else Update();
138       }
139     return 0;
140 }