來源：?？途W(wǎng)：

題目描述

一個只含數(shù)字的字符串，q次操作，每次操作將第i位數(shù)字改為x，每次操作后，統(tǒng)計長度在[l, r]之間且首數(shù)字大于尾數(shù)字的子串的個數(shù)。

輸入描述:
第一行一個只含數(shù)字的字符串；
第二行3個整數(shù)q, l, r；
接下來q行，每行兩個整數(shù)i, x。
輸出描述:
輸出q行，每行一個整數(shù)，表示長度在[l, r]之間且首數(shù)字大于尾數(shù)字的子串的個數(shù)。
示例1
輸入
復(fù)制

585605 2 2 4 1 6 4 2

輸出
復(fù)制

7 8

備注:

設(shè)字符串長度為n則： 1 <= n <= 100000; 1 <= q <= 100000; 1 <= l <= r <= n; 1 <=
i <= n; 0 <= x <= 9;

題解：

題意很明確，可以用樹狀數(shù)組和線段樹來做
我用的樹狀數(shù)組，用到一個二維的數(shù)組，0~9的每個數(shù)組為一維，記錄的是該范圍內(nèi)數(shù)組x出現(xiàn)的次數(shù)
雖然是二維數(shù)組sum[x][y]，但其實大部分操作和一維樹狀數(shù)組是一樣的，因為數(shù)組sum中的x是給定的，只剩下一個y來變動
本題中有兩個操作，一個是修改數(shù)，一個是輸出結(jié)果
在每次輸出時我們要先將指定位置原來的數(shù)刪去，因為不這樣的話查詢新值的時候可能會把當(dāng)前沒有更新的值算進(jìn)去。即add(now,pos,-1)
在查詢結(jié)果的代碼中，會出現(xiàn)連續(xù)的四個for循環(huán)，我來講解一下：

for(int j = 0;j< now;j++)ans-= query(j,pos+l-1,pos+r-1);//包含第pos位的區(qū)間， for(int j = 0;j< x;j++)ans+= query(j,pos+l-1,pos+r-1);for(int j = now+1;j<= 9;j++)ans-= query(j,pos-r+1,pos-l+1);for(int j = x+1;j<= 9;j++)ans+= query(j,pos-r+1,pos-l+1);

要先記住一個條件：
我們要替代的位置是pos，該位置的數(shù)原本是now，要替換成x
題目要求統(tǒng)計長度在[l, r]之間且首數(shù)字大于尾數(shù)字的子串的個數(shù)
第一個for：因為now被替代了，那以now為首字母，以小于now的數(shù)為尾數(shù)子所構(gòu)成的子串就不存在了，所以查詢區(qū)間[pos+l-1,pos+r-1]內(nèi)小于now數(shù)的數(shù)量，這就是不存在的子串?dāng)?shù)。為什么區(qū)間是[pos+l-1,pos+r-1]呢？因為被代替的位置是pos，題目要求的是長度在[l, r]的子串，所以從pos往后l和r才是我們所要的區(qū)間
第二個for：正好與第一個相反，因為x的加入，所以以x為首字母，小于x的數(shù)為尾字母所構(gòu)成的子串增加，所以要加上，就是上一個翻版
第三個for：因為now沒了，那以now為尾字母，以大于now的數(shù)為首字母的數(shù)所構(gòu)成的子串也沒了，所以要減去
第四個for：是第三個for的翻版
總結(jié)一下：因為now的離開和x的加入，導(dǎo)致以now為首字母和以now為尾字母的情況不再存在，而以x為首字母和以x為尾字母的情況增加
最后記得：要把x加入到樹狀里

add(x,pos,1);

感覺講的足夠詳細(xì)了

代碼：

#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define mod 1000000007 using namespace std; typedef long long ll; const int maxn = 2e5+5; const double esp = 1e-12; const int ff = 0x3f3f3f3f; map<int,int>::iterator it;int n,q,l,r; char s[maxn]; ll sum[11][maxn];int lowbit(int x) {return x&(-x); }ll get_sum(int num,int x)//計算區(qū)間和? {ll ans = 0;for(int i = x;i>= 1;i-= lowbit(i))ans+= sum[num][i];return ans; }ll query(int num,int l,int r) {if(l> n||r< 1) return 0;l = max(1,l);//注意細(xì)節(jié)r = min(n,r);return get_sum(num,r)-get_sum(num,l-1); }void add(int num,int x,int val)//更新num這個數(shù)的那一維? {for(int i = x;i<= n;i+= lowbit(i))sum[num][i]+= val; }int main() {scanf("%s",s+1);cin>>q>>l>>r;n = strlen(s+1);for(int i = 1;i<= n;i++)add(s[i]-'0',i,1);//更新樹狀數(shù)組?ll ans = 0;for(int i = 1;i<= n;i++)for(int j = 0;j< s[i]-'0';j++)ans+= query(j,i+l-1,i+r-1);//查詢 i+l-1,i+r-1之間比他小的數(shù)while(q--){int pos,x,now;scanf("%d %d",&pos,&x);now = s[pos]-'0';//被代替的數(shù)//x是替代的數(shù) add(now,pos,-1);//注意要先減掉，因為不這樣的話查詢新值的時候可能會把當(dāng)前沒有更新的值算進(jìn)去for(int j = 0;j< now;j++)ans-= query(j,pos+l-1,pos+r-1);//包含第pos位的區(qū)間， for(int j = 0;j< x;j++)ans+= query(j,pos+l-1,pos+r-1);for(int j = now+1;j<= 9;j++)ans-= query(j,pos-r+1,pos-l+1);for(int j = x+1;j<= 9;j++)ans+= query(j,pos-r+1,pos-l+1);add(x,pos,1); s[pos] = x+'0';printf("%lld\n",ans);}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的数字串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。