P6357 题解

· · 题解

无耻的推销博客

题目描述

给定一串长度为 n 的数字，数字为 0 \sim 9 之间的任意一个，下标从 1 记起。

然后进行 m 次区间查询，每次查找区间 [l, r] 的区间和，并在查询结束后将区间里的每一个数都 + 1。特殊地，如果 + 1 前的数字为 9，那么 + 1 之后就变成了 0。

输出每次查询的区间和。

题目分析

使用支持区间加和区间求和的数据结构即可。在这里使用分块和线段树。

分块

感觉跑的飞快。题解区似乎有兄弟卡不过去。

在每个块内维护以下信息：当前块内 $1 \sim 9$ 每个数出现的次数（$cnt_i$），当前块的懒标记（$add$）。那么一个块内的区间和就是： $$sum = \sum_{i \in [0, 9]} cnt_i \times [(i + add) \bmod 10]$$ 代码示例如下： ```cpp #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;
}