1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 using namespace std; 6 #define N 50010 7 struct node { 8     int l, r, id, ans; 9 } p[N];10 int bit[N], a[N], b[N], num[N], ans, kuai, n;11 12 bool cmp(const node &a, const node &b) {13     if(a.l / kuai == b.l / kuai) return a.r < b.r;14     return a.l / kuai < b.l / kuai;15 }16 bool cmpid(const node &a, const node &b) { return a.id < b.id; }17 int lowbit(int x) { return x & (-x); }18 void add(int x, int w) { for( ; x <= n; x += lowbit(x)) bit[x] += w; }19 int sum(int x) { int ans = 0; for( ; x ; x -= lowbit(x)) ans += bit[x]; return ans; }20 21 int main() {22     while(~scanf("%d", &n)) {23         for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];24         int q; scanf("%d", &q);25         for(int i = 1; i <= q; i++) scanf("%d%d", &p[i].l, &p[i].r), p[i].id = i;26 27         memset(bit, 0, sizeof(bit));28         ans = 0; kuai = sqrt(n);29         sort(b + 1, b + 1 + n);30         int cnt = unique(b + 1, b + 1 + n) - b - 1;31         for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;32 33         sort(p + 1, p + 1 + q, cmp);34         for(int L = 1, R = 0, i = 1; i <= q; i++) {35             int l = p[i].l, r = p[i].r;36             for( ; L < l; L++) { ans -= sum(a[L] - 1); add(a[L], -1); }37             for( ; L > l; L--) { ans += sum(a[L-1] - 1); add(a[L-1], 1); }38             for( ; R < r; R++) { ans += R - L + 1 - sum(a[R+1]); add(a[R+1], 1); }39             for( ; R > r; R--) { ans -= R - L + 1 - sum(a[R]); add(a[R], -1); }40             p[i].ans = ans;41         }42         sort(p + 1, p + 1 + q, cmpid);43         for(int i = 1; i <= q; i++) printf("%d\n", p[i].ans);44     }45     return 0;46 }