天津网站建设技术托管,简单设计网站,如何修改wordpress主题,深圳企业做网站公来源#xff1a;牛客网#xff1a;
题目描述
一个只含数字的字符串#xff0c;q次操作#xff0c;每次操作将第i位数字改为x#xff0c;每次操作后#xff0c;统计长度在[l, r]之间且首数字大于尾数字的子串的个数。
输入描述: 第一行一个只含数字的字符串#xff1b…来源牛客网
题目描述
一个只含数字的字符串q次操作每次操作将第i位数字改为x每次操作后统计长度在[l, r]之间且首数字大于尾数字的子串的个数。
输入描述: 第一行一个只含数字的字符串 第二行3个整数q, l, r 接下来q行每行两个整数i, x。 输出描述: 输出q行每行一个整数表示长度在[l, r]之间且首数字大于尾数字的子串的个数。 示例1 输入 复制
585605
2 2 4
1 6
4 2输出 复制
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,posl-1,posr-1);//包含第pos位的区间 for(int j 0;j x;j)ans query(j,posl-1,posr-1);for(int j now1;j 9;j)ans- query(j,pos-r1,pos-l1);for(int j x1;j 9;j)ans query(j,pos-r1,pos-l1);要先记住一个条件 我们要替代的位置是pos该位置的数原本是now要替换成x 题目要求统计长度在[l, r]之间且首数字大于尾数字的子串的个数 第一个for因为now被替代了那以now为首字母以小于now的数为尾数子所构成的子串就不存在了所以查询区间[posl-1,posr-1]内小于now数的数量这就是不存在的子串数。为什么区间是[posl-1,posr-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); 感觉讲的足够详细了
代码
#includebits/stdc.h
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn 2e55;
const double esp 1e-12;
const int ff 0x3f3f3f3f;
mapint,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,s1);cinqlr;n strlen(s1);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,il-1,ir-1);//查询 il-1,ir-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,posl-1,posr-1);//包含第pos位的区间 for(int j 0;j x;j)ans query(j,posl-1,posr-1);for(int j now1;j 9;j)ans- query(j,pos-r1,pos-l1);for(int j x1;j 9;j)ans query(j,pos-r1,pos-l1);add(x,pos,1); s[pos] x0;printf(%lld\n,ans);}return 0;
}
