Bzoj 3289(莫队+树状数组)

BZOJ 3289
题意：不强制在线求区间逆序对。
离线莫队，右端点对逆序对答案的贡献等于当前区间所有大于右端点值的数的个数，可以用树状数组维护这个数。左端点类似，是所有小于左端点值的数的个数。

#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 n, q, whw, ai[MAXN], ans[MAXN], blolen, bl[MAXN], tax[MAXN], c[MAXN];
int nl = 1, nr = 0, nans = 0;
struct data {
    int l, r, id;
    bool operator < (const data &b) const {
        if (bl[l] == bl[b.l]) return r < b.r;
        return bl[l] < bl[b.l];
    }
}xw[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 + 1; i += lowbit(i)) c[i] += v;
}
void clean() {
}
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 + 1;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) scanf("%d%d", &xw[i].l, &xw[i].r), xw[i].id = i;
    sort(xw + 1, xw + 1 + q);
    for (int i = 1; i <= q; i++) {
        while (nl < xw[i].l) nans -= query(ai[nl] - 1), add(ai[nl], -1), nl++;
        while (nl > xw[i].l) nans += query(ai[nl - 1] - 1), add(ai[nl - 1], 1), nl--;
        while (nr < xw[i].r) nans += query(whw + 1) - query(ai[nr + 1]), add(ai[nr + 1], 1), nr++;
        while (nr > xw[i].r) nans -= query(whw + 1) - query(ai[nr]), add(ai[nr], -1), nr--;
        ans[xw[i].id] = nans;
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0; 
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}