BZOJ 3744: Gty的妹子序列【分块 + 树状数组 + 主席树】

任意门：https://www.lydsy.com/JudgeOnline/problem.php?id=3744

3744: Gty的妹子序列

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 2571 Solved: 746
[Submit][Status][Discuss]

Description

我早已习惯你不在身边，

人间四月天寂寞断了弦。

回望身后蓝天，

跟再见说再见……

某天,蒟蒻Autumn发现了从 Gty的妹子树(bzoj3720) 上掉落下来了许多妹子,他发现

她们排成了一个序列,每个妹子有一个美丽度。

Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:"你知道区间

[l,r]中妹子们美丽度的逆序对数吗?"

蒟蒻Autumn只会离线乱搞啊……但是Bakser神犇说道:"强制在线。"

请你帮助一下Autumn吧。

给定一个正整数序列a,对于每次询问,输出al...ar中的逆序对数,强制在线。

Input

第一行包括一个整数n(1<=n<=50000),表示数列a中的元素数。

第二行包括n个整数a1...an(ai>0,保证ai在int内)。

接下来一行包括一个整数m(1<=m<=50000),表示询问的个数。

接下来m行,每行包括2个整数l、r(1<=l<=r<=n),表示询问al...ar中的逆序

对数(若ai>aj且i<j,则为一个逆序对)。

l,r要分别异或上一次询问的答案(lastans),最开始时lastans=0。

保证涉及的所有数在int内。

Output

对每个询问,单独输出一行,表示al...ar中的逆序对数。

Sample Input

4
1 4 2 3
1
2 4

Sample Output

解题思路：

如果是可以离线的话，直接莫队啦。

但是这里强制在线，就需要分块了。

用 f [ j ][ i ] 维护第 j 到第 i 块的右端的答案,这样就省去了处理块前的那些情况了（论前缀和的美妙）。

预处理 f[ j ][ i ] 的方法就是树状数组直接暴力。

如果当前区间【L，R】的 R刚好是某一块的右端点，那么答案就是 f [ L ][ pos[ R ] ]；

如果不是，那么我们还要处理一下 R 到前一块右端点的区间逆序数，

这里分两部分，第一部分是这一区间与前面的的逆序数，用主席树维护。

　　　　　　　第二部分就是这一区间的逆序数了，直接树状数组暴力。

AC code：

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int MAXN = 5e4+;

 int N, M, cnt, tot, ans;

 int c1[MAXN], c2[MAXN];

 int ch[MAXN*][], sum[MAXN*], a[MAXN], d[MAXN];

 int siz, lim, bl[], br[], pos[MAXN];

 int f[MAXN][], root[MAXN];

 void add1(int x, int val)       //维护小的值

 {

     while(x <= N){

         c1[x]+=val;

         x+=(x&(-x));

     }

 }

 void add2(int x, int val)       //维护大的值

 {

     while(x){

         c2[x]+=val;

         x-=(x&(-x));

     }

 }

 int query1(int x)

 {

     int res = ;

     while(x){

         res+=c1[x];

         x-=(x&(-x));

     }

     return res;

 }

 int query2(int x)

 {

     int res = ;

     while(x <= N){

         res+=c2[x];

         x+=(x&(-x));

     }

     return res;

 }

 void update(int x, int &y, int l, int r, int k)

 {

     y = ++tot;

     ch[y][] = ch[x][];

     ch[y][] = ch[x][];

     sum[y] = sum[x]+;

     if(l==r) return;

     int mid = (l+r)/;

     if(k<=mid) update(ch[x][], ch[y][], l, mid, k);

     else update(ch[x][], ch[y][], mid+, r, k);

 }

 int getsum(int x, int y, int l, int r, int L, int R)

 {

     if(L > R) return ;

     if(l >= L && r <= R) return sum[y]-sum[x];

     int mid = (l+r)/, res = ;

     if(L <= mid) res+=getsum(ch[x][], ch[y][], l, mid, L, R);

     if(R > mid) res+=getsum(ch[x][], ch[y][], mid+, r, L, R);

     return res;

 }

 int main()

 {

     int i, j, x, L, R;

     scanf("%d", &N);

     for(int i = ; i <= N; i++){

         scanf("%d", &a[i]);

         d[i] = a[i];

     }

     sort(d+, d++N);

     siz = unique(d+, d++N)-d-;

     for(i = ; i <= N; i++)

         a[i] = lower_bound(d+, d++siz, a[i])-d;

     lim = sqrt(N);

     for(i = ; i <= N; i+=lim){

         bl[++cnt] = i;br[cnt] = min(N, i+lim-);

         for(j = bl[cnt]; j <= br[cnt]; j++)

             pos[j] = cnt;

     }

     for(i = ; i <= cnt; i++){

         add1(a[br[i]], );

         for(j = br[i]-; j >= ; j--){

             f[j][i] = f[j+][i]+query1(a[j]-);

             add1(a[j], );

         }

         for(j = br[i]; j >= ; j--){

             add1(a[j], -);

         }

     }

     for(i = ; i <= N; i++)

         update(root[i-], root[i], , N, a[i]);

     scanf("%d", &M);

     ans = ;

     while(M--){

         scanf("%d %d", &L, &R);

         L^=ans;R^=ans;

         ans = ;

         if(L > R) {puts(""); continue;}

         if(pos[L] == pos[R]){

             for(j = L; j <= R; j++){

                 ans+=query2(a[j]+);

                 add2(a[j], );

             }

             for(j = L; j <= R; j++)

                 add2(a[j], -);

         }

         else{

             if(br[pos[R]] == R){

                 ans = f[L][pos[R]];

             }

             else{

                 ans = f[L][pos[R]-];

                 x = br[pos[R]-];

                 if(x){

                     for(j = x+; j <= R; j++){

                         ans+= getsum(root[L-], root[x], , N, a[j]+, N);

                     }

                     for(j = x+; j <= R; j++){

                         ans+=query2(a[j]+);

                         add2(a[j],);

                     }

                     for(j = x+; j <= R; j++)

                         add2(a[j], -);

                 }

             }

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

BZOJ 3744: Gty的妹子序列【分块 + 树状数组 + 主席树】

3744: Gty的妹子序列

Description

Input

Output

Sample Input

Sample Output

解题思路：

最新文章

热门文章

巴特西

BZOJ 3744: Gty的妹子序列 【分块 + 树状数组 + 主席树】

3744: Gty的妹子序列

Description

Input

Output

Sample Input

Sample Output

解题思路：

最新文章

热门文章

BZOJ 3744: Gty的妹子序列【分块 + 树状数组 + 主席树】