首页 > 代码库 > 【分块】【树状数组】bzoj3744 Gty的妹子序列
【分块】【树状数组】bzoj3744 Gty的妹子序列
离散化，分块。
预处理出：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 else111 {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 }
【分块】【树状数组】bzoj3744 Gty的妹子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。