BZOJ 3744
题意：强制在线不修改求区间逆序对。
比较容易想到一个做法：用树状数组维护$[1, i]$逆序对数目，然后每个询问$[l,r]$就用$[1,r]$的答案再去除$[1,l-1]$的答案，去除方法是枚举每个$[1,l-1]$的数，在之后$[l, r]$区间找比他小的数的个数，答案减去这个个数即可，可以用树状数组/主席树维护(前缀和)，时间复杂度很高，高达$O(mnlog_n)$
我们可以优化，可以用分块优化暴力枚举。预处理出$s(i,j)$表示第$i$个块最开始的位置到点$j$之间逆序对的个数，用树状数组维护即可，时间复杂度$O(n\sqrt n)$
对于询问，如果$l,r$在同一块，直接树状数组暴力统计，因为在块中。
不在一块的话，找$l$在的块的后面一块，运用$s(i,j)$直接将后面所有的逆序对都处理完了，然后考虑前面不整块，与前面说的容易想到的方法一样，直接做就行，因为在块中所有枚举量被大大减小。
这里代码用了主席树。为了练习主席树求区间小于等于$k$。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 50000 + 5;
int key = 0, n, q, whw, blolen, ai[MAXN], tax[MAXN], bl[MAXN], s[300][50000 + 5], c[MAXN];
int lowbit(int x) {return x & (-x);}
int query(int x) {
int ret = 0;
for (int i = x; i > 0; i -= lowbit(i)) ret += c[i];
return ret;
}
void add(int x, int v) {
for (int i = x; i <= whw; i += lowbit(i)) c[i] += v;
}
#define M ((l + r) >> 1)
int sz, sumv[MAXN * 40], lc[MAXN * 40], rc[MAXN * 40], rt[MAXN];
int mge(int &x, int y) {
if (x == 0) return x = y, 0;
if (y == 0) return 0;
sumv[x] += sumv[y];
mge(lc[x], lc[y]), mge(rc[x], rc[y]);
return 0;
}
void build(int l, int r, int &x, int pos, int v) {
if (x == 0) x = ++sz, sumv[x] = lc[x] = rc[x] = 0;
sumv[x] += v;
if (l == r) return ;
if (pos <= M) build(l, M, lc[x], pos, v); else build(M + 1, r, rc[x], pos, v);
}
int query_zxs(int l, int r, int x, int v) {
if (l == r) return 0;
if (v <= M) return query_zxs(l, M, lc[x], v); else return sumv[lc[x]] + query_zxs(M + 1, r, rc[x], v);
}
int calc(int l, int r) {
int ret = 0;
if (bl[l] == bl[r]) {
ms(c, 0);
for (int i = l; i <= r; i++) add(ai[i], 1), ret += query(whw) - query(ai[i]);
return ret;
} else {
ret = s[bl[l] + 1][r];
for (int i = blolen * bl[l]; i >= l; i--) {
ret += query_zxs(1, whw, rt[r], ai[i]) - query_zxs(1, whw, rt[i], ai[i]);
}
return ret;
}
}
void clean() {
sz = 0;
}
int solve() {
clean();
blolen = sqrt(n);
for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), tax[i] = ai[i], bl[i] = (i - 1) / blolen + 1;
sort(tax + 1, tax + 1 + n), whw = unique(tax + 1, tax + 1 + n) - tax - 1;
for (int i = 1; i <= n; i++) ai[i] = lower_bound(tax + 1, tax + 1 + whw, ai[i]) - tax;
bool f = n % blolen;
for (int i = 1; i <= n / blolen + f; i++) {
int x = (i - 1) * blolen + 1;
ms(c, 0);
for (int j = x; j <= n; j++) s[i][j] = s[i][j - 1], add(ai[j], 1), s[i][j] += query(whw) - query(ai[j]);
}
for (int i = 1; i <= n; i++) build(1, whw, rt[i], ai[i], 1), mge(rt[i], rt[i - 1]);
scanf("%d", &q);
while (q--) {
int l, r; scanf("%d%d", &l, &r);
l ^= key, r ^= key;
printf("%d\n", key = calc(l, r));
}
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
/*
9
5 1 2 3 6 7 8 4 9
100
1 9
*/
