题解 P3215 【[HNOI2011]括号修复 / [JSOI2011]括号序列】
ChthollyTree
2019-02-04 22:56:40
既然有区间推平操作，自然就想到珂朵莉树了
之后几个操作就可以暴力维护了
就是Query操作说一下做法
我的做法是：求出 设 ( 为 1， ) 为-1
求出这个区间的前缀和
如果某个地方的前缀和小于 0 （设为S）则说明此时前面的 ')'数量多于 '(' 数量，无法匹配，此时则需要修改
修改 $\frac{-s}{2}$(上取整)个括号
同时修改前缀和（s为奇数改为1，否则为0）
最后的 若 前缀和 > 0 表示 '(' 较多,无法匹配
则还需要修改$\frac{s}{2}$个括号
```
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define se set<aa>
#define it iterator
int n,m;
int a[MAXN];
char ch[MAXN];
struct aa
{
int l,r,v;
};
bool operator <(aa a,aa b) {
return a.r < b.r;
}
set<aa>s;
void wt()
{
for(se::it i = s.begin(); i != s.end(); i ++)
{
cout<<(i->l)<<" "<<(i->r)<<" "<<(i->v)<<"\n";
}
}
int zh(char a)
{
if(a == '(') return 1;
else return -1;
}
void splix(se::it a,int i) {
if(i < a->l) return;
if(a->r < i+1) return;
int sl = a->l,sr = a->r,sv = a->v;
s.erase(a);
s.insert((aa){sl,i,sv});
s.insert((aa){i+1,sr,sv});
}
void fen(int l,int r)
{
se::it x = s.lower_bound((aa){0,l,0});
splix(x,l-1);
se::it y = s.lower_bound((aa){0,r,0});
splix(y,r);
}
void tuiping(int l,int r,int v)
{
fen(l,r);
se::it x = s.lower_bound((aa){0,l,0});
se::it y = s.lower_bound((aa){0,r,0});
y ++;
s.erase(x,y);
s.insert((aa){l,r,v});
}
aa c[MAXN];
int nn;
void tiqu(int l,int r)
{
fen(l,r);
se::it x = s.lower_bound((aa){0,l,0});
se::it y = s.lower_bound((aa){0,r,0});
nn = 0;
for(se::it i = x; 1 == 1; i ++) {
nn ++;
c[nn] = (*i);
// cout<<nn<<":"<<c[nn].l<<" "<<c[nn].r<<" "<<c[nn].v<<"\n";
if(i == y) break;
}
}
void Swap(int l,int r)
{
fen(l,r);
tiqu(l,r);
se::it x = s.lower_bound((aa){0,l,0});
se::it y = s.lower_bound((aa){0,r,0});
y ++;
s.erase(x,y);
for(int i = 1; i <= nn; i ++) {
s.insert((aa){r - (c[i].r - c[i].l),r,c[i].v});
r -= (c[i].r - c[i].l)+1;
// cout<<r<<"\n";
}
}
void Invert(int l,int r) {
fen(l,r);
tiqu(l,r);
se::it x = s.lower_bound((aa){0,l,0});
se::it y = s.lower_bound((aa){0,r,0});
y ++;
s.erase(x,y);
for(int i = 1; i <= nn; i ++) {
s.insert((aa){c[i].l,c[i].r,-c[i].v});
}
}
void qiu(int l,int r)
{
fen(l,r);
tiqu(l,r);
int ans = 0,s = 0;
for(int i = 1; i <= nn; i ++)
{
s += (c[i].r - c[i].l + 1)*c[i].v;
if(s < 0)
{
ans += (-s)>>1;
if((-s)&1)
{
s = 1;
ans ++;
}
else s = 0;
}
}
ans += abs(s)>>1;
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",ch+1);
for(int i = 1; i <= n; i ++) {
if(ch[i] == '(' )
{
a[i] = 1;
s.insert((aa){i,i,a[i]});
}else {
a[i] = -1;
s.insert((aa){i,i,a[i]});
}
}
// wt();
for(int i = 1; i <= m; i ++)
{
string opt;
cin >> opt;
if(opt == "Replace")
{
int l,r;
scanf("%d%d",&l,&r);
string ot;
cin >> ot;
tuiping(l,r,zh(ot[0]));
}
if(opt == "Query")
{
int l,r;
scanf("%d%d",&l,&r);
qiu(l,r);
}
if(opt == "Swap")
{
int l,r;
scanf("%d%d",&l,&r);
Swap(l,r);
}
if(opt == "Invert")
{
int l,r;
scanf("%d%d",&l,&r);
Invert(l,r);
}
}
return 0;
}
```