#P6782. [2019备战noi]befuddle

    ID: 6602 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理滑动窗口离线与分治离线查询查询排序数据结构懒标记线段树CF2400

[2019备战noi]befuddle

Befuddle

题目描述

给定一个由小写英文字母组成、长度为 nn 的字符串 ss,下标从 11 到 nn。

有 mm 个询问,每个询问包含五个整数 X,A,B,L,RX,A,B,L,R。请找出一个子串 s[i,j]s_{[i,j]},满足:

  • L≤i≤j≤RL\le i\le j\le R,即整个子串位于指定区间内。
  • A≤j−i+1≤BA\le j-i+1\le B。
  • 子串中恰好有 XX 种不同的字符。

如果有多组满足条件的 (i,j)(i,j),首先选择 ii 最小的;如果仍有多组,再选择 jj 最小的。若无解,输出 -1 -1。

输入格式

第一行一个字符串 ss。

第二行一个正整数 mm,表示询问数。

接下来 mm 行,每行五个整数 X,A,B,L,RX,A,B,L,R,描述一个询问。

输出格式

每个询问输出一行两个整数 i,ji,j。无解时输出两个整数 -1 -1。

样例输入

abcc
3
2 1 3 1 4
2 3 3 1 4
1 2 2 1 3

样例输出

1 2
2 4
-1 -1

数据范围与子任务

所有数据满足 1≤n,m≤1051\le n,m\le10^5,1≤L≤R≤n1\le L\le R\le n,1≤A≤B≤n1\le A\le B\le n,1≤X≤261\le X\le26。

子任务 分值 附加限制
1 66 n≤100n\le100
2 99 n≤1000n\le1000
3 1717 A=1A=1,B=nB=n
4 L=1L=1,R=nR=n
5 所有询问的 XX 都相等
6 3434 无