首页 » 树状数组 » 正文

牛客Wannafly挑战赛15-数字串


链接:https://www.nowcoder.com/acm/contest/112/D
来源:牛客网

题目描述:

一个只含数字的字符串,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){  //p位置为num,维护数组 
    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){  //p位置不是num了 
    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){  //返回在l与r长度之间,p位置是起点或者终点 
    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;
}

发表评论