2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——B. DJ Nicholas（get_range_cnt，可以变为 get_pref_cnt(r)-get_pref_cnt(l - 1)，是一个非常经典的套路）

题目大意

题目设定
给定一个包含 $k$（$1 \le k \le 26$）首短歌的曲库，分别用前 $k$ 个大写英文字母表示。
由这 $k$ 首歌可以生成一个无限长的母带（master track）$t$。生成方式为：不断重复这 $k$ 首歌，但在每一次重复整个曲库时，都会将当前序列的第一首歌移动到序列的末尾。
例如，当 $k = 4$ 时，曲库初始为 ABCD，那么母带 $t$ 就是无限长的字符串 ABCD BCDA CDAB DABC ABCD ...。

有一个长度为 $n$ 的播放列表，初始时全部为空白。在此问题中，播放列表和母带均从 1 开始索引。

操作要求
需要对播放列表执行 $q$ 次操作，操作分为以下两种：

1. + i a b：将播放列表中从位置 $a$ 到 $b$（包含两端）的片段，替换为母带 $t$ 中从位置 $i$ 开始、长度为 $b - a + 1$ 的子串。

2. ? a b：查询播放列表中从位置 $a$ 到 $b$（包含两端）的片段。输出 $k$ 个整数，其中第 $j$ 个整数表示该片段中第 $j$ 个英文字母（即第 $j$ 首歌）的出现次数。

输入格式
第一行包含三个空格分隔的整数 $k$、$n$ 和 $q$。
接下来 $q$ 行，每行描述一个操作，格式为 + i a b 或 ? a b。

输出格式
对于每一个 ? a b 操作，输出一行包含 $k$ 个空格分隔的整数，表示查询的结果。

数据范围
$1 \le k \le 26$
$1 \le n \le 10^9$
$1 \le q \le 10^5$
每次操作中：$1 \le i \le 10^9$，$1 \le a \le b \le n$

样例输入

4 10 4
+ 7 2 6
+ 2 8 10
+ 9 1 4
? 4 9

样例输出

1 2 1 1

样例解释
在此样例中，$k = 4$ 且 $n = 10$。母带 $t$ 为 ABCDBCDACDABDABC...。
播放列表初始为空，我们用星号代表空白部分：**********。

1. 执行 + 7 2 6：
   我们需要一个长度为 $6 - 2 + 1 = 5$ 的子串。
   母带 $t$ 中从位置 7 开始、长度为 5 的子串是 DACDA。
   将播放列表中第 2 到第 6 首歌替换为该子串，此时播放列表变为：DACDA****。

2. 执行 + 2 8 10：
   播放列表第 8 到 10 的位置被替换后变为：DACDA*BCD。

3. 执行 + 9 1 4：
   覆盖掉前 4 个位置的歌曲，播放列表最终变为：CDABDA*BCD。

4. 执行 ? 4 9：
   查看当前播放列表中第 4 到第 9 首歌，对应片段为 BDA*BC。
   需要输出 A、B、C、D 四个字母在此片段内分别出现的次数。因此，输出 1 2 1 1。

思路讲解

其实还是很明显的动态开点线段树。我说白了是个动态开点线段树的云玩家，我都看出来是动态开点线段树了。

P13825 【模板】线段树 1.5（指针式动态开点线段树）

既然是这个动态开点线段树，我们想一想，我们的 apply 函数如何书写吧。

其实最重要的是，在知道母带上 l，r 的情况下，求出母带上的 cnt 数组。

get_range_cnt，可以变为 get_pref_cnt®-get_pref_cnt(l - 1)，是一个非常经典的套路。

array<int, 26> get_range_cnt(ll l, ll r) {
    auto R = get_pref_cnt(r);
    auto L = get_pref_cnt(l - 1);
    for (int i = 0; i < k; ++i) {
        R[i] -= L[i];
    }
    return R;
}

AC代码

AC
https://codeforces.com/gym/106262/submission/365836934

源代码

/**
 * Problem: B. DJ Nicholas
 * Contest: 2025 ICPC Asia Manila Regional
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106262/problem/B
 * Created: 2026-03-04 17:34:48
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

// static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
// static constexpr ll mod = 998244353; // (ll)1e9+7;
// static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

ll K;
/*
 *
 */
using arr=array<unsigned int,27>;
bool is_init=false;
vector<vector<ll>> next_ch_rem_pos(28,vector<ll>(28));
arr get_pref(ll r) {
    arr res{};
    if (r==0) {
        return res;
    }

    if (!is_init) {
        vector<ll> str(K*K+2);
        for (int i=1;i<=K;++i) {
            for (int j=1;j<=K;++j) {
                str[K*(i-1)+j]=j;
            }
        }
        for (int i=1;i<=K;++i) {
            rotate(str.begin()+K*(i-1)+1,str.begin()+K*(i-1)+i,str.begin()+K*(i-1)+K+1);
        }
        // 怕这个遍历影响常数？直接存下来不就行了？
        for (int ch=1;ch<=K;++ch) {
            for (int i=1;i<=K*K;++i) {
                if (str[i]==ch) {
                    next_ch_rem_pos[ch][((i-1)/K)]=i;
                }
            }
        }
        is_init=true;
    }

    for (int i=1;i<=K;++i) {
        res[i]+=r/K;
        ll rot=((r/K*K+1-1)/K)%K;
        ll next_pos=next_ch_rem_pos[i][rot]+r/(K*K)*(K*K);
        if (next_pos<=r) {
            ++res[i];
        }
    }
    return res;
}
arr operator-(arr a, arr b) {
    for (int i=1;i<=K;++i) {
        a[i]-=b[i];
    }
    return a;
}
arr get_range(ll l,ll r) {
    // st 是 1-based，我们先切换成 0-based
    return get_pref(r)-get_pref(l-1);
}
struct Tag {
    // 在母串中的这个位置
    ll base=0;
    bool need_apply=false;
    void apply(const Tag &t,ll offset) {
        base=t.base+offset;
        need_apply=true;
    }
};

struct Info {
    ll l=0,r=0;
    arr cnt{};
    static Info merge(const Info &a,const Info &b) {
        Info res=a;
        res.r=b.r;
        for (int i=1;i<=26;++i) {
            res.cnt[i]+=b.cnt[i];
        }
        return res;
    }
    void apply(const Tag&t,ll offset) {
        if (!t.need_apply) return;
        cnt=get_range(t.base+offset,t.base+offset+r-l);
    }
};

// 我认为还是用 C++14 的写法，把你要写的东西传进去比较好，不容易写错
// template<class I=Info,class T=Tag>
struct SEG {
    // 如果不需要泛型，可以用下面的来替代
    using I=Info;
    using T=Tag;
    struct Node {
        I info;
        T tag;
        Node* rs=nullptr;
        Node* ls=nullptr;
    };

    void init_node(Node *u,ll l,ll r) {
        u->info.l=l;
        u->info.r=r;
    }

    Node* root=nullptr;
    ll N;

    static bool isIntersect(ll l1, ll r1, ll l2, ll r2) {
        if (!(l1 > r2 || r1 < l2)) return true;
        return false;
    }

    SEG(ll N):N(N) {
        root=new Node();
        init_node(root,1,N);
    }

    void extend(Node *u) {
        if (u->ls==nullptr) {
            u->ls=new Node();
            init_node(u->ls,u->info.l,(u->info.l+u->info.r)>>1);
        }
        if (u->rs==nullptr) {
            u->rs=new Node();
            init_node(u->rs,((u->info.l+u->info.r)>>1)+1,u->info.r);
        }
    }

    void push(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        extend(u);
        if (u->tag.need_apply) {
            u->ls->info.apply(u->tag,0);
            u->rs->info.apply(u->tag,u->rs->info.l - u->info.l);
            u->ls->tag.apply(u->tag,0);
            u->rs->tag.apply(u->tag,u->rs->info.l - u->info.l);
            u->tag={};
        }
    }
    void pull(Node *u) {
        if (u->info.l==u->info.r) {
            return;
        }
        u->info=I::merge(u->ls->info,u->rs->info);
    }
    void modify(Node*u,ll l,ll r,T t) {
        if (u->info.l>=l && u->info.r<=r) {
            u->info.apply(t,u->info.l-l);
            u->tag.apply(t,u->info.l-l);
            return;
        }
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            modify(u->ls,l,r,t);
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            modify(u->rs,l,r,t);
        }
        pull(u);
    }

    Info query(Node *u,ll l,ll r) {
        if (u->info.l>=l && u->info.r<=r) {
            return u->info;
        }
        Info res;
        bool is_get=false;
        push(u);
        if (isIntersect(u->ls->info.l,u->ls->info.r,l,r)) {
            res=query(u->ls,l,r);
            is_get=true;
        }
        if (isIntersect(u->rs->info.l,u->rs->info.r,l,r)) {
            if (!is_get) {
                res=query(u->rs,l,r);
            }else {
                res=I::merge(res,query(u->rs,l,r));
            }
        }
        return res;
    }
};

void Solve() {
    ll N,Q;
    cin >> K >> N >> Q;
    SEG seg(N);
    for (int i=1;i<=Q;++i) {
        char op;
        cin>>op;
        if (op=='+') {
            ll base,l,r;
            cin>>base>>l>>r;
            seg.modify(seg.root,l,r,{base,true});
        }else {
            ll l,r;
            cin>>l>>r;
            Info res=seg.query(seg.root,l,r);
            for (int j=1;j<=K;++j) {
                cout<<res.cnt[j]<<" ";
            }
            cout<<"\n";
        }
    }
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106262/submission/365836934

*/

心路历程（WA，TLE，MLE……）