朝田诗乃 的博客

朝田诗乃 的博客

题解 P5501 【[LnOI2019]来者不拒,去者不追】

posted on 2019-08-10 10:17:31 | under 题解 |

考虑莫队。当区间 $[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})$ 。

代码:

#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]);
}