题目链接
题意
给定(n)个数，(q)个询问，每次询问([l,r])区间内的逆序对数。
强制在线。
思路
参考：http://www.cnblogs.com/candy99/p/6579556.html
离线的话就如上一题bzoj 3289 Mato的文件管理，可以直接用 莫队 搞，在线的话怎么办呢？
分块大法好。
1
预处理出两个信息：
- (f[i][j])：从 第(i)块开始位置 到 位置(j) 这段区间的逆序对数
- (s[i][j])：前(i)块中(leq j)的数字总数
2
有了这两个信息之后怎么用呢？
考虑一个询问([l,r])，
首先，如果左右端点在同一段内，直接暴力即可，
否则，将其拆成三段看待：
-------------------------------------------------
| ① | ② | ③ |
l l所在块的右端点 r所在块的左端点 r
如上图，
逆序对数=
①中的逆序对数+②中的逆序对数+③中的逆序对数+
①与②间的逆序对数+①与③间的逆序对数+②与③间的逆序对数
根据上面预处理出的信息(f)，
即能直接得到（②+③）一整段的逆序对数，
即②中的逆序对数+③中的逆序对数+②与③间的逆序对数，
复杂度(O(1))
因此，另外要求的就是，
①中的逆序对数+①与②间的逆序对数+①与③间的逆序对数
其中，
①中的逆序对数 及 ①与③间的逆序对数 可以直接树状数组暴力算，
(sqrt n)次插入，(2*sqrt n)次查询，复杂度(O(sqrt n*logn))
①与②间的逆序对数 则需枚举①中的每个数，然后用预处理出的另一个信息(s)，
复杂度(O(sqrt n*1))
3
最后再来讨论一下该如何预处理这两个信息。
(f[i][j])：从 第(i)块开始位置 到 位置(j) 这段区间的逆序对数
对每一块做一次树状数组，复杂度：(2*(sqrt n+2sqrt n+cdots+n)*logn=O(nsqrt nlogn))
(s[i][j])：前(i)块中(leq j)的数字总数
算每一块时，充分利用前缀和思想，先算第(i)块中(= j)的数字总数，再算第(i)块中(leq j)的数字总数，最后算前(i)块中(leq j)的数字总数，复杂度：(O(nsqrt n))
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 50010
#define maxb 310
using namespace std;
typedef long long LL;
int a[maxn], mp[maxn], c[maxn], cnt[maxb][maxn], bl[maxn];
int n, m, nn, num, blo;
struct node { int l, r; }b[maxb];
int f[maxb][maxn];
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return x*f;
}
inline int lowbit(int x) { return x & -x;}
inline int query(int x) { int ret=0; while (x) ret += c[x], x-=lowbit(x); return ret; }
inline void add(int x, int v) { while (x<=nn) c[x] += v, x+=lowbit(x); }
void init(int s) {
b[s].l=s*blo, b[s].r=(s==num-1?n:b[s].l+blo);
memset(c, 0, sizeof c);
F(i, b[s].l, n) {
f[s][i] = f[s][i-1] + i-b[s].l-query(a[i]);
add(a[i], 1);
}
F(i, b[s].l, b[s].r) ++cnt[s][a[i]];
F2(i, 1, nn) cnt[s][i] += cnt[s][i-1];
F2(i, 1, nn) cnt[s][i] += cnt[s-1][i];
}
int ask(int l, int r) {
int ret=0;
if (bl[l]==bl[r]) {
memset(c, 0, sizeof c);
F2(i, l, r) {
ret += i-l-query(a[i]);
add(a[i], 1);
}
}
else {
ret += f[bl[l]+1][r];
memset(c, 0, sizeof c);
F(i, l, b[bl[l]].r) {
ret += i-l-query(a[i]);
add(a[i], 1);
ret += cnt[bl[r]-1][a[i]-1]-cnt[bl[l]][a[i]-1];
}
int ex=b[bl[l]].r-l;
F2(i, b[bl[r]].l, r) ret += ex-query(a[i]);
}
return ret;
}
int main() {
scanf("%d", &n); blo = sqrt(n);
F(i, 0, n) a[i]=mp[i]=read(), bl[i]=i/blo;
sort(mp, mp+n);
nn = unique(mp, mp+n)-mp;
F(i, 0, n) a[i] = lower_bound(mp, mp+nn, a[i])-mp+1;
num = bl[n-1]+1;
F(i, 0, num) init(i);
int lastans=0;
scanf("%d", &m);
F(i, 0, m) {
int l=read(),r=read();
l^=lastans, r^=lastans;
--l, --r; if (l>r) swap(l, r);
if (l<0||r>=n) continue;
printf("%d
", lastans=ask(l,r));
}
return 0;
}