[bzoj3744]Gty的妹子序列解题报告

本文主要是介绍[bzoj3744]Gty的妹子序列解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比较显然的做法是用bit维护做到 $O(n\sqrt \log n)$ 。
但是。。作为一名~~理论计算机科学家~~傻逼，我们需要 $O(n\sqrt n)$ 的做法，注意到如果我们把 $(i,a_i)$ 看成点，实际上要求 $O(1)$ 询问一个矩形内点的个数，这个显然可以用可持久化分块来搞，维护每个块内的前缀和和所有块的前缀和——但是空间复杂度是 $3n\sqrt n$ ，MLE！所以我们被迫改变块的大小，改成 $\sqrt {2n}$ ，这样空间复杂度就是 $2\sqrt {2n}$ ，就可以卡过了。。然后常数巨大被bit虐成狗。。
代码：

#include<cstdio>
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<cmath>
const int N=5e4+1,M=5e4+5;
int a[N],hash[N];void in(int &x){char c=getchar();while(c<'0'||c>'9')c=getchar();for(x=0;c>='0'&&c<='9';c=getchar())x=x*10+(c^'0');
}const int B=317;
//const int B=2;
int bnum[N][160],bcnts[N][160];
int cnts[N][320];int cal(int l,int r,int a,int b){if(l>r||a>b)return 0;int a0=a/B+1,a1=a%B+1,b0=b/B+1,b1=b%B+1;//printf("cal(%d,%d,%d,%d)=",l,r,a,b);int ans;if(a0==b0){ans=cnts[bnum[r][b0]][b1]-cnts[bnum[r][a0]][a1-1]-cnts[bnum[l-1][b0]][b1]+cnts[bnum[l-1][a0]][a1-1];}else{//printf("%d+%d+%d\n",(cnts[bnum[r][b0]][b1]-cnts[bnum[l-1][b0]][b1]),(bcnts[r][b0-1]-bcnts[r][a0]-bcnts[l-1][b0-1]+bcnts[l-1][a0]),(cnts[bnum[r][a0]][B]-cnts[bnum[r][a0]][a0-1]-cnts[bnum[l-1][a0]][a0]+cnts[bnum[l-1][a0]][a0-1]));ans=(cnts[bnum[r][b0]][b1]-cnts[bnum[l-1][b0]][b1])+(bcnts[r][b0-1]-bcnts[r][a0]-bcnts[l-1][b0-1]+bcnts[l-1][a0])+(cnts[bnum[r][a0]][B]-cnts[bnum[r][a0]][a1-1]-cnts[bnum[l-1][a0]][B]+cnts[bnum[l-1][a0]][a1-1]);}//printf("%d\n",ans);return ans;
}const int S=224;
//const int S=2;
int ans[225][225];
int main(){freopen("bzoj_3744.in","r",stdin);freopen("bzoj_3744.out","w",stdout);int n;in(n);for(int i=1;i<=n;++i)in(a[i]);for(int i=n;i;--i)hash[i-1]=a[i];sort(hash,hash+n);int htot=unique(hash,hash+n)-hash;for(int i=n;i;--i)a[i]=lower_bound(hash,hash+htot,a[i])-hash;--htot;for(int i=1;i<=n;++i){memcpy(bnum[i],bnum[i-1],sizeof(bnum[0]));bnum[i][a[i]/B+1]=i;memcpy(bcnts[i],bcnts[i-1],sizeof(bcnts[0]));for(int j=a[i]/B;j<=n/B;++j)++bcnts[i][j+1];memcpy(cnts[i],cnts[bnum[i-1][a[i]/B+1]],sizeof(cnts[0]));for(int j=a[i]%B;j<B;++j)++cnts[i][j+1];}int nowans;for(int i=1;i<=n/S;++i){nowans=0;for(int j=i*S;j<=n;++j){nowans+=cal(i*S,j-1,a[j]+1,htot);if(j%S==0){ans[i][j/S]=nowans;//printf("ans(%d,%d)=%d\n",i*S,j,nowans);}}}return 0;//puts("------------");int m;in(m);int l,r,l0,r0;int lastans=0;while(m--){in(l),in(r);//l^=lastans,r^=lastans;l0=l/S,r0=r/S;lastans=ans[l0+1][r0];if(l0!=r0)for(int i=r-(r%S)+1;i<=r;++i)lastans+=cal(S*(l0+1),i-1,a[i]+1,htot);for(int i=min(r,S*(l0+1)-1);i>=l;--i){//cout<<"Cal("<<i<<")\n";lastans+=cal(i+1,r,0,a[i]-1);}printf("%d\n",lastans);}
}