题解 P5501 【[LnOI2019]来者不拒，去者不追】
诗乃
2019-08-10 10:17:31
考虑莫队。当区间$[l,r]$已经被处理好时，向区间内加入一个数$x$ ，分析答案的变化。不难发现，区间内比$x$大的数的排名全部提升了一位。所以答案的变化为：
$ans+=$区间内所有比$x$大的数的和$+x*($区间内比$x$小的数的个数$+1)$
删除同理。
可以发现，区间内所有比$x$大的数的和与区间内比$x$小的数的个数比较难在$O(1)$的时间内统计出来。因此我们使用$lxl$巨巨发明的莫队二次离线算法，将这两个值离线出来处理。
为了方便表述，我们将区间$[l,r]$内所有比$x$大的数的和记为$sum(x, [l,r])$，将区间内比$x$小的数的个数记为 $cnt(x, [l,r])$。
以将左端点左移为例，需要询问$sum(a[l-1],[l,r])$的值，相当于询问$sum(a[l-1],[l,n])-sum(a[l-1],[r,n])$。
对于前半部分，我们可以使用树状数组在$O(nlogn)$的时间内求出所有$sum(a[i],[i+1,n])$。对于后半部分，我们可以把所有需要处理的位置 ii 全部记录下来，在模拟莫队完成后处理。
对于后半部分，我们需要一个查询$O(1)$，插入复杂度小于等于$O(\sqrt{n})$的东西来维护，不难想到权值分块。
对于莫队中其他所有端点移动情况可以做类似处理，对于所有的$cnt(x,[l,r])$进行相同处理，随便写一写就切掉啦！
总空间复杂度$O(n)$，时间复杂度$O(nlogn+n\sqrt{n})$。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
const int V = 100000;
const int MAXN = 500050;
const int MAXB = 4050;
void read(int &x) {
char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Qry {int l, r, id; lint ans;} q[MAXN];
struct T {int l, r, id, op;};
int siz, Vsiz, n, m, a[MAXN], cl[MAXN], cr[MAXN], bl[MAXN];
lint ans[MAXN], t1[MAXN], t2[MAXN], pre1[MAXN], pre2[MAXN], pref1[MAXN], pref2[MAXN], c1[MAXN], s1[MAXB], c2[MAXN], s2[MAXB];
void up1(int x, int val) {for( ; x > 0; t1[x] += val, x -= x&(-x));}
lint qr1(int x) {lint res = 0; for(; x <= V; res += t1[x], x += x&(-x)); return res;}
void up2(int x, int val) {for(; x <= V; t2[x] += val, x += x&(-x));}
lint qr2(int x) {lint res = 0; for( ; x > 0; res += t2[x], x -= x&(-x)); return res;}
int cmp(Qry a, Qry b) {return a.l/siz == b.l/siz ? a.r < b.r : a.l < b.l;}
vector <T> vl[MAXN], vr[MAXN];
int main() {
read(n); read(m); siz = sqrt(n); Vsiz = 400;
for(int i = 1; i <= n; ++i) read(a[i]);
for(int i = 1; i <= m; ++i) {read(q[q[i].id = i].l), read(q[i].r); if(q[i].l>q[i].r||q[i].l<1||q[i].r>n) puts("nmd");}
sort(q+1, q+m+1, cmp);
for(int i = 1; i <= n; ++i) {
pre1[i] = qr1(a[i]+1);
pre2[i] = qr2(a[i]-1);
up1(a[i], a[i]); up2(a[i], 1);
pref1[i] = pref1[i-1] + pre1[i] + 1ll * a[i] * (pre2[i] + 1);
}
memset(t1, 0, sizeof t1); memset(t2, 0, sizeof t2);
for(int i = n; i >= 1; --i) {
pre1[i] = qr1(a[i]+1);
pre2[i] = qr2(a[i]-1);
up1(a[i], a[i]); up2(a[i], 1);
pref2[i] = pref2[i+1] + pre1[i] + 1ll * a[i] * (pre2[i] + 1);
}
for(int L = 1, R = 0, i = 1; i <= m; ++i) {
int l = q[i].l, r = q[i].r;
q[i].ans = pref1[r]-pref1[R]+pref2[l]-pref2[L];
if(L < l) vl[r+1].push_back((T) {L, l-1, i, 1});
if(L > l) vl[r+1].push_back((T) {l, L-1, i, -1});
if(R < r) vr[L-1].push_back((T) {R+1, r, i, -1});
if(R > r) vr[L-1].push_back((T) {r+1, R, i, 1});
L = l; R = r;
}
for(int i = 1; i <= Vsiz; ++i) {
cl[i] = cr[i-1] + 1; cr[i] = i*Vsiz;
for(int j = cl[i]; j <= cr[i]; ++j) bl[j] = i;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j < bl[a[i]]; ++j) s2[j] += a[i];
for(int j = cl[bl[a[i]]]; j <= a[i]; ++j) c2[j] += a[i];
for(int j = bl[a[i]]+1; j <= Vsiz; ++j) ++s1[j];
for(int j = a[i]; j <= cr[bl[a[i]]]; ++j) ++c1[j];
for(int j = 0; j < vr[i].size(); ++j) {
int l = vr[i][j].l, r = vr[i][j].r, id = vr[i][j].id;
lint tmp = 0;
for(int k = l; k <= r; ++k)
tmp += 1ll*a[k]*(s1[bl[a[k]-1]]+c1[a[k]-1]) + (s2[bl[a[k]+1]]+c2[a[k]+1]);
q[id].ans += vr[i][j].op * tmp;
}
}
memset(s1, 0, sizeof s1); memset(c1, 0, sizeof c1); memset(s2, 0, sizeof s2); memset(c2, 0, sizeof c2);
for(int i = n; i >= 1; --i) {
for(int j = 1; j < bl[a[i]]; ++j) s2[j] += a[i];
for(int j = cl[bl[a[i]]]; j <= a[i]; ++j) c2[j] += a[i];
for(int j = bl[a[i]]+1; j <= Vsiz; ++j) ++s1[j];
for(int j = a[i]; j <= cr[bl[a[i]]]; ++j) ++c1[j];
for(int j = 0; j < vl[i].size(); ++j) {
int l = vl[i][j].l, r = vl[i][j].r, id = vl[i][j].id;
lint tmp = 0;
for(int k = l; k <= r; ++k)
tmp += 1ll*a[k]*(s1[bl[a[k]-1]]+c1[a[k]-1]) + (s2[bl[a[k]+1]]+c2[a[k]+1]);
q[id].ans += vl[i][j].op * tmp;
}
}
for(int i = 1; i <= m; ++i) q[i].ans += q[i-1].ans, ans[q[i].id] = q[i].ans;
for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
}
```