离散，然后树状数组+莫队。
最初用的是直接粘过来的1488的sbt，然后极限随机数据要跑14s。好郁闷。
然后改用数状数组就变1s了。是我再次把sbt写丑了还是它常数够厉害TT
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct query {
int i, l, r, pl, pr;
};
typedef unsigned int uint;
const int maxn = 50009;
#define update(_p_) (sz[_p_]=sz[ls[_p_]]+sz[rs[_p_]]+1)
inline bool cmpQry(const query& a, const query& b) {
return a. pl < b. pl || (a. pl == b. pl && a. pr > b. pr);
}
inline bool cmpP(int* a, int* b) {
return *a < *b;
}
int n, m, bsz, a[maxn], *r[maxn], maxa, t[maxn];
uint ans[maxn];;
query q[maxn];
void btChg(int* t, int p, int v) {
for (; p <= maxa; p += (p & -p))
t[p] += v;
}
int btQry(int* t, int p) {
int s = 0;
for (; p; p -= (p & -p))
s += t[p];
return s;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
scanf("%d", a + i), r[i - 1] = a + i;
sort(r, r + n, cmpP);
maxa = 0;
for (int i = 0, l = *r[0] - 1; i < n; ++ i)
if (*r[i] == l)
*r[i] = maxa;
else
l = *r[i], *r[i] = ++ maxa;
for (bsz = 1; bsz * bsz < n; ++ bsz);
scanf("%d", &m);
for (int i = 0; i < m; ++ i) {
scanf("%d%d", &q[i]. l, &q[i]. r);
q[i]. i = i;
q[i]. pl = q[i]. l / bsz;
q[i]. pr = q[i]. r / bsz;
}
sort(q, q + m, cmpQry);
int l = 1, r = 1;
memset(t, 0, sizeof(t));
btChg(t, a[1], 1);
uint tot = 0;
for (int i = 0; i < m; ++ i) {
while (r < q[i]. r) {
++ r;
tot += r - l - btQry(t, a[r]);
btChg(t, a[r], 1);
}
while (l > q[i]. l) {
-- l;
tot += btQry(t, a[l] - 1);
btChg(t, a[l], 1);
}
while (r > q[i]. r) {
btChg(t, a[r], -1);
tot -= r - l - btQry(t, a[r]);
-- r;
}
while (l < q[i]. l) {
btChg(t, a[l], -1);
tot -= btQry(t, a[l] - 1);
++ l;
}
ans[q[i]. i] = tot;
}
for (int i = 0; i < m; ++ i)
printf("%u\n", ans[i]);
}