[LCT刷题] P1501 [国家集训队]Tree II

题目思路

要求维护树上路径和，支持乘法、加法。

考虑如何使用LCT维护。首先LCT自带的反转标记仍然需要，在此基础上增加乘法标记和加法标记，然后会发现：标记无法像线段树一样用“区间长度”乘标记维护，因为LCT不具有区间长度规律。因此再记录一个 s i z e size size表示所在辅助森林中的 S p l a y Splay Splay子树大小，那么就可以实现标记下放：

1. 先释放乘法标记： ( w [ x ] ∗ = v a l ) % = M O D ; ( t r e e [ x ] . s u m ∗ = v a l ) % = M O D ; ( t r e e [ x ] . a d d _ t a g ∗ = v a l ) % = M O D ; ( t r e e [ x ] . m u l _ t a g ∗ = v a l ) % = M O D ; \begin{aligned} (w[x] &*= val) \%= MOD; \\ (tree[x].sum &*= val) \%= MOD; \\ (tree[x].add\_tag &*= val) \%= MOD; \\ (tree[x].mul\_tag &*= val) \%= MOD; \\ \end{aligned} (w[x](tree[x].sum(tree[x].add_tag(tree[x].mul_tag​∗=val)%=MOD;∗=val)%=MOD;∗=val)%=MOD;∗=val)%=MOD;​
2. 再释放加法标记： ( w [ x ] + = v a l ) % = M O D ; ( t r e e [ x ] . s u m + = v a l ∗ t r e e [ x ] . s i z ) % = M O D ; ( t r e e [ x ] . a d d t a g + = v a l ) % = M O D ; \begin{aligned} (w[x] &+= val) \%= MOD;\\ (tree[x].sum &+= val * tree[x].siz) \%= MOD;\\ (tree[x].add_tag &+= val) \%= MOD;\\ \end{aligned} (w[x](tree[x].sum(tree[x].addt​ag​+=val)%=MOD;+=val∗tree[x].siz)%=MOD;+=val)%=MOD;​
3. 最后释放反转标记即可

对于所有的操作，首先 s p l i t split split提取链，然后再对链进行操作即可。注意别抄错板子。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define elif else if
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10, MOD = 51061;

int w[N];

namespace LCT {
    struct Info{
        int sum, siz;
        int add_tag, mul_tag;
        void reset_add() { add_tag = 0; }
        void reset_mul() { mul_tag = 1; }
    } tree[N];
    int ch[N][2], f[N], tag[N];

    #define ls ch[x][0]
    #define rs ch[x][1]

    void init_tag(int n) { 
        for(int i = 1; i > n >> q;
    LCT::init_tag(n);
    for(int i = 1; i  u >> v;
        LCT::link(u, v);
    }    
    while(q--) {
        char op; cin >> op;
        if(op == '+') {
            int u, v, k; cin >> u >> v >> k;
            LCT::split(u, v);
            LCT::push_add(v, k);       
        } elif(op == '-') {
            int u1, v1, u2, v2; cin >> u1 >> v1 >> u2 >> v2;
            LCT::cut(u1, v1), LCT::link(u2, v2);
        } elif(op == '*') {
            int u, v, k; cin >> u >> v >> k;
            LCT::split(u, v);
            LCT::push_mul(v, k);

        } else {
            int u, v; cin >> u >> v;
            LCT::split(u, v);
            cout