2025 ICPC Asia Manila Regional（2025 ICPC 亚洲 菲律宾 马尼拉）——B. DJ Nicholas（get_range_cnt，可以变为 get_pref_cnt(r)-get_pref_cnt(l - 1)，是一个非常经典的套路） · znzryb
## 题目大意
**题目设定**
给定一个包含 $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$ 的子串。
1. `? 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****`。
1. 执行 `+ 2 8 10`：
播放列表第 8 到 10 的位置被替换后变为：`DACDA*BCD`。
1. 执行 `+ 9 1 4`：
覆盖掉前 4 个位置的歌曲，播放列表最终变为：`CDABDA*BCD`。
1. 执行 `? 4 9`：
查看当前播放列表中第 4 到第 9 首歌，对应片段为 `BDA*BC`。
需要输出 A、B、C、D 四个字母在此片段内分别出现的次数。因此，输出 `1 2 1 1`。
## 思路讲解
其实还是很明显的动态开点线段树。我说白了是个动态开点线段树的云玩家，我都看出来是动态开点线段树了。
[P13825 【模板】线段树 1.5（指针式动态开点线段树）](/2026/03/08/20260308-1a1d47d5)
既然是这个动态开点线段树，我们想一想，我们的 apply 函数如何书写吧。
其实最重要的是，在知道母带上 l，r 的情况下，求出母带上的 cnt 数组。
**get_range_cnt，可以变为 get_pref_cnt(r)-get_pref_cnt(l - 1)**，是一个非常经典的套路。
```cpp
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](https://codeforces.com/gym/106262/submission/365836934)
::: 源代码
```cpp
/**
* 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……）
