bzoj3289 -- 莫队+树状数组

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define N 50010
 8 #define lowbit(x) x&-x
 9 struct Node{
10     int l,r,f;
11 }a[N];
12 struct Ls{
13     int w,f;
14 }l[N];
15 int Ans[N],s,i,j,k,n,m,b[N],c[N],A[N],q,L,R,Res,Sum;
16 inline bool Cmp1(Ls a,Ls b){return a.w<b.w;}
17 inline bool Cmp2(Node x,Node y){
18     if(b[x.l]==b[y.l])return x.r<y.r;
19     return b[x.l]<b[y.l];
20 }
21 inline int Query(int x){
22     int Ans=0;
23     for(;x;x-=lowbit(x))Ans+=c[x];
24     return Ans;
25 }
26 inline void Update(int x,int y){for(;x<=m;x+=lowbit(x))c[x]+=y;}
27 int main(){
28     scanf("%d",&n);
29     for(i=1;i<=n;i++)scanf("%d",&l[i].w),l[i].f=i;
30     sort(l+1,l+n+1,Cmp1);
31     A[l[1].f]=m=1;
32     for(i=2;i<=n;i++)
33     if(l[i].w==l[i-1].w)A[l[i].f]=m;else A[l[i].f]=++m;
34     s=sqrt((double)n);
35     for(i=1;i<=n;i++)b[i]=(i-1)/s+1;
36     scanf("%d",&q);
37     for(i=1;i<=q;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].f=i;
38     sort(a+1,a+q+1,Cmp2);
39     for(i=L=1;i<=q;i++){
40         while(a[i].l<L)L--,Res+=Query(A[L]-1),Update(A[L],1);
41         while(a[i].r>R)R++,Update(A[R],1),Res+=R-L+1-Query(A[R]);
42         while(a[i].l>L)Res-=Query(A[L]-1),Update(A[L],-1),L++;
43         while(a[i].r<R)Update(A[R],-1),Res-=R-L-Query(A[R]),R--;
44         Ans[a[i].f]=Res;
45     }
46     for(i=1;i<=q;i++)printf("%d\n",Ans[i]);
47     return 0;
48 }