任意门：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
1 4 2 3
1
2 4
Sample Output
2
解题思路：
如果是可以离线的话，直接莫队啦。
但是这里强制在线，就需要分块了。
用 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 ;
}