这题就是考你怎么把能优化常数的地方都优化一下。
做法比较清晰，分块加持久化值域线段树。大块预处理，小块暴力算。虽然最初不想写持久化数据结构就试图用平衡树去做，结果发现做法是错的，单次复杂度是O(n*lgn)的。看来我太年轻了。后来改了但是常数巨大也没法跑。
本来是一次询问里有若干次在持久化线段树上查询的。然后首先发现可以预处理出从开头到一块末尾这一段里有多少个比后面任意一个位置大的数的个数。还有一个数前面比它大的数的个数。这俩加起来常数差不多就小到能过了。
丧心病狂！
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 50009;
const int maxb = 259;
const int maxnd = maxn * 30;
struct seg {
int v;
seg *ls, *rs;
};
inline bool cmpP(const int* a, const int* b) {
return *a < *b;
}
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
int n, m, bs, tb, a[maxn], *r[maxn], lans, t[maxn];
int bb[maxb][maxb], br[maxb], bt[maxb], bi[maxb],bp[maxb][maxb], fb[maxn];
int clo[maxn], ff[maxb][maxn];
seg *sp, *rt[maxn];
#define mid(p) ((p->l+p->r)>>1)
int btQry(int* t, int p) {
int s = 0;
while (p)
s += t[p], p -= (p & -p);
return s;
}
void btChg(int* t, int p, int v) {
while (p <= n)
t[p] += v, p += (p & -p);
}
#define vof(x) ((x)?(x->v):0)
#define lson(x) ((x)?(x->ls):0)
#define rson(x) ((x)?(x->rs):0)
seg *sgtChg(seg* q, int p0, int v0) {
seg *s = sp ++, *p = s;
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
p-> v = vof(q) + v0;
if (p0 <= mid) {
p-> rs = rson(q);
q = lson(q);
p-> ls = sp ++;
p = p-> ls;
r = mid;
}
else {
p-> ls = lson(q);
q = rson(q);
p-> rs = sp ++;
p = p-> rs;
l = mid + 1;
}
}
p-> v = vof(q) + v0;
return s;
}
int sgtQryLower(seg* p, int v) {
int l = 1, r = n, s = 0;
while (l < r && p) {
int mid = (l + r) >> 1;
if (v > mid) {
s += vof(lson(p));
p = rson(p);
l = mid + 1;
}
else {
p = lson(p);
r = mid;
}
}
return s;
}
int query(int l, int r) {
int lb = fb[l] + 1, rb = fb[r] - 1, ans = 0;
if (fb[l] == fb[r]) {
for (int i = l; i <= r; ++ i)
ans += sgtQryLower(rt[r + 1], a[i]) - clo[i];
}
else {
for (int i = lb; i <= rb; ++ i) {
ans += bi[i];
ans += bb[i][rb];
}
for (int i = l; fb[i] < lb; ++ i)
ans += sgtQryLower(rt[r + 1], a[i]) - clo[i];
if (lb)
for (int i = (rb + 1) * bs; i <= r; ++ i)
ans += ff[rb][i] - ff[lb - 1][i];
else
for (int i = (rb + 1) * bs; i <= r; ++ i)
ans += ff[rb][i];
ans += bp[fb[r]][r - bs * fb[r]];
}
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(br, 0, sizeof(br));
memset(bb, 0, sizeof(bb));
memset(bi, 0, sizeof(bi));
memset(bt, 0, sizeof(bt));
readInt(n);
sp = new seg[maxn * 30];
for (bs = 1; bs * bs < n; ++ bs);
for (int i = 0; i < n; ++ i) {
readInt(a[i]);
r[i] = a + i;
fb[i] = i / bs;
}
fb[n] = n;
sort(r, r + n, cmpP);
for (int i = 0, l = *r[0] - 1, v = 0; i < n; ++ i)
if (*r[i] == l)
*r[i] = v;
else
l = *r[i], *r[i] = ++ v;
rt[0] = 0;
for (int i = 0; i < n; ++ i) {
bi[fb[i]] += i - fb[i] * bs - btQry(t, a[i]);
bp[fb[i]][i - fb[i] * bs] = bi[fb[i]];
btChg(t, a[i], 1);
rt[i + 1] = sgtChg(rt[i], a[i], 1);
clo[i] = sgtQryLower(rt[i], a[i]);
if (fb[i] ^ fb[i + 1])
memset(t, 0, sizeof(t));
}
tb = fb[n - 1];
for (int i = 0; i < tb; ++ i) {
int s = 0, c = 0;
memset(t, 0, sizeof(t));
for (int j = i * bs; fb[j] == fb[i * bs]; ++ j)
btChg(t, a[j], 1), ++ c;
for (int j = (i + 1) * bs; j < n; ++ j) {
s += c - btQry(t, a[j]);
if (fb[j] ^ fb[j + 1])
bb[i][fb[j]] = s;
}
}
for (int i = 0; i < tb; ++ i) {
int c = 0;
memset(t, 0, sizeof(t));
for (int j = 0; fb[j] <= fb[i * bs]; ++ j)
btChg(t, a[j], 1), ++ c;
for (int j = (i + 1) * bs; j < n; ++ j)
ff[i][j] = c - btQry(t, a[j]);
}
lans = 0;
readInt(m);
while (m --) {
int l, r;
readInt(l);
readInt(r);
l ^= lans;
r ^= lans;
-- l;
-- r;
printf("%d\n", (lans = query(l, r)));
}
}