BZOJ 3809 Gty的二逼妹子序列

【题意】莫队加树状数组的做法很显然，解法借鉴HZWER大牛，这道题可以这样做，考虑对权值分块，这样使得每次查询复杂度变为√n，而修改的复杂度变为O1 总复杂度降为m√n，其实我自己一直没怎么想懂这个问题，感觉这个复杂度确实没优化多少。 【AC 代码】 #include <math.h> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn=100010; int n,m,sz; int a[maxn],ans[1000010]; int pos[maxn],l[maxn],r[maxn]; int c[maxn],blockans[maxn];//BIT struct node{ int l,r,a,b,id; friend bool operator<(const node &aa,const node &bb){ if(pos[aa.l]==pos[bb.l]) return aa.r<bb.r; return aa.l<bb.l; } }q[1000010]; int queryans(int x,int y){ int tmp=0; int L=pos[x],R=pos[y]; for(int i=L+1; i<R; i++) tmp+=blockans[i]; if(L==R){ for(int i=x; i<=y; i++){ if(c[i]) tmp++; } }else{ for(int i=x; i<=r[L]; i++){ if(c[i]) tmp++; } for(int i=l[R]; i<=y; i++){ if(c[i]) tmp++; } } return tmp; } void del(int x){ c[x]--; if(c[x]==0) blockans[pos[x]]--; } void add(int x){ c[x]++; if(c[x]==1) blockans[pos[x]]++; } void solve() { int l=1,r=0; for(int i=1; i<=m; i++){ while(l<q[i].l) del(a[l]),l++; while(r>q[i].r) del(a[r]),r--; while(l>q[i].l) l--,add(a[l]); while(r<q[i].r) r++,add(a[r]); ans[q[i].id]=queryans(q[i].a,q[i].b); } } int main() { memset(c,0,sizeof(c)); memset(blockans,0,sizeof(blockans)); memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); scanf("%d%d",&n,&m); sz=(int)sqrt(n); for(int i=1; i<=n; i++){ pos[i]=i/sz; } for(int i=1; i<=n; i++){ r[pos[i]]=i; if(!l[pos[i]]) l[pos[i]]=i; } for(int i=1; i<=n; i++){ scanf("%d",&a[i]); } for(int i=1; i<=m; i++){ scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b); q[i].id=i; } sort(q+1,q+m+1); solve(); for(int i=1; i<=m; i++){ printf("%d\n",ans[i]); } }