首页 > 代码库 > 【分块】【树状数组】bzoj3787 Gty的文艺妹子序列
【分块】【树状数组】bzoj3787 Gty的文艺妹子序列
题解懒得自己写了，Orz一发wangxz神犇的：
http://bakser.gitcafe.com/2014/12/04/bzoj3787-Gty%E7%9A%84%E6%96%87%E8%89%BA%E5%A6%B9%E5%AD%90%E5%BA%8F%E5%88%97-%E5%AE%98%E6%96%B9%E9%A2%98%E8%A7%A3/
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 }
【分块】【树状数组】bzoj3787 Gty的文艺妹子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。