数字串_牛客博客

题目描述

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

输入描述:
第一行一个只含数字的字符串；
第二行3个整数q, l, r；
接下来q行，每行两个整数i, x。
输出描述:
输出q行，每行一个整数，表示长度在[l, r]之间且首数字大于尾数字的子串的个数。
示例1
输入
复制

输出
复制

7
8

备注:

设字符串长度为n则： 1 <= n <= 100000; 1 <= q <= 100000; 1 <= l <= r <= n; 1 <=
i <= n; 0 <= x <= 9;

题解：

题意很明确，可以用树状数组和线段树来做
我用的树状数组，用到一个二维的数组，0~9的每个数组为一维，记录的是该范围内数组x出现的次数
虽然是二维数组sum[x][y]，但其实大部分操作和一维树状数组是一样的，因为数组sum中的x是给定的，只剩下一个y来变动
本题中有两个操作，一个是修改数，一个是输出结果
在每次输出时我们要先将指定位置原来的数删去，因为不这样的话查询新值的时候可能会把当前没有更新的值算进去。即add(now,pos,-1)
在查询结果的代码中，会出现连续的四个for循环，我来讲解一下：

	for(int j = 0;j< now;j++)
			ans-= query(j,pos+l-1,pos+r-1);//包含第pos位的区间， 
		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，该位置的数原本是now，要替换成x
题目要求统计长度在[l, r]之间且首数字大于尾数字的子串的个数
第一个for：因为now被替代了，那以now为首字母，以小于now的数为尾数子所构成的子串就不存在了，所以查询区间[pos+l-1,pos+r-1]内小于now数的数量，这就是不存在的子串数。为什么区间是[pos+l-1,pos+r-1]呢？因为被代替的位置是pos，题目要求的是长度在[l, r]的子串，所以从pos往后l和r才是我们所要的区间
第二个for：正好与第一个相反，因为x的加入，所以以x为首字母，小于x的数为尾字母所构成的子串增加，所以要加上，就是上一个翻版
第三个for：因为now没了，那以now为尾字母，以大于now的数为首字母的数所构成的子串也没了，所以要减去
第四个for：是第三个for的翻版
总结一下：因为now的离开和x的加入，导致以now为首字母和以now为尾字母的情况不再存在，而以x为首字母和以x为尾字母的情况增加
最后记得：要把x加入到树状里

add(x,pos,1);

感觉讲的足够详细了

代码：

#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)//计算区间和?
{
   
	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);//注意细节
	r = min(n,r);
	return get_sum(num,r)-get_sum(num,l-1);
}
 
void add(int num,int x,int val)//更新num这个数的那一维?
{
   
	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);//更新树状数组?
	
	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之间比他小的数
	
	while(q--)
	{
   
		int pos,x,now;
		scanf("%d %d",&pos,&x);
		now = s[pos]-'0';//被代替的数
		//x是替代的数 
		add(now,pos,-1);//注意要先减掉，因为不这样的话查询新值的时候可能会把当前没有更新的值算进去
		for(int j = 0;j< now;j++)
			ans-= query(j,pos+l-1,pos+r-1);//包含第pos位的区间， 
		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;
}