#1901. Metropolis

    ID: 1901 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1960来源:qoj.ac数据:公开样例字符串差分树状数组

Metropolis

Metropolis

题目描述

标题: Metropolis - Problem - QOJ.ac

Statistics

对于一个由左括号 ( 和右括号 ) 构成的字符串,我们称它是匹配括号串,当且仅当其中左右括号数量相等,且存在一种将左右括号一一匹配的方案,使得任何匹配中左括号在右括号前面,且任何两对匹配对应的区间要么不相交,要么有包含关系。

对于两个匹配括号串 X,Y,我们称 X 能生成 Y 当且仅当可以从 X 中删除若干对(可以为 0 对)匹配的括号对得到 Y。

给定长度为 n 的匹配括号串 A 和长度为 m 的匹配括号串 B,有 q 次询问,每次询问给定 l1,r1,l2,r2,求 A[l1,r1] 能否生成 B[l2,r2],保证这两个子串都是匹配括号串。

输入格式

从标准输入读入数据。

第一行:三个整数 n,m,q。

第二行:一个长度为 n 的字符串 A。

第三行:一个长度为 m 的字符串 B。

接下来 q 行:每行四个整数 l1,r1,l2,r2,描述一个询问。

输出格式

输出到标准输出。

输出共 q 行:若答案为肯定,输出 YES;若答案为否定,输出 NO。

样例

输入

8 8 8
(()())()
(())()()
1 6 1 4
1 6 1 6
1 6 5 8
2 5 1 4
2 5 5 8
7 8 7 8
1 8 1 8
1 8 1 6

输出

YES
NO
YES
NO
YES
YES
NO
YES

子任务

对于全部数据:1≤n,m,q≤12000, 1≤l1<r1≤n, 1≤l2<r2≤m,保证 A,B 以及每次询问的子串都是匹配括号串。

Subtask 1(15%):n,m≤30。

Subtask 2(20%):n,m≤100。

Subtask 3(15%):n,m≤600。

Subtask 4(20%):n,m≤4000。

Subtask 5(30%):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

8 8 8
(()())()
(())()()
1 6 1 4
1 6 1 6
1 6 5 8
2 5 1 4
2 5 5 8
7 8 7 8
1 8 1 8
1 8 1 6
YES
NO
YES
NO
YES
YES
NO
YES