题目描述
给定一串长度为 \(n\) 的数字，数字为 \(0 \sim 9\) 之间的任意一个，下标从 \(1\) 记起。
然后进行 \(m\) 次区间查询，每次查找区间 \([l, r]\) 的区间和，并在查询结束后将区间里的每一个数都 $ + 1$。特殊地，如果 $ + 1$ 前的数字为 \(9\)，那么 $ + 1$ 之后就变成了 \(0\)。
输出每次查询的区间和。
题目分析
使用支持区间加和区间求和的数据结构即可。在这里使用分块和线段树。
分块
跑的飞快。
\(9 + 1 \to 0\) 这个限制非常的难搞。然而我们发现一共只有十个数字，因此不管怎么暴力搞都是没问题的（大不了乘个大常数）。
在每个块内维护以下信息：当前块内 \(1 \sim 9\) 每个数出现的次数（\(cnt_i\)），当前块的懒标记（\(add\)）。那么一个块内的区间和就是：
\[sum = \sum_{i \in [0, 9]} cnt_i \times [(i + add) \mod 10] \]代码示例如下：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
const int N = 250010, M = (int)sqrt(N) + 20;
const int INF = 0x3f3f3f3f;
int n, m, len, w[N];
struct Block {
int l = INF, r = -INF, add;
int cnt[10];
}b[M];
int get(int x) {
return (int)x / len;
}
void change(int k, int &x) {
b[k].cnt[x] -- ;
b[k].cnt[(x + 1) % 10] ++ ;
x = (x + 1) % 10;
}
void modify(int l, int r) {
int lc = get(l), rc = get(r);
if (lc == rc) {
for (int i = l; i <= r; i ++ )
change(lc, w[i]);
return;
}
for (int i = l; i <= b[lc].r; i ++ ) change(lc, w[i]);
for (int i = r; i >= b[rc].l; i -- ) change(rc, w[i]);
for (int i = lc + 1; i <= rc - 1; i ++ )
b[i].add = (b[i].add + 1) % 10;
}
int query_block(int k) {
int ans = 0;
for (int i = 0; i <= 9; i ++ )
ans += b[k].cnt[i] * ((i + b[k].add) % 10);
return ans;
}
int query(int l, int r) {
int lc = get(l), rc = get(r);
int ans = 0;
if (lc == rc) {
for (int i = l; i <= r; i ++ )
ans += (w[i] + b[lc].add) % 10;
return ans;
}
for (int i = l; i <= b[lc].r; i ++ ) ans += (w[i] + b[lc].add) % 10;
for (int i = r; i >= b[rc].l; i -- ) ans += (w[i] + b[rc].add) % 10;
for (int i = lc + 1; i <= rc - 1; i ++ )
ans += query_block(i);
return ans;
}
int main() {
scanf("%d%d", &n, &m); len = (int)sqrt(n);
for (int i = 1; i <= n; i ++ )
scanf("%1d", &w[i]);
for (int i = 1; i <= n; i ++ ) {
b[get(i)].l = min(b[get(i)].l, i);
b[get(i)].r = max(b[get(i)].r, i);
b[get(i)].cnt[w[i]] ++ ;
}
while (m -- ) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r));
modify(l, r);
}
return 0;
}
单次询问复杂度为 \(O(\sqrt{n})\)，空间复杂度 \(O(\sqrt{n})\)
线段树
思路与分块相同，即在每一个节点维护每个数出现的次数。注意 pushup 和 pushdown 的处理。
单次询问复杂度 \(O(\log n)\) 明显快于分块。空间复杂度 \(O(n)\) 略劣。
代码示例如下：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 250010;
int w[N], n, m;
struct Tree {
int l, r;
int sum, add;
int cnt[10];
}tr[N << 2];
#define ls u << 1
#define rs u << 1 | 1
void pushup(int u) {
tr[u].sum = tr[ls].sum + tr[rs].sum;
for (int i = 0; i <= 9; i ++ )
tr[u].cnt[i] = tr[ls].cnt[i] + tr[rs].cnt[i];
}
void push(int u, int k) { // 这里需要注意
tr[u].add += k;
while (k -- ) {
for (int i = 9; i; i -- )
swap(tr[u].cnt[i], tr[u].cnt[i - 1]);
}
tr[u].sum = 0;
for (int i = 1; i <= 9; i ++ )
tr[u].sum += tr[u].cnt[i] * i;
}
void pushdown(int u) {
if (tr[u].add) {
tr[u].add %= 10;
push(ls, tr[u].add);
push(rs, tr[u].add);
tr[u].add = 0;
}
}
void build(int u, int l, int r) {
tr[u] = {l, r};
if (l == r) {
tr[u].sum = w[r];
tr[u].cnt[w[r]] ++ ;
return;
}
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r)
return (void)push(u, 1);
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(ls, l, r);
if (r > mid) modify(rs, l, r);
pushup(u);
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1, sum = 0;
if (l <= mid) sum += query(ls, l, r);
if (r > mid) sum += query(rs, l, r);
return sum;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%1d", &w[i]);
build(1, 1, n);
while (m -- ) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(1, l, r));
modify(1, l, r);
}
return 0;
}