Parenthesis
Problem Description:
Bobo has a balanced parenthesis sequence P=p1 p2…pn of length n and q questions.
The i-th question is whether P remains balanced after pai and pbi swapped. Note that questions are individual so that they have no affect on others.
Parenthesis sequence S is balanced if and only if:
S is empty;
or there exists balanced parenthesis sequence A,B such that S=AB;
or there exists balanced parenthesis sequence S' such that S=(S').
Input:
The input contains at most 30 sets. For each set:
The first line contains two integers n,q (2≤n≤105,1≤q≤105).
The second line contains n characters p1 p2…pn.
The i-th of the last q lines contains 2 integers ai,bi (1≤ai,bi≤n,ai≠bi).
Output:
For each question, output "Yes" if P remains balanced, or "No" otherwise.
Sample Input:
4 2
(())
1 3
2 3
2 1
()
1 2
Sample Output:
No
Yes
No
【题目链接】CSU 1809 Parenthesis
【题目类型】线段树+前缀和
&题意:
给了一个平衡的括号序列s(平衡是指括号匹配正常)现在q次询问,每次输入两个数a、b;问将s[a]和s[b]交换后是否仍然平衡(即是否正常匹配)平衡则输出“Yes”,否则输出“No”
&题解:
这种括号的题目有一种经典的套路就是遇到'('加一,遇到')'减一,这样整个序列最后的前缀和一定是非负的,同样的这里贪心一下就会发现只有把'(' 和')'交换的时候才会出问题,这时我们就要想一下了,有了括号的套路,你只给一个数组赋值正负一是没什么意义的,所以你要求他的前缀和,放在pre数组中,这样假设每次修改的区间是u,v,也就是只有当s[u] == '(' && s[v] == ')'才需要判断,且u<=v,那么要判断什么呢?你想,正确情况下他的pre是不会有<0的情况的,但如果换了之后,前面u的位置换成了'('就要减1,后面v的位置是加1的,所以不用管,这时候pre在区间[u,v-1]的最小值>=2才可以。
【时间复杂度】O(nlogn)
&代码:
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
#define SII(N,M) scanf("%d %d",&(N),&(M))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 100000 + 5 ;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[MAXN << 2], pre[MAXN];
inline void Pushmin(int rt) {
sum[rt] = min(sum[rt << 1], sum[rt << 1 | 1]);
}
void Build(int l, int r, int rt) {
if (l == r) {
sum[rt] = pre[l];
return;
}
int m = (l + r) >> 1;
Build(lson);
Build(rson);
Pushmin(rt);
}
int Query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
int m = (l + r) >> 1;
int ans = INF;
if (L <= m)
ans = min(ans, Query(L, R, lson));
if (R > m)
ans = min(ans, Query(L, R, rson));
return ans;
}
int n, q;
char s[MAXN];
void Solve() {
while (~SII(n, q)) {
scanf("%s", s + 1);
rez(i, 1, n) if (s[i] == '(') pre[i] = pre[i - 1] + 1;
else pre[i] = pre[i - 1] - 1;
Build(1, n, 1);
rep(i, q) {
int u, v;
SII(u, v);
if (v < u) swap(u, v);
if (s[u] == '(' && s[v] == ')') {
int d = Query(u, v - 1, 1, n, 1);
if (d < 2) puts("No");
else puts("Yes");
}
else puts("Yes");
}
}
}
int main() {
Solve();
return 0;
}
CSU 1809 Parenthesis(线段树+前缀和)的更多相关文章
-
湖南省2016省赛题。1809: Parenthesis 线段树
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1809 给定一串平衡的序列,要求交换两个位置之后,问其是否还平衡. 首先要注意到交换的是两个位置,这 ...
-
HDU 5172 GTY&#39;s gay friends 线段树+前缀和+全排列
题目链接: hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5172 bc(中文):http://bestcoder.hdu.edu.cn/contest ...
-
CSU 1809 - Parenthesis - [前缀和+维护区间最小值][线段树/RMQ]
题目链接:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1809 Bobo has a balanced parenthesis sequenc ...
-
CSU 1809 Parenthesis 思维+线段树
1809: Parenthesis Submit Page Summary Time Limit: 5 Sec Memory Limit: 128 Mb Submitte ...
-
【贪心】CSU 1809 Parenthesis (2016湖南省第十二届大学生计算机程序设计竞赛)
题目链接: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1809 题目大意: 给一个长度为N(N<=105)的合法括号序列.Q(Q<= ...
-
CSU 1809 Parenthesis(RMQ-ST+思考)
1809: Parenthesis Submit Description Bobo has a balanced parenthesis sequence P=p1 p2…pn of length n ...
-
csu 1809 Parenthesis
题目见此 分析,把'('当成1, ')'当成-1, 计算前缀和sum. 记交换括号左边的序号为u, 右边为v,讨论左右括号: 1.s[u] == '(' && s[v] == ')' ...
-
【BZOJ】1651: [Usaco2006 Feb]Stall Reservations 专用牛棚(线段树/前缀和 + 差分)
http://www.lydsy.com/JudgeOnline/problem.php?id=1651 很奇妙.. 我们发现,每一时刻的重叠数选最大的就是答案.... orz 那么我们可以线段树维护 ...
-
【vijos】1750 建房子(线段树套线段树+前缀和)
https://vijos.org/p/1750 是不是我想复杂了.... 自己yy了个二维线段树,然后愉快的敲打. 但是wa了两法.......sad 原因是在处理第二维的更新出现了个小问题,sad ...
随机推荐
-
一些常用的git指令
PyCharm编辑器 如何切换分支 git branch 查看当前在哪个分支,也会显示本地所有的分支名 git branch dev-chenqiao 新建分支 git checkout dev-ch ...
-
9款一键快速搭建PHP运行环境的好工具
9款一键快速搭建PHP运行环境的好工具 胡倡萌 2011/02/19 网络资源 77,063 1 内容提要: 建立一个PHP网站,首先需要搭建PHP的开发和运行环境,对于PHP初学者也是一个难 ...
-
关于PetaPoco的T4模板使用
PetaPoco是一款适用于.Net 和Mono的微小.快速.单文件的微型ORM.PetaPoco介绍:http://www.cnblogs.com/youring2/archive/2012/06/ ...
-
(转)RabbitMQ消息队列(三):任务分发机制
在上篇文章中,我们解决了从发送端(Producer)向接收端(Consumer)发送“Hello World”的问题.在实际的应用场景中,这是远远不够的.从本篇文章开始,我们将结合更加实际的应用场景来 ...
-
使用SpringMVC+mybatis+事务控制+JSON 配置最简单WEB
最近在总结一些项目的基础知识,根据公司最近的一些意向和技术路线,初步整理了一个简单的配置例子 1.使用springmvc代替strutsMVC 2.使用请求json数据串的方式代替传统 ...
-
writeToFile 读写文件问题
关于 writeToFile 读写文件:当字典中键值对以 Model(例如:studentModel)为值时发现 Dictionary 调用 writeToFile 方法无法生成 plist 文件,经 ...
-
smarty练习:数据的增删改
根据数据库中的三张表格:timu,xuanxiang,kemu来进行数据的增删改查,并且使用smarty模版将前端与后台分离开来 三张表格: 主页面后台 main.php: <?php //引入 ...
-
powerdesigner反向MySQL5.1数据库 生成ER图
我用的powerdesigner是15.1版本,数据库是MySQL5.1.57 (1)首先新建一个“PhysicalDataModel”类型的文件,然后点击“Database”->"C ...
-
index_init_oprions.go
{ options.DocCacheSize = defaultDocCacheSize } }
-
WPF自定义控件的自定义属性绑定后不更新问题
原文:WPF自定义控件的自定义属性绑定后不更新问题 需要在绑定时设置属性变更触发 UpdateSourceTrigger=PropertyChanged 例如: <Border CornerRa ...