首页 > 数字串
开通博客写题解
头像 阿哲不是吧
发表于 2020-10-06 18:33:31
来源：牛客网： 题目描述 一个只含数字的字符串，q次操作，每次操作将第i位数字改为x，每次操作后，统计长度在[l, r]之间且首数字大于尾数字的子串的个数。 输入描述:第一行一个只含数字的字符串；第二行3个整数q, l, r；接下来q行，每行两个整数i, x。输出描述:输出q行，每行一个整数，表示长 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 我想一发AC唔
发表于 2020-08-04 15:25:39
题意 一个只含数字的字符串，q次操作，每次操作将第i位数字改为x，每次操作后，统计长度在[l, r]之间且首数字大于尾数字的子串的个数。 题解 可以维护一个树状数组，logn时间内求得某个字符后边有多少字符小于它。我们先读入字符串并初始化树状数组，求出最初的答案。对于每次修改，我们只需要计算这个字符 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”