bzoj3744 Gty的妹子序列

　　乱搞，处理出这三样东西，[1,i]所包含的逆序对数cnt[i],区间[1,i]对于区间[j*sqrt(n),(j+1)*sqrt(n)]的逆序对数sum[j][i],以及倒序将每个元素插入主席树，那么询问[l,r]的答案就为[1,r]的逆序对数减去[1,l-1]的逆序对数减去(A,B)(A∈[1,l-1],B∈[l,r])的逆序对数，最后一个可以根据预处理出的信息求出，时间复杂度O(nsqrt(n)log(n))。

　　代码

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<vector>
  4 #include<map>
  5 #define fi first
  6 #define sc second
  7 #define mp make_pair
  8 #define pb push_back
  9 #define lb(x) (x&-x)
 10 using namespace std;
 11 const int N = 50010;
 12 const int M = 1010100;
 13 int n,a[N],i,j,k,cnt[N],c[N],tot,B,tt,v[M],b[N];
 14 int s[205][N],ls[M],rs[M],root[N],ans;
 15 map<int,int> ma;
 16 void insert(int &x,int y,int l,int r,int a,int b)
 17 {
 18     x=++tt;
 19     ls[x]=ls[y];
 20     rs[x]=rs[y];
 21     v[x]=v[y];
 22     if ((a<=l)&&(r<=b))
 23     {
 24         v[x]++;
 25         return;
 26     }
 27     int m=(l+r)>>1;
 28     if (a<m) insert(ls[x],ls[y],l,m,a,b);
 29     if (m<b) insert(rs[x],rs[y],m,r,a,b);
 30     v[x]=v[ls[x]]+v[rs[x]];
 31 }
 32 int query(int y,int x,int l,int r,int a,int b)
 33 {
 34     if (!y) return 0;
 35     if ((a<=l)&&(r<=b)) return v[y]-v[x];
 36     int m=(l+r)>>1,ans=0;
 37     if (a<m) ans+=query(ls[y],ls[x],l,m,a,b);
 38     if (m<b) ans+=query(rs[y],rs[x],m,r,a,b);
 39     return ans;
 40 }
 41 void cc(int x,int w)
 42 {
 43     while (x<=tot)
 44     {
 45         c[x]+=w;
 46         x+=lb(x);
 47     }
 48 }
 49 int sum(int x)
 50 {
 51     int ans=0;
 52     while (x)
 53     {
 54         ans+=c[x];
 55         x-=lb(x);
 56     }
 57     return ans;
 58 }
 59 int main()
 60 {
 61     scanf("%d",&n);
 62     for (i=0;i<n;i++)
 63     {
 64         scanf("%d",&a[i]);
 65          b[i]=a[i];
 66     }
 67     sort(b,b+n);
 68     for (i=0;i<n;i++)
 69     if (ma[b[i]]==0) ma[b[i]]=++tot;
 70     for (i=0;i<n;i++)
 71     a[i]=ma[a[i]];
 72     
 73     for (i=0;i<n;i++)
 74     {
 75         if (i) cnt[i]=cnt[i-1]+sum(tot)-sum(a[i]);
 76         cc(a[i],1);
 77     }
 78     B=250;
 79     for (i=0;;i++)
 80     if (i*B>=n) break;
 81     else
 82     {
 83         for (j=1;j<=tot;j++) c[j]=0;
 84         for (j=i*B;(j<(i+1)*B) && (j<n);j++) cc(a[j],1); 
 85         for (j=0;j<n;j++)
 86         {
 87             s[i][j]=sum(tot)-sum(a[j]);
 88             if (j) s[i][j]+=s[i][j-1];
 89         }
 90     }
 91 
 92     for (i=n-1;i>=0;i--)
 93     insert(root[i],root[i+1],0,tot,a[i]-1,a[i]);
 94 
 95     int q;
 96     scanf("%d",&q);
 97     for (i=1;i<=q;i++)
 98     {
 99         int l,r;
100         scanf("%d%d",&l,&r);
101         l^=ans;r^=ans;
102         l--;r--;
103         ans=cnt[r];if (l) ans-=cnt[l-1];
104         for (j=0;j<l/B;j++)
105         {
106             int w=s[j][r];if (l) w-=s[j][l-1];
107             ans-=w;
108         }
109         for (k=j*B;k<l;k++)
110         if (a[k]-1) ans-=query(root[l],root[r+1],0,tot,0,a[k]-1);
111         printf("%d
",ans);
112     }
113     
114 }