题解 P8640 [蓝桥杯 2016 国 A] 圆圈舞

251Sec · 2023-07-28 17:52:59 · 题解

思维难度不高，但是难写的一批。

考虑一个环内的贡献，设环内的点为 1 \sim c，则贡献为：

简单推一下这个式子，就可以得到它等于：

我们可以尝试对一个环维护出 \sum F_i,\sum iF_i, \sum H_j, \sum jH_j, \sum\limits_{i>j} F_iG_j 这些东西，就可以算答案了。可以发现这些东西作为区间信息是可以合并的：前面四个的合并比较显然，第五个东西可以参考 CDQ 分治的思想，即将左边和右边内部的贡献加起来再加上左边对右边的贡献。

看一下操作：后面两种操作是平凡的单点修改，考虑第一种操作。手玩一下，发现如果操作的两个点属于同一个环，那么这个环会裂成两个；如果两个点不属于同一个环，那么环会合并在一起。分讨一下，可以得到，我们需要这样一个数据结构：

• 支持单点修改。
• 支持区间分裂合并。
• 支持查询上面提到的那一堆东西。

可以发现 FHQ Treap 完美满足这个条件，所以写一棵 FHQ Treap 维护即可。

最后放上我写的史山。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
mt19937 rnd(251251);
namespace Treap {
    struct Node {
        int ls, rs;
        int siz, pri, prt;
        ll f, h, sf, sh, tf, th, fh;
        ll ans;
        Node() {}
        Node(ll _f, ll _h) {
            f = _f; h = _h;
            sf = tf = f;
            sh = th = h;
            siz = 1; pri = rnd();
        }
    } f[100005];
    int tcn;
    void Pushup(Node &s, const Node &ls, const Node &rs) {
        s.sf = (ls.sf + rs.sf + s.f) % P;
        s.sh = (ls.sh + rs.sh + s.h) % P;
        s.tf = (ls.tf + rs.tf + rs.sf * (ls.siz + 1) % P + s.f * (ls.siz + 1) % P) % P;
        s.th = (ls.th + rs.th + rs.sh * (ls.siz + 1) % P + s.h * (ls.siz + 1) % P) % P;
        s.fh = (ls.fh + rs.fh + s.h * rs.sf % P + s.f * ls.sh % P + ls.sh * rs.sf % P) % P;
        s.siz = ls.siz + rs.siz + 1;
        s.ans = (s.sf * s.th % P - s.sh * s.tf % P + s.siz * s.fh % P + P) % P;
    }
    int NewNode(ll f, ll h) {
        int p = ++tcn;
        Treap::f[p] = Node(f, h);
        return p;
    }
    void Split(int p, int rk, int &x, int &y) {
        if (!p) {
            x = y = 0;
            return;
        }
        if (f[f[p].ls].siz + 1 <= rk) {
            x = p;
            Split(f[p].rs, rk - f[f[p].ls].siz - 1, f[p].rs, y);
        } else {
            y = p;
            Split(f[p].ls, rk, x, f[p].ls);
        }
        f[f[p].ls].prt = f[f[p].rs].prt = p;
        f[p].prt = 0;
        Pushup(f[p], f[f[p].ls], f[f[p].rs]);
    }
    int Merge(int x, int y) {
        if (!x || !y) return x | y;
        if (f[x].pri >= f[y].pri) {
            f[x].rs = Merge(f[x].rs, y);
            Pushup(f[x], f[f[x].ls], f[f[x].rs]);
            f[f[x].ls].prt = f[f[x].rs].prt = x;
            f[x].prt = 0;
            return x;
        } else {
            f[y].ls = Merge(x, f[y].ls);
            Pushup(f[y], f[f[y].ls], f[f[y].rs]);
            f[f[y].ls].prt = f[f[y].rs].prt = y;
            f[y].prt = 0;
            return y;
        }
    }
    int Rank(int p) {
        int rk = f[f[p].ls].siz + 1;
        while (p) {
            if (p == f[f[p].prt].rs) rk += f[f[f[p].prt].ls].siz + 1;
            p = f[p].prt;
        }
        return rk;
    }
    void ModifyF(int p, int i, ll w) {
        int x = 0, y = 0, z = 0;
        Split(p, i, x, z);
        Split(x, i - 1, x, y);
        f[y].f = f[y].sf = f[y].tf = w;
        Merge(Merge(x, y), z);
    }
    void ModifyH(int p, int i, ll w) {
        int x = 0, y = 0, z = 0;
        Split(p, i, x, z);
        Split(x, i - 1, x, y);
        f[y].h = f[y].sh = f[y].th = w;
        Merge(Merge(x, y), z);
    }
    int Find(int u) {
        return f[u].prt ? Find(f[u].prt) : u;
    }
}
using namespace Treap;
int n, m;
ll ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        ll f, h;
        scanf("%lld%lld", &h, &f);
        if (i == 1) NewNode(f, h);
        else Merge(Find(1), NewNode(f, h));
    }
    ans = f[Find(1)].ans;
    scanf("%d", &m);
    while (m--) {
        int op, p, q;
        scanf("%d%d%d", &op, &p, &q);
        if (op == 1) {
            int x = Find(p), y = Find(q);
            if (x == y) {
                ans -= f[x].ans;
                int rp = Rank(p), rq = Rank(q);
                if (rp < rq) {
                    int a, b, c;
                    Split(x, rq - 1, b, c);
                    Split(b, rp, a, b);
                    int ac = Merge(a, c);
                    ans += f[ac].ans + f[b].ans;
                }
                else {
                    int a, b, c;
                    Split(x, rp, b, c);
                    Split(b, rq - 1, a, b);
                    int ac = Merge(a, c);
                    ans += f[ac].ans + f[b].ans;
                }
            }
            else {
                ans -= f[x].ans + f[y].ans;
                int rp = Rank(p), rq = Rank(q);
                int a, b, c, d;
                Split(x, rp, a, b);
                Split(y, rq - 1, c, d);
                int r = Merge(Merge(a, d), Merge(c, b));
                ans += f[r].ans;
            }

        }
        else if (op == 2) {
            ans -= f[Find(p)].ans;
            ModifyH(Find(p), Rank(p), q);
            ans += f[Find(p)].ans;
        }
        else {
            ans -= f[Find(p)].ans;
            ModifyF(Find(p), Rank(p), q);
            ans += f[Find(p)].ans;
        }
        ans = (ans % P + P) % P;
        printf("%lld\n", ans);
    }
    return 0;
}