laekov

离散，然后树状数组+莫队。

最初用的是直接粘过来的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]);

}