首页 > 代码库 > BZOJ 2329: [HNOI2011]括号修复 [splay 括号]
BZOJ 2329: [HNOI2011]括号修复 [splay 括号]
题目描述
一个合法的括号序列是这样定义的：
空串是合法的。
如果字符串 S 是合法的，则(S)也是合法的。
- 如果字符串 A 和 B 是合法的，则 AB 也是合法的。
现在给你一个长度为 N 的由‘(‘和‘)‘组成的字符串，位置标号从 1 到 N。对这个字符串有下列四种操作：
Replace a b c：将[a,b]之间的所有括号改成 c。例如：假设原来的字符串为：))())())(，那么执行操作 Replace 2 7 ( 后原来的字符串变为：)(((((()(。
Swap a b：将[a,b]之间的字符串翻转。例如：假设原来的字符串为：))())())(，那么执行操作 Swap 3 5 后原来的字符串变为：))))(())(。
Invert a b：将[a,b]之间的‘(’变成‘)’,‘)’变成‘(’。例如：假设原来的字符串为：))())())(，那么执行操作 Invert 4 8 后原来的字符串变为：))((()(((。
- Query a b：询问[a,b]之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的‘(’变成‘)’或‘)’变成‘(’。注意执行操作 Query 并不改变当前的括号序列。例如：假设原来的字符串为：))())())(，那么执行操作 Query 3 6
的结果为 2，因为要将位置 5 的‘)’变成‘(’并将位置 6 的‘(’变成‘)’。
输入输出格式
输入格式：
从文件input.txt中读入数据，输入文件的第一行是用空格隔开的两个正整数N和M，分别表示字符串的长度和将执行的操作个数。第二行是长度为N的初始字符串S。接下来的M行是将依次执行的M个操作，其中操作名与操作数之间以及相邻操作数之间均用空格隔开。30%的数据满足
N,M≤3000。100%的数据满足N,M≤100000。
输出格式：
输出文件 output.txt 包含 T 行，其中 T 是输入的将执行的 M 个操作中 Query 操作出现的次数。Query 操作的每次出现依次对应输出文件中的一行，该行只有一个非负整数，表示执行对应 Query 操作的结果，即：所指字符串至少要改变多少位才能变成合法的括号序列。输入数据
保证问题有解。
输入输出样例
输入样例#1：
4 5((((Replace 1 2 )Query 1 2Swap 2 3Invert 3 4Query 1 4
输出样例#1：
12
说明
样例解释：输入中有2个Query操作，所以输出有2行。执行第一个Query操作时的括号序列为))((，因改变第1位可使[1,2]之间的字符串变成合法的括号序列，故输出的第一行为1。执行第二个Query操作时的括号序列为)((),因要改变第1位和第2位才能使[1,4]之间的字符串变成合法的括号序列，故输出的第二行为2。
去luogu偷题面
多了区间修改操作..................
区间修改后要把反转翻转标记清空
反转标记需要反转修改标记
PS：luogu时限不科学，要强开O2才过
#pragma GCC optimize(2)
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;#define lc t[x].ch[0]#define rc t[x].ch[1]#define pa t[x].faconst int N=1e5+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,Q,l,r,a[N];char s[N],op[20];struct node{ int ch[2],fa,size,v,sum,lmx,lmn,rmx,rmn,rev,flp,tag; node():fa(0){ch[0]=ch[1]=0;}}t[N];int root;inline int wh(int x){return t[pa].ch[1]==x;}inline void update(int x){ if(!x) return; t[x].size=t[lc].size+t[rc].size+1; t[x].sum=t[lc].sum+t[rc].sum+t[x].v; t[x].lmx=max(t[lc].lmx,max(t[lc].sum+t[x].v,t[lc].sum+t[x].v+t[rc].lmx)); t[x].lmn=min(t[lc].lmn,min(t[lc].sum+t[x].v,t[lc].sum+t[x].v+t[rc].lmn)); t[x].rmx=max(t[rc].rmx,max(t[rc].sum+t[x].v,t[rc].sum+t[x].v+t[lc].rmx)); t[x].rmn=min(t[rc].rmn,min(t[rc].sum+t[x].v,t[rc].sum+t[x].v+t[lc].rmn));}inline void rever(int x){ t[x].rev^=1; swap(lc,rc); swap(t[x].lmx,t[x].rmx); swap(t[x].lmn,t[x].rmn);}inline void flip(int x){ t[x].flp^=1; t[x].sum=-t[x].sum;t[x].v=-t[x].v; t[x].lmx=-t[x].lmx;t[x].lmn=-t[x].lmn; swap(t[x].lmx,t[x].lmn); t[x].rmx=-t[x].rmx;t[x].rmn=-t[x].rmn; swap(t[x].rmx,t[x].rmn); t[x].tag=-t[x].tag;}inline void paint(int x,int d){ t[x].rev=t[x].flp=0; t[x].v=t[x].tag=d;t[x].sum=t[x].size*d; t[x].lmx=t[x].rmx=max(d,t[x].sum); t[x].lmn=t[x].rmn=min(d,t[x].sum);}inline void pushDown(int x){ if(t[x].rev){ if(lc) rever(lc); if(rc) rever(rc); t[x].rev=0; } if(t[x].flp){ if(lc) flip(lc); if(rc) flip(rc); t[x].flp=0; } if(t[x].tag){ if(lc) paint(lc,t[x].tag); if(rc) paint(rc,t[x].tag); t[x].tag=0; }}inline void rotate(int x){ int f=t[x].fa,g=t[f].fa,c=wh(x); if(g) t[g].ch[wh(f)]=x;t[x].fa=g; t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f; t[x].ch[c^1]=f;t[f].fa=x; update(f);update(x);}inline void splay(int x,int tar){ for(;pa!=tar;rotate(x)) if(t[pa].fa!=tar) rotate(wh(x)==wh(pa)?pa:x); if(tar==0) root=x;}int build(int l,int r,int f){//printf("build %d %d %d\n",l,r,f); if(l>r) return 0; int x=(l+r)>>1; lc=build(l,x-1,x);rc=build(x+1,r,x); t[x].fa=f; t[x].rev=t[x].flp=t[x].tag=0; t[x].v=a[x];//not need update(x);//printf("get %d %d %d %d %d %d %d %d %d\n",x,l,r,t[x].v,t[x].sum,t[x].lmx,t[x].lmn,t[x].rmx,t[x].rmn); return x;}inline int kth(int k){//printf("kth %d\n",k); int x=root,ls=0; while(x){ pushDown(x); int _=ls+t[lc].size;//printf("size %d %d\n",x,_); if(_<k&&k<=_+1) return x; else if(k<=_) x=lc; else ls=_+1,x=rc; } return 0;}void Query(int l,int r){//printf("query %d %d\n",l,r); int f=kth(l);splay(f,0); int x=kth(r+2);splay(x,f); int a=t[lc].lmx,b=t[lc].rmn;//printf("hi %d %d %d %d %d\n",f,x,lc,a,b); printf("%d\n",(a+1)/2+(-b+1)/2);}void Flip(int l,int r){ int f=kth(l);splay(f,0); int x=kth(r+2);splay(x,f); flip(lc);update(x);update(f);}void Rever(int l,int r){ int f=kth(l);splay(f,0); int x=kth(r+2);splay(x,f); rever(lc);update(x);update(f);}void Cover(int l,int r){ char c[2];scanf("%s",c); int d= c[0]==‘(‘?-1:1; int f=kth(l);splay(f,0); int x=kth(r+2);splay(x,f); paint(lc,d);update(x);update(f);}void print(int x){ pushDown(x); if(lc) print(lc); printf("%c ",t[x].v==-1?‘(‘:‘)‘); if(rc) print(rc);}int main(){ //freopen("in.txt","r",stdin); n=read();Q=read(); scanf("%s",s+1); for(int i=1;i<=n;i++) a[i+1]=s[i]==‘(‘?-1:1; //for(int i=1;i<=n+2;i++) printf("%d ",a[i]);puts(""); t[0].lmn=t[0].rmn=INF; t[0].lmx=t[0].rmx=-INF; root=build(1,n+2,root); while(Q--){//print(root);puts(" end"); scanf("%s",op);l=read();r=read(); if(op[0]==‘R‘) Cover(l,r); if(op[0]==‘S‘) Rever(l,r); if(op[0]==‘I‘) Flip(l,r); if(op[0]==‘Q‘) Query(l,r); }}
BZOJ 2329: [HNOI2011]括号修复 [splay 括号]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。