2025 杭电多校 1 补题

中位数

n 够小，可以考虑 $n^2$ 解法，因而易想到，对于每个数，比他大的记为 1，反之记为 -1，接着遍历每个位置的前缀和，如果有相同的值，就加上出现的次数即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59


#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 i128;
const ll N=2e3+7,mod=998244353;
const ll inf=1e18;
const db eps=1e-8,PI=acos(-1.0);
int a[N],b[N],sum[N],n;
ll val[N<<1];
ll sol(int mid)
{
    rep(i,0,n) {
        sum[i]=0;
        val[i+n]=val[i]=0;
    }
    val[n]=1;
    int pos=0;
    ll ans=0;
    rep(i,1,n) {
        if(a[i]>mid)  b[i]=1;
        else if(a[i]<mid)  b[i]=-1;
        else b[i]=0,pos=i;
        sum[i]=sum[i-1]+b[i];
        if(!pos)  val[sum[i]+n]+=i+1;
        else  ans+=val[sum[i]+n]*i;
    }
    return ans*mid;
}
void solve()
{
    ll ans=0;
    cin>>n;
    rep(i,1,n) {
        cin>>a[i];
    }
    rep(i,1,n) {
        ans+=sol(a[i]);
    }
    printf("%lld\n",ans);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

子序列

注意到题目要求，两侧大于中间，同时原数组是个排列。

求最长的子序列，确定两侧的值，将中间大于两侧的值都删掉即可。

从大到小遍历值，依次确定 l, r，有新来的就更新区间，看能否扩大区域，此时答案即为区域长度减去中间比两侧大的值的数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), pos(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    ll ans = 0;
    if (n == 1) {
        cout << 1 << endl;
        return;
    }
    int l, r;
    l = min(pos[n], pos[n - 1]), r = max(pos[n], pos[n - 1]);
    ans = r - l + 1;
    for (int i = n - 2; i >= 1; i--) {
        if (pos[i] > l && pos[i] < r) continue;
        if (pos[i] < l) {
            l = pos[i];
        } else {
            r = pos[i];
        }
        ans = max(ans, (r - l + 1ll) - (n - i - 1));
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

传送门

优先走同色路径，一直走到不能走，再走需要花费代价的路径。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86


#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 i128;
const ll N=2e5+7,M=1e6+7,mod=998244353;
const ll inf=1e9+7;
const db eps=1e-8,PI=acos(-1.0);
int dis[N];
vector<int> num[N],tmp[N];
vector<pii> nx[N];
bool vis[M],in[N],in2[N],out[N];
void solve()
{
    int n,m;
    cin>>n>>m;
    rep(i,1,m) {
        int u,v,c;
        cin>>u>>v>>c;
        nx[u].push_back(mk(v,c));
        nx[v].push_back(mk(u,c));
    }
    rep(i,1,n) {
        dis[i]=inf;
    }
    dis[1]=0;
    deque<int> q,q2;
    q.push_back(1);
    while(!q.empty()) {
        int x=q.front();
        q.pop_front();
        out[x]=1;
        for(auto y:num[x])  vis[y]=1;
        for(auto [y,c]:nx[x]) {
            if(out[y])  continue;
            if(vis[c]) {
                dis[y]=dis[x];
                num[y].push_back(c);
                if(!in[y])  q.push_front(y),in[y]=1;
            } else {
                if(in[y])  continue;
                dis[y]=dis[x]+1;
                tmp[y].push_back(c);
                if(!in2[y])  q2.push_back(y),in2[y]=1;
            }
        }
        for(auto y:num[x])  vis[y]=0;
        if(q.empty()) {
            for(auto y:q2) {
                if(out[y])  continue;
                in[y]=1;
                q.push_back(y);
                num[y]=tmp[y];
                tmp[y].clear();
            }
            q2.clear();
        }
    }
    printf("%d\n",dis[n]);
    rep(i,1,n) {
        num[i].clear();
        tmp[i].clear();
        in[i]=0;
        in2[i]=0;
        out[i]=0;
        nx[i].clear();
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

景区建设

注意到建设传送器的代价极大，远大于联通传送器的代价，所以首要目的是少建传送器，接着看传送器联通代价可以发现，高度产生的贡献远大于位置差的贡献，所以传送器之间从高到低依次连接。

从高到低构建联通块，联通块的个数，即为传送器的个数，再将每个联通块的最高点排序后依次连接即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
#define int long long

const int N = 1e2 + 7, mod = 1e9 + 7;
const ll INF = 1ll << 34;

int fa[N][N], a[N][N], vis[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m;

void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && a[x][y] > a[nx][ny]) {
            vis[nx][ny] = 1;
            fa[nx][ny] = fa[x][y];
            dfs(nx, ny);
        }
    }
}

bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    return a.first > b.first;
}

bool cmp2(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    return a.first < b.first;
}

void solve() {
    cin >> n >> m;
    vector<pair<int, pair<int, int>>> tmp;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            tmp.push_back({a[i][j], {i, j}});
            fa[i][j] = a[i][j];
            vis[i][j] = 0;
        }
    }
    sort(tmp.begin(), tmp.end(), cmp);
    vector<pair<int, pair<int, int>>> TP;
    ll ans = 0;
    for (auto [x, y] : tmp) {
        if (!vis[y.first][y.second]) {
            vis[y.first][y.second] = 1;
            dfs(y.first, y.second);
            TP.push_back({x, {y.first, y.second}});
            // cout << x << endl;
        }
    }
    ans = TP.size() * (1ll << 34);
    bool flag = 0;
    for (auto [x, y] : TP) {
        if (y.first == 1 && y.second == 1) {
            flag = 1;
            ans -= (1ll << 34);
            break;
        }
    }
    if (!flag) TP.push_back({a[1][1], {1, 1}});
    sort(TP.begin(), TP.end(), cmp2);
    for (int i = 1; i < TP.size(); i++) {
        pair<int, int> now = TP[i].second, lst = TP[i - 1].second;
        // cout << TP[i].first << " " << TP[i - 1].first << endl;
        ans += (114ll * abs(now.first - lst.first) + 5141ll * abs(now.second - lst.second) + 919810ll * abs(TP[i].first - TP[i - 1].first));
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

树上LCM

LCM(x, y) 的过程实际上是对 x, y 的每个质因子个数取 max 的过程。
如果 LCM(x, y) != x，那么如果仅对 y 进行 LCM 操作是无法变成 x 的。

只有 x 的约数，才能做出贡献，我们只需要在所有的路径中不断连接约数，看有多少种连法即可，通过树上 DP 维护。

先找到 x 的所有约数，然后离散化到一个数组中。

进行 DP，当前位置是 x 的约数，才能进行 DP，否则只能继承子状态，结束自身。

若是 x 的约数，即可对其子节点的所有约数出现次数操作，加合。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;


__int128 lcm(ll a, ll b) {
    if (a == 0 || b == 0) return 0;
    return (__int128)a / gcd(a, b) * b;
}


const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n;
    ll x; 
    cin >> n >> x;
    vector<ll> d; 
    map<ll, int> id; 
    d.push_back(0);
    for (ll i = 1; i * i <= x; i++) { 
        if(x % i == 0) {
            d.push_back(i);
            if (i * i != x) {
                d.push_back(x / i);
            }
        }
    }
    sort(d.begin() + 1, d.end()); 
    int m = d.size();
    for (int i = 1; i < m; i++) {
        id[d[i]] = i;
    }
    vector<int> tmp[m + 10];
    for (int i = 1; i < m; i++) {
        for (int j = i; j < m; j++) {
            if (lcm(d[i], d[j]) == x) {
                tmp[i].push_back(j);
                if (i != j) {
                    tmp[j].push_back(i);
                }
            }
        }
    }
    vector<int> nx[n + 10];
    vector<ll> a(n + 10); 
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        nx[u].push_back(v);
        nx[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<vector<ll>> g(n + 10, vector<ll>(m + 10, 0));
    vector<ll> f(n + 10, 0);

    function<void(int, int)> dfs = [&](int u, int fa) {
        bool flag = true;
        if (!id.count(a[u])) {
            flag = false;
        } else {
            g[u][id[a[u]]] = 1;
        }

        if (flag && id[a[u]] == m - 1) {
            f[u] = 1;
        }

        for (auto v : nx[u]) {
            if (v == fa) continue;
            dfs(v, u);
            
            f[u] += f[v]; 

            if (!flag) continue; 

            for (int i = 1; i < m; i++) {
                if (g[v][i] > 0) { 
                    for (auto j : tmp[i]) {
                        f[u] += g[v][i] * g[u][j];
                    }
                }
            }
            for (int i = 1; i < m; i++) {
                if (g[v][i] > 0) {
                    __int128 now = lcm(d[i], a[u]);
                    if (now > x) continue;
                    if (id.count(now)) {
                        int k = id[now];
                        g[u][k] += g[v][i];
                    }
                }
            }
        }
    };
    dfs(1, 0);
    cout << f[1] << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

奸商

奇数长度一定可以，因为中心位置始终是一字符，自己和自己相同。

偶数长度为 n 的如果可以，那么长度为 m (n < m) 的一定可以。

只需要对长度为 len 的串依次判断，左右若不等，赋一份 ascii 码小的记到当前统计结果（通过二进制来记录 17 位字母），若有相等，这一段不需要幻视都可通过。

对所有长度为 len 的串统计过结果后，得到所有可行方案的二进制串，可通过 SOSdp 将所有不可能的方案排除，在剩下的方案中取最小的

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n, len;
    string s;
    cin >> n >> s;
    vector<int> w(20, 0);
    for (int i = 0; i < 17; i++) {
        cin >> w[i];
    }
    cin >> len;
    if (len & 1) len++;
    if (len > n) {
        cout << "0\n";
        return;
    }
    // m 这个变量在 SOS DP 中不再需要，但我们保留 now
    // int m = 0; 
    auto calc = [&](int x) {
        int res = 0;
        for (int i = 0; i < 17; i++) {
            if (x & (1 << i)) {
                res += w[i];
            }
        }
        return res;
    };
    auto find = [&](int l, int r) {
        int res = 0;
        while (l < r) {
            if (s[l] == s[r]) return 0;
            int x = min(s[l], s[r]) - 'a';
            res |= (1 << x);
            l++;
            r--;
        }
        return res;
    };
    vector<int> f(n + 10, 0);
    int now = 0;
    for (int i = 1, j = len; j <= n; i++, j++) {
        f[++now] = find(i - 1, j - 1);
        if (f[now] == 0) now--;
    }
    if (now == 0) {
        cout << "0\n";
        return;
    }
    // 1. 定义一个数组 bad 来标记不可行的方案
    // bad[j] = 1 表示方案 j 是不可行的
    vector<int> bad(1 << 17, 0);
    int all = (1 << 17) - 1; // 用于计算补集

    // 2. 找到所有“根”不可行方案
    // 如果一个方案是某个约束 f[i] 的补集的子集，那它就是不可行的。
    // 我们先标记出这些补集本身。
    for (int i = 1; i <= now; i++) {
        bad[all ^ f[i]] = 1;
    }

    // 3. SOS DP: 将“不可行”属性从超集传播到子集
    // 如果 mask 是不可行的，那么它的任何子集也必然不可行。
    for (int i = 0; i < 17; i++) {
        for (int j = all; j >= 0; j--) {
            // 如果 j 包含第 i 位，并且 j 是不可行的
            if ((j & (1 << i)) && bad[j]) {
                // 那么 j 去掉第 i 位后的子集 (j ^ (1 << i)) 也一定是不可行的
                bad[j ^ (1 << i)] = 1;
            }
        }
    }
    // ---------- SOS DP 结束 ----------

    int ans = 1e9 + 7; // 使用一个较大的初始值
    // 4. 遍历所有方案，找到可行的方案中的最小花费
    for (int i = 0; i < (1 << 17); i++) {
        // 如果 bad[i] 为 0，说明它是一个可行的方案
        if (!bad[i]) {
            ans = min(ans, calc(i));
        }
    }
    
    // 如果 ans 没有被更新，说明没有可行解（理论上不会发生，因为全付费一定可行）
    if (ans == 1e9 + 7) {
        cout << calc(all) << endl; // 这种情况的答案是全付费
    } else {
        cout << ans << endl;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

博弈

nim 获胜：所有堆异或不为 0

anti-nim (最后一次操作的人输) 获胜：

1. 当每堆石子的数量都为 1 时，异或和为 0 时先手获胜；
1. 当有至少一堆石子的个数大于 1 时，异或和不为 0 时先手获胜。

房间可以分为 4 种：

C1 (王牌房, Win): 至少有一堆石子 > 1，且 Grundy 值 G ≠ 0。
- 效果: 先手玩家进入此房间，可完全控制后续，立即获胜。
- 数量计为 n1。
C2 (直通房, Pass-through): 所有石子堆都是 1，且堆数为偶数。
- 效果: 先手玩家进入，会输掉这个子游戏，总步数为偶数。轮次不变，自己继续开启下一房间。
- 数量计为 n2。
C3 (转换房, Conversion): 所有石子堆都是 1，且堆数为奇数。
- 效果: 先手玩家进入，会赢下这个子游戏，总步数为奇数。轮次翻转，对手开启下一房间。
- 数量计为 n3。
C4 (必败房, Lose): 至少有一堆石子 > 1，且 Grundy 值 G = 0。
- 效果: 先手玩家进入，会将控制权交给对手，立即落败。
- 数量计为 n4。

Alice 的目标是排列房间，使得轮到她时，她能进入一个 C1 房；或者轮到 Bob 时，Bob 进入一个 C4 房。

设 P(w, l, t) 为当前玩家面对 w 个王牌房(C1)，l 个必败房(C4)，t 个转换房(C3)时，获胜的概率。当前玩家从这 w+l+t 个房间中随机选择一个作为序列的下一个。

选中 C1 (概率 $\frac{w}{w+l+t}$): 立即获胜。贡献为 $\frac{w}{w+l+t} \times 1$。选中 C4 (概率 $\frac{l}{w+l+t}$): 立即失败。贡献为 $\frac{l}{w+l+t} \times 0$。选中 C3 (概率 $\frac{t}{w+l+t}$): 轮次翻转。对手面对 w, l, t-1 的局面。自己获胜的条件是对手失败。对手获胜概率为 P(w, l, t-1)，所以自己获胜概率为 1 - P(w, l, t-1)。贡献为 $\frac{t}{w+l+t} \times (1 - P(w, l, t-1))$。

将三者相加，得到递推式： $P(w, l, t) = \frac{w + t \cdot (1 - P(w, l, t-1))}{w+l+t}$

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e6 + 7, mod = 1e9 + 7;

ll fact[N];

ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

ll inv(ll x) {
    return qpow(x, mod - 2, mod);
}

void init() {
    fact[0] = fact[1] = 1;
    for (int i = 2; i < N; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
}

void solve() {
    int n;
    cin >> n;
    ll c1 = 0; // 异或和不为 0，且不全是 1 元堆: 先手进入可完全控制后续，立即获胜
    ll c2 = 0; // 全是 1 元堆，堆数为偶数: 总步数为偶数，轮次不变，自己开启下一房间
    ll c3 = 0; // 全是 1 元堆，堆数为奇数: 总步数为奇数，轮次变更，对手开启下一房间
    ll c4 = 0; // 异或和为 0，且不全是 1 元堆: 先手进入会将控制权交给对手，立即落败
    ll tot = 0; // 总堆数
    vector<vector<int>> r(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        tot += x;
        ll G = 0;
        bool one = 1;
        for (int j = 0; j < x; j++) {
            int y;
            cin >> y;
            G ^= y;
            if (y != 1) one = 0;
        }
        if (!one) {
            if (G) c1++;
            else c4++;
        } else {
            if (x & 1) c3++;
            else c2++;
        }
    }

    // 特殊情况：如果场上没有任何决定性的房间 (C1或C4)
    // 游戏结果是确定的，只取决于总步数的奇偶性

    if (c1 == 0 && c4 == 0) {
        if (tot % 2 != 0) {
            cout << fact[n] << endl;
        } else {
            cout << 0 << endl;
        }
        return;
    }

    // 一般情况：存在决定性房间，使用概率模型计算获胜排列的比例
    // 设 P(w, l, t) 为面对 w个C1, l个C4, t个C3房时，当前玩家获胜的概率
    // 递推式: P(w,l,t) = (w * 1 + l * 0 + t * (1-P(w,l,t-1))) / (w+l+t)
    
    ll w = c1, l = c4, t_Max = c3; 

    // 当没有 c3 时，获胜概率等于在所有决定性房间中先选到王牌房的概率

    ll p = 0;
    if (w + l == 0) p = 0;
    else p = w * inv(w + l) % mod;

    for (int i = 1; i <= t_Max; i++) {
        ll tmp = (1 - p + mod) % mod;
        ll num = (w + i * tmp) % mod;
        if (num < 0) num += mod;
        p = (num * inv(w + l + i)) % mod; // 更新 p 为 P(w, l, i)
    }

    ll ans = (fact[n] * p) % mod;
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

夜世界

变量	类型	含义
`l`, `r`	`int`	存储在 `tr` 数组中的索引，分别指向左、右子节点。
`sum`	`ll`	区间 `[l, r]` 内所有 `a_i` 的和。用于计算区间内的总支付额。
`tmp`	`ll`	区间 `[l, r]` 内所有 `b_i` 的和。主要用于辅助计算和理解 `B`。
`B`	`ll`	理想金币净变化。代表在不考虑金币不能为负的限制下，穿过该区间后金币的总增量。`B = sum(a_i - b_i)`。
`A`	`ll`	最低金币保证/保底值。代表无论进入该区间时金币多寡，离开时金币数目的下界。它量化了 `max(0, ...)` 操作的累积效应。

为了使用线段树等数据结构，我们必须将“带着 m_in 的钱穿过一个区间 [L, R]”这个过程，抽象成一个可以快速计算和合并的函数 f(m_in)，使得 m_out = f(m_in)。

单个普通金矿 i 的函数：
- 过程：m -> m + a_i，然后 m -> m - min(m, b_i)。
- 合并后：m_out = (m_in + a_i) - min(m_in + a_i, b_i)。
- 利用恒等式 x - min(x, y) = max(0, x - y)，我们得到： m_out = max(0, m_in + a_i - b_i)。
推广到区间的函数模型：我们发现，单个金矿的函数形式可以被一个更通用的模型所描述： m_out = max(A, m_in + B) 对于单个金矿 i，A=0，B = a_i - b_i。
函数的合并 (核心)：假设我们已知左右两个子区间 [L, mid] 和 [mid+1, R] 的函数参数 (A_L, B_L) 和 (A_R, B_R)。我们来推导合并后的大区间 [L, R] 的新参数 (A_new, B_new)。
- 经过左区间：m_mid = max(A_L, m_in + B_L)
- 带着 m_mid 经过右区间：m_out = max(A_R, m_mid + B_R)
- 代入 m_mid：m_out = max(A_R, max(A_L, m_in + B_L) + B_R)
- 展开化简：m_out = max(A_R, A_L + B_R, m_in + B_L + B_R)
- 整理成目标形式：m_out = max( max(A_R, A_L + B_R), m_in + (B_L + B_R) )
通过对比，我们得到了函数的合并法则：
- B_new = B_L + B_R
- A_new = max(A_R, A_L + B_R)
这个合并操作是 O(1) 的，满足结合律，因此我们可以使用线段树来维护。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 2e5 + 7, mod = 1e9 + 7;

struct Node {
    int l, r;
    ll sum, tmp;
    ll A, B;
};

Node tr[N << 2 + N * 20];
int tot = 0, rt[N], a[N], b[N], n, m;

void pushup(int u) {
    int l = tr[u].l, r = tr[u].r;
    tr[u].sum = tr[l].sum + tr[r].sum;
    tr[u].tmp = tr[l].tmp + tr[r].tmp;

    tr[u].B = tr[l].B + tr[r].B;
    tr[u].A = max(tr[r].A, tr[l].A + tr[r].B);
}

int build(int l, int r) {
    int u = ++tot;
    if (l == r) {
        tr[u].sum = a[l];
        tr[u].tmp = b[l];
        tr[u].B = a[l] - b[l];
        tr[u].A = 0;
        return u;
    }
    int mid = (l + r) >> 1;
    tr[u].l = build(l, mid);
    tr[u].r = build(mid + 1, r);
    pushup(u);
    return u;
}

int update(int lst, int l, int r, int pos, ll va, ll vb) {
    int u = ++tot;
    tr[u] = tr[lst];
    if (l == r) {
        tr[u].sum = va;
        tr[u].tmp = vb;
        tr[u].B = va - vb;
        tr[u].A = 0;
        return u;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        tr[u].l = update(tr[lst].l, l, mid, pos, va, vb);
    } else {
        tr[u].r = update(tr[lst].r, mid + 1, r, pos, va, vb);
    }
    pushup(u);
    return u;
}

Node query_range(int u, int l, int r, int ql, int qr) {
    if (ql > qr) return {0, 0, 0, 0, 0, 0};
    if (ql <= l && qr >= r) {
        return tr[u];
    }
    int mid = (l + r) >> 1;
    if (qr <= mid) {
        return query_range(tr[u].l, l, mid, ql, qr);
    } else if (ql > mid) {
        return query_range(tr[u].r, mid + 1, r, ql, qr);
    } else {
        Node left = query_range(tr[u].l, l, mid, ql, qr);
        Node right = query_range(tr[u].r, mid + 1, r, ql, qr);
        Node res;
        res.l = l; res.r = r;
        res.sum = left.sum + right.sum;
        res.tmp = left.tmp + right.tmp;
        res.B = left.B + right.B;
        res.A = max(right.A, left.A + right.B);
        return res;
    }
}

pair<ll, ll> query_val(int u, int l, int r, int pos) {
    if (l == r) {
        return {tr[u].sum, tr[u].tmp};
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        return query_val(tr[u].l, l, mid, pos);
    } else {
        return query_val(tr[u].r, mid + 1, r, pos);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    tot = 0;
    rt[0] = build(1, n);

    for (int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            ll y;
            cin >> x >> y;
            pair<ll, ll> val = query_val(rt[i - 1], 1, n, x);
            rt[i] = update(rt[i - 1], 1, n, x, y, val.second);
        } else if (op == 2) {
            int x;
            ll y;
            cin >> x >> y;
            pair<ll, ll> val = query_val(rt[i - 1], 1, n, x);
            rt[i] = update(rt[i - 1], 1, n, x, val.first, y);
        } else if (op == 3) {
            int x;
            cin >> x;
            rt[i] = rt[x];
        } else {
            rt[i] = rt[i - 1];
            int k;
            cin >> k;
            vector<int> pos(k + 1);
            for (int j = 1; j <= k; j++) {
                cin >> pos[j];
            }
            ll cur = 0, pay = 0;
            int lst = 0;
            for (int j = 1; j <= k; j++) {
                int now = pos[j];
                if (lst + 1 <= now - 1) {
                    Node res = query_range(rt[i], 1, n, lst + 1, now - 1);
                    ll spend = max(res.A, cur + res.B);
                    pay += (cur + res.sum -spend);
                    cur = spend;
                }
                pair<ll, ll> val = query_val(rt[i], 1, n, now);
                ll sum = cur + val.first;
                ll spend = (sum + 1) / 2;
                pay += spend;
                cur = sum - spend;
                lst = now;
            }
            if (lst <= n) {
                Node res = query_range(rt[i], 1, n, lst + 1, n);
                ll spend = max(res.A, cur + res.B);
                pay += (cur + res.sum - spend);
            }
            cout << pay << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}