题解：SP12563 CDC12_H - Halt The War

yueyixuan1 · 2026-05-12 21:25:23 · 题解

前言

第 9 次写题解。

线段树板子题。

题目大意

给定了一个长为 N 的序列 a，一开始 a_1 \dots a_n 全是 0，随后进行 Q 次操作：

• modification l r 操作需要将 a_l,a_{l+1},\dots,a_{r} 这些数全部加 1，并输出 OK。
• answer l r 操作需要输出目前的 \sum_{i=l}^{r} a_i。

多组数据。

思路

看到不难想到使用线段树。

不太会出门左转这里。

当然这里讲一下简要思路。

记 f_k 存区间和，v_k 存懒标记。

随后建树，这里不再叙述。

修改，考虑两种情况：

• 当前区间完全在修改区间内，更新懒标记 v_k 与 f_k。
• 否则，先将当前的那个节点的懒标记传给它的子节点，然后递归修改它的子节点，最后改一下当前节点的 f。

查询区间和：

• 递归过程中用 p 累加所有祖先节点的懒标记，当区间与你需要求的区间一模一样的时候，那么答案就是 p \times len +f_k。其中 len 代表它的长度。

注意多组数据需要清空哦。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T;
int n,m;
int a[100010];
int v[400010];
int f[400010];

inline void buildtree(int k, int L, int R){
    v[k]=0;
    if (L==R){
        f[k]=a[R];
        return;
    }
    int M=(L+R)>>1;
    buildtree(k+k, L, M);
    buildtree(k+k+1, M+1, R);
    f[k]=f[k+k]+f[k+k+1];
}

inline void insert(int k, int L, int R, int x, int y, int z){
    if (L==x && R==y){
        v[k]+=z;
        return;
    }
    f[k]+=(y-x+1)*z;
    int M=(L+R)>>1;
    if (y<=M){
        insert(k+k, L, M, x,y,z);
    } else{
        if (x>M){
            insert(k+k+1, M+1, R, x,y,z);
        } else{
            insert(k+k, L, M, x, M, z);
            insert(k+k+1, M+1, R, M+1, y, z);
        }
    }
}

inline int solve(int k, int L, int R, int x, int y, int p){
    p+=v[k];
    if (L==x && R==y){
        return p*(R-L+1)+f[k];
    }
    int M=(L+R)>>1;
    if (y<=M){
        return solve(k+k, L, M, x, y, p);
    } else{
        if (x>M){
            return solve(k+k+1, M+1, R, x,y,p);
        } else{
            return solve(k+k, L, M, x, M, p)+solve(k+k+1, M+1, R, M+1, y, p);
        }
    }
}

signed main(){
    scanf("%lld", &T);
    for(int i=1;i<=T;i++){
        printf("Scenario #%lld:\n", i);
        scanf("%lld%lld", &n, &m);
        for(int i=1;i<=n;i++){
            scanf("%lld", &a[i]);
        }
        buildtree(1, 1, n);
        char opt[100];
        for(int x,y,k;m--;){
            scanf("%s%lld%lld", opt, &x, &y);
            if (opt[0]=='m'){
                k=1;
                insert(1, 1, n, x, y, k);
                printf("OK\n");
            } else{
                printf("%lld\n", solve(1, 1, n, x, y, 0));
            }
        }
    }
}

后续

我也很好奇为什么我的代码读入了数组 a_i 居然还能 AC。若有人知道为啥，评论一下，感谢您的回复。

真正的代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T;
int n,m;
int a[100010];
int v[400010];
int f[400010];

inline void buildtree(int k, int L, int R){
    v[k]=0;
    if (L==R){
        f[k]=0;
        return;
    }
    int M=(L+R)>>1;
    buildtree(k+k, L, M);
    buildtree(k+k+1, M+1, R);
    f[k]=f[k+k]+f[k+k+1];
}

inline void insert(int k, int L, int R, int x, int y, int z){
    if (L==x && R==y){
        v[k]+=z;
        return;
    }
    f[k]+=(y-x+1)*z;
    int M=(L+R)>>1;
    if (y<=M){
        insert(k+k, L, M, x,y,z);
    } else{
        if (x>M){
            insert(k+k+1, M+1, R, x,y,z);
        } else{
            insert(k+k, L, M, x, M, z);
            insert(k+k+1, M+1, R, M+1, y, z);
        }
    }
}

inline int solve(int k, int L, int R, int x, int y, int p){
    p+=v[k];
    if (L==x && R==y){
        return p*(R-L+1)+f[k];
    }
    int M=(L+R)>>1;
    if (y<=M){
        return solve(k+k, L, M, x, y, p);
    } else{
        if (x>M){
            return solve(k+k+1, M+1, R, x,y,p);
        } else{
            return solve(k+k, L, M, x, M, p)+solve(k+k+1, M+1, R, M+1, y, p);
        }
    }
}

signed main(){
    scanf("%lld", &T);
    for(int i=1;i<=T;i++){
        printf("Scenario #%lld:\n", i);
        scanf("%lld%lld", &n, &m);
        buildtree(1, 1, n);
        char opt[100];
        for(int x,y,k;m--;){
            scanf("%s%lld%lld", opt, &x, &y);
            if (opt[0]=='m'){
                k=1;
                insert(1, 1, n, x, y, k);
                printf("OK\n");
            } else{
                printf("%lld\n", solve(1, 1, n, x, y, 0));
            }
        }
    }
}