【分块】【树状数组】bzoj3744 Gty的妹子序列

浏览数：42 / 时间：2015年06月08日

离散化，分块。

预处理出：ans[i][j] 第i块到第j块的逆序对数。

f[i][j] 第1~i块中大于j的数的个数。

g[i][j] 第1~j块中小于j的数的个数。

每次询问时对于整块部分可以O(1)获得。

对于零散部分呢？

>在一列数的后面添加一个数，逆序对数会增加数列中比它大的数的个数。

>在一列数的前面添加一个数，逆序对数会增加数列中比它小的数的个数。

所以统计以上信息的时候，对于整块的部分，我们可以借由预处理的东西差分来O(1)地获得答案，零散的部分就是树状数组咯。

空间复杂度是O(n*sqrt(n))的。

时间复杂度是O(n*sqrt(n)*log(n))的。

P.S.根本不用卡常数什么的呢。

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 #define N 50001
  7 #define BLOCK_SIZE 250
  8 int sz,sum,n,a[N],l[BLOCK_SIZE],r[BLOCK_SIZE],D[N],f[BLOCK_SIZE][BLOCK_SIZE];
  9 int Less[BLOCK_SIZE][N],More[BLOCK_SIZE][N],b[N],en,m,x,y,num[N],ans;
 10 struct Point{int v,p;}t[N];
 11 bool operator < (const Point &a,const Point &b){return a.v<b.v;}
 12 int Res,Num;char C,CH[12];
 13 inline int G()
 14 {
 15     Res=0;C=‘*‘;
 16     while(C<‘0‘||C>‘9‘)C=getchar();
 17     while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();}
 18     return Res;
 19 }
 20 inline void P(int x)
 21 {
 22     Num=0;if(!x){putchar(‘0‘);puts("");return;}
 23     while(x>0)CH[++Num]=x%10,x/=10;
 24     while(Num)putchar(CH[Num--]+48);
 25     puts("");
 26 }
 27 void add(int p,const int &v) {while(p<=n) {D[p]+=v; p+=(p&(-p));}}
 28 int getsum(int p) {int res=0; while(p) {res+=D[p]; p-=(p&(-p));} return res;}
 29 void makeblock()
 30 {
 31     sz=sqrt(n); if(!sz) sz=1;
 32     for(sum=1;sum*sz<n;sum++)
 33       {
 34           l[sum]=r[sum-1]+1;
 35           r[sum]=sum*sz;
 36           for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
 37       }
 38     l[sum]=r[sum-1]+1;
 39     r[sum]=n;
 40     for(int i=l[sum];i<=r[sum];i++) num[i]=sum;
 41 }
 42 void LiSan()
 43 {
 44     sort(t+1,t+n+1); a[t[1].p]=++en;
 45     for(int i=2;i<=n;i++)
 46       {
 47           if(t[i].v!=t[i-1].v) en++;
 48           a[t[i].p]=en;
 49       }
 50 }
 51 void init_each_ans()
 52 {
 53     for(int i=1;i<=sum;i++)
 54       {
 55           memset(D,0,sizeof(D)); int pos=0,res=0;
 56           for(int j=i;j<=sum;j++)
 57             {
 58                 for(int k=l[j];k<=r[j];k++)
 59                   {
 60                       pos++;
 61                       add(a[k],1);
 62                       res+=(pos-getsum(a[k]));
 63                   }
 64                 f[i][j]=res;
 65             }
 66       } memset(D,0,sizeof(D));
 67 }
 68 void init_sum()
 69 {
 70     memcpy(b,a,sizeof(b));
 71     for(int i=1;i<=sum;i++)
 72       {
 73         sort(b+l[i],b+r[i]+1);
 74           memcpy(More[i],More[i-1],sizeof(More[i]));
 75           memcpy(Less[i],Less[i-1],sizeof(Less[i]));
 76           for(int j=1;j<=en;j++)
 77             {
 78                 More[i][j]+=(b+r[i]+1-upper_bound(b+l[i],b+r[i]+1,j));
 79                 Less[i][j]+=(lower_bound(b+l[i],b+r[i]+1,j)-(b+l[i]));
 80             }
 81       }
 82 }
 83 int getMore(const int &L,const int &R,const int &v){return More[R][v]-More[L-1][v];}
 84 int getLess(const int &L,const int &R,const int &v){return Less[R][v]-Less[L-1][v];}
 85 int main()
 86 {
 87     n=G();
 88     for(int i=1;i<=n;i++)
 89       {
 90           t[i].v=G();
 91           t[i].p=i;
 92       }
 93     LiSan(); makeblock(); init_each_ans(); init_sum();
 94     m=G();
 95     for(int j=1;j<=m;j++)
 96       {
 97           x=G(); y=G(); x^=ans; y^=ans;
 98           if(num[x]+1>=num[y])
 99             {
100                 int pos=0; ans=0;
101                 for(int i=x;i<=y;i++)
102                   {
103                       pos++;
104                       add(a[i],1);
105                       ans+=(pos-getsum(a[i]));
106                   }
107                 for(int i=x;i<=y;i++) add(a[i],-1);
108               P(ans);
109             }
110           else
111             {
112                 int pos=r[num[x]]-x+1; ans=f[num[x]+1][num[y]-1];
113                 for(int i=r[num[x]];i>=x;i--)
114                   {
115                       ans+=(getLess(num[x]+1,num[y]-1,a[i])+getsum(a[i]-1));
116                       add(a[i],1);
117                   }
118                 for(int i=l[num[y]];i<=y;i++)
119                   {
120                       pos++;
121                       add(a[i],1);
122                       ans+=(pos-getsum(a[i])+getMore(num[x]+1,num[y]-1,a[i]));
123                   }
124                 for(int i=x;i<=r[num[x]];i++) add(a[i],-1);
125                 for(int i=l[num[y]];i<=y;i++) add(a[i],-1);
126               P(ans);
127             }
128       }
129     return 0;
130 }