数字串

题意

一个只含数字的字符串，q次操作，每次操作将第i位数字改为x，每次操作后，统计长度在[l, r]之间且首数字大于尾数字的子串的个数。

题解

可以维护一个树状数组，logn时间内求得某个字符后边有多少字符小于它。我们先读入字符串并初始化树状数组，求出最初的答案。对于每次修改，我们只需要计算这个字符修改对于整个答案的影响即可。那么，我们就可以得到整个数组最后的答案。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long LL;
char s[N];
struct BIT {
    int c[10][N];
    int lowbit(int x) {
        return x & (-x);
    }
    void add(int x, int p, int val) {
        for (int i = p; i < N; i += lowbit(i)) c[x][i] += val;
    }
    int ask(int x, int p) {
        int ret = 0;
        for (int i = p; i >= 1; i -= lowbit(i)) ret += c[x][i];
        return ret;
    }
};
BIT bit;
void solve() {
    int q, l, r, p, x; // 首数字大于尾数字
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    LL ret = 0;
    scanf("%d%d%d", &q, &l, &r);
    for (int i = 1; i <= n; i++) bit.add(s[i] - '0', i, 1);
    for (int i = 1; i <= n; i++) {
        if (i + l - 1 <= n) {
            for (int j = 0; j < s[i] - '0'; j++) ret += bit.ask(j, min(i + r - 1, n)) - bit.ask(j, i + l - 2); 
        }
    }
    while (q--) {
        scanf("%d%d", &p, &x);
        if (s[p] == x + '0') {
            printf("%lld\n", ret);
            continue;
        }
        LL temp = 0;
        for (int j = 0; j < s[p] - '0'; j++) {
            if (p + l - 1 <= n)
                temp -= bit.ask(j, min(p + r - 1, n)) - bit.ask(j, p + l - 2);
        }
        for (int j = s[p] - '0' + 1; j < 10; j++) {
            if (p >= l)
                temp -= bit.ask(j, p - l + 1) - bit.ask(j, max(p - r + 1, 1) - 1);
        }
        bit.add(s[p] - '0', p, -1);
        s[p] = x + '0';
        for (int j = 0; j < s[p] - '0'; j++) {
            if (p + l - 1 <= n)
                temp += bit.ask(j, min(p + r - 1, n)) - bit.ask(j, p + l - 2);
        }
        for (int j = s[p] - '0' + 1; j < 10; j++) {
            if (p >= l)
                temp += bit.ask(j, p - l + 1) - bit.ask(j, max(p - r + 1, 1) - 1);
        }
        bit.add(s[p] - '0', p, 1);
        ret += temp;
        printf("%lld\n", ret);
    }
}
int main() {
    solve();
    return 0;
}