用分块莫队离线询问的同时用树状数组快速计算逆序对个数。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define N 56789#define ll long longusing namespace std;int read(){ int x = 0, f = 1; char ch = getchar(); while (ch<'0' || ch>'9') { if (ch=='-') f = -1; ch = getchar(); } while (ch>='0' && ch<='9') { x = x*10 + ch-'0'; ch = getchar(); } return x*f;}struct node{int l, r, id;} q[N];int n, m, k[N], a[N], pos[N], ans[N], s[N], now;bool cmp(node a, node b){ if (pos[a.l] == pos[b.l]) return a.r < b.r; else return a.l < b.l;}int Q(int x){ int a = 0; while (x>0) a+=s[x], x-=x&(-x); return a;}void Add(int x, int c) { while (x<=n) s[x]+=c, x+=x&(-x); }int main(){ n=read(); rep(i, 1, n) k[i]=a[i]=read(); sort(a+1, a+1+n); rep(i, 1, n) k[i] = lower_bound(a+1, a+n+1, k[i])-a; int block = int(sqrt(n)); rep(i, 1, n) pos[i] = (i-1)/block+1; m=read(); rep(i, 1, m) q[i].l=read(), q[i].r=read(), q[i].id = i; sort(q+1, q+1+m, cmp); int l = 1, r = 0; rep(i, 1, m) { while (l < q[i].l) now -= Q(k[l]-1), Add(k[l], -1), l++; while (l > q[i].l) l--, now += Q(k[l]-1), Add(k[l], 1); while (r < q[i].r) r++, now += r-l-Q(k[r]), Add(k[r], 1); while (r > q[i].r) now -= r-l+1-Q(k[r]), Add(k[r], -1), r--; ans[q[i].id] = now; } rep(i, 1, m) printf("%d\n", ans[i]); return 0;}