| 题目名称 | 2670. [HAOI 2017]供给侧改革 |
|---|---|
| 输入输出 | supply.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mouse
于2017-04-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：11， 提交：43， 通过率：25.58% | ||||
 ccz181078 |
100 | 0.400 s | 53.45 MiB | C++ |
 Imone NOI2018Au |
100 | 0.410 s | 48.07 MiB | C++ |
 wrz91win |
100 | 0.469 s | 58.72 MiB | C++ |
 xtommy |
100 | 0.526 s | 59.16 MiB | C++ |
 FoolMike |
100 | 0.628 s | 120.56 MiB | C++ |
 Youngsc |
100 | 0.859 s | 48.09 MiB | C++ |
 『』 |
100 | 1.279 s | 37.10 MiB | C++ |
 胡嘉兴 |
100 | 1.492 s | 157.67 MiB | C++ |
 __ |
100 | 1.691 s | 81.25 MiB | C++ |
 Cydiater |
100 | 2.854 s | 40.46 MiB | C++ |
| 本题关联比赛 | |||
| HAOI 2017 | |||
| 关于 供给侧改革 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
COGS标签有BUG。。。添加一个标签，自动变成其他的鬼畜标签了。。。
| ||||
|
HAOI2017的坑终于填完……
感谢syq神犇的代码，感谢ccz神犇的教诲 FoolMike
2017-07-04 12:09
4楼
| ||||
|
考场上写的SA+set，被卡常，换treap，依旧被卡，我大概就是这么一步步退役的
| ||||
|
回复 @FoolMike :
考场上意识模糊..或者说字符串那一套理论学傻什么的 Cydiater
2017-05-03 18:59
2楼
| ||||
|
FoolMike
2017-05-03 18:27
1楼
| ||||
【题目描述】
Anihc国提高社会生产力水平，落实好以人民为中心的发展思想。决定进行供给侧结构性改革。
为了提高供给品质，你调查乐某个产业近来n个时期的供求关系平衡情况，每个时期的情况用0或1中的一个数字表示，于是这就是一个长度为n的01字符串S。为了更好的了解这一些数据，你需要解决一些询问，我们令data(l,r)表示：在字符串S中，起始位置在[l,r]之间的这些后缀之中，具有最长公共前缀的长度。
对于每一个询问L,R，求$$ans=\sum_{L\leq i<R}data(i,R)$$
由于你其实根本没时间调查，所以这些数据都是乱编的，即串S中的每一位都是在0和1之间随机产生的。
【输入格式】
第一行2个整数n,Q，表示字符串的长度，以及询问个数。
接下来一行长度为n的一个01串S。
接下来Q行，每行两个整数L,R，表示一个询问[L,R]。
【输出格式】
共Q行，每行一个整数，表示对应询问的答案。
【样例输入】
6 3 010110 2 5 1 6 1 2
【样例输出】
4 6 0
【数据规模与约定】
【来源】
2017河南省选上午t2