2122: 智慧爷的蛋糕

题目描述


智慧爷有很多蛋糕,蛋糕排成一排,蛋糕类型有26种,类型为从 a-z; 有一天,智慧爷吃撑了,他突然看到有一段蛋糕和另一段蛋糕长的一样。这个时候,智慧爷开始头晕了,智慧爷的眩晕度表示 从位置 a-b ,c-d两段前面有多少个蛋糕一模一样,就是 位置a,c的蛋糕类型一样,智慧爷的眩晕度就加一 然后a+1,c+1,a+2,c+2…一直相同智慧爷的眩晕度就加一,不一样智慧爷就醒了。智慧爷醒了后,,想知道自己最大的眩晕度。由于智慧爷眩晕了,于是这个问题就交给你了

输入


一个数n 表示字符串的长度 ,蛋糕的长度 n<=2e5
字符串
一个数q 表示q次查询 q<=2e5
下面 q行 每行四个整数 a,b,c,d; a<=b ,c<=d ,0<=a,b,c,d

输出


每次查询智慧爷的最大眩晕度

样例输入


10
bdcabaccca
3
5 5 1 7
1 1 2 5
6 7 1 4

样例输出


0
0
0

提示


浙江理工大学月赛2019年5月

来源/分类


浙江理工大学月赛

请先 登录 后评论
  • 0 关注
  • 0 收藏,549 浏览
  • 轩爸 提出于 2019-08-02 22:38

相似问题