牛客Wannafly挑战赛15-数字串

文章转载自：xuanqis.com

题目链接：点击打开链接

来源：牛客网

题目描述:

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

输入描述:

第一行一个只含数字的字符串；
第二行3个整数q, l, r；
接下来q行，每行两个整数i, x。

输出描述:

输出q行，每行一个整数，表示长度在[l, r]之间且首数字大于尾数字的子串的个数。

思路：

首先根据各个数字建立树状数组，再算出最开始的时候有多少个满足要求的串，然后对于所有的改变操作，计算改变前的受该点影响的值的大小，然后改变该点的数字，再次计算该点所能影响的值，两个值的差值就是改变数字所变化的值，然后用原来的减去就是当前所需要的。
注：代码有参考http://www.mamicode.com/info-detail-2293519.html

代码：

#define ll long long
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
using namespace std; 
const int maxn = 1e5+5;

char s[maxn];
int c[12][maxn];  //存放j前面所具有的i个数
int lowbit(int x) {return x&(-x);}  //lowbit函数
int len;
void update_plus(int num, int p){  //更新数据
    for(int i = p; i <= len; i += lowbit(i)){
        c[num][i]++;
    }     
}

void init(){  //一个个的更新c数组
    for(int i = 1; i <= len; i++){
        update_plus(s[i]-'0', i);
    } 
}

void update_sub(int num, int p){  //进行减少
    for(int i = p; i <= len; i += lowbit(i)){
        c[num][i]--;
    }
}

ll add(int x, int p){  //计算从1到p的x的个数
    ll sum = 0;
    for(int i = p; i >= 1; i -= lowbit(i)){
        sum += 1ll*c[x][i];
    }
    return sum;
}

ll calculate(int p, int l, int r){
    ll sum=0; 
    for(int j = 0; j <= 9; j++){ 
        int b = p+ r-1, a = p+l-1;
        if (a <= len && j < (s[p]-'0')) sum += 1ll*add(j, min(len, b))-1ll*add(j, a-1);
        a = p-r+1, b = p-l+1;
        a = max(a, 1);
        if (b >= 1 && j > (s[p]-'0')) sum += 1ll*add(j, b)-1ll*add(j, a-1);
    }
    return sum;
}
int main() {
    int q, l, r; 
    int p, x;
    //freopen("1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%s", s+1);  //输入数
    len = strlen(s+1);  //长度
    init();  //初始化
    scanf("%d%d%d",&q,&l,&r);  //输入操作数，最小最大长度
    ll ans = 0;
    for(int i = 1; i <= len; i++){
        for(int j = 0; j <= 9; j++){
            int b = i+r-1, a = i+l-1;  //这里a是当前位加l-1，b是当前位加r-1
            if (a <= len && j < (s[i]-'0')) //如果
                ans += 1ll*add(j, min(len, b))-1ll*add(j, a-1);  //b算的减去a算的
        }
    }  //此时ans已经是不修改的值了
    for(int i = 1; i <= q; i++){
        scanf("%d%d", &p, &x);  //输入位置和修改后的值
        ll sum = calculate(p,l,r);  //原先的
        update_sub(s[p]-'0', p);  //原值减少
        update_plus(x, p);  //现值增加
        s[p] = '0'+x;  //注意这里要更改，防止多次更改该值
        ll sum2= calculate(p,l,r); //现在的
        ans = ans-sum+sum2;
        printf("%lld\n", ans);
    }
    return 0;
}