注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2329][HNOI2011]括号修复  

2014-11-28 15:59:32|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
卧槽我代码能力实在是太弱了
调了n久
题目有两个地方比较坑:
1.默认询问的区间长度一定是2的倍数
2.第一个数据里混了一些tab进去……读入挂没判的话会wa = =、
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
const int P = N;
int n,m,T,data[N];
struct Node{
Node();
int cot[2],ln[2],rn[2];
short d,rev,rep,back;
Node *ch[2],*fa;
short pl(){return this==fa->ch[1];}
int size(){return cot[0]+cot[1];}
void count(){
cot[0] = ch[0]->cot[0] + ch[1]->cot[0];
cot[1] = ch[0]->cot[1] + ch[1]->cot[1];
cot[d] += 1;
ln[0] = ch[0]->ln[0];
ln[0] = max(ln[0],ch[0]->cot[0] - ch[0]->cot[1] + (d?-1:1) + ch[1]->ln[0]);
ln[1] = ch[0]->ln[1];
ln[1] = max(ln[1],ch[0]->cot[1] - ch[0]->cot[0] + (d?1:-1) + ch[1]->ln[1]);
rn[0] = ch[1]->rn[0];
rn[0] = max(rn[0],ch[1]->cot[0] - ch[1]->cot[1] + (d?-1:1) + ch[0]->rn[0]);
rn[1] = ch[1]->rn[1];
rn[1] = max(rn[1],ch[1]->cot[1] - ch[1]->cot[0] + (d?1:-1) + ch[0]->rn[1]);
// if(!ch[0]->cot[d^1])ln[d] += ch[1]->ln[d]+1;
// if(!ch[1]->cot[d^1])rn[d] += ch[0]->rn[d]+1;
}
void replace(short);
void Inv();
void reverse();
void push(){
if(rev){
ch[0]->reverse();
ch[1]->reverse();
rev=0;
}
if(back){
ch[0]->Inv();
ch[1]->Inv();
back=0;
}
if(rep > -1){
ch[0]->replace(rep);
ch[1]->replace(rep);
rep=-1;
}
}

}house[N],*null;int hn;
void Node::reverse(){
if(this == null)return;
swap(ch[0],ch[1]);
swap(ln[0],rn[0]);
swap(ln[1],rn[1]);
rev^=1;
}
void Node::replace(short val){
if(this == null)return;
d = rep = val;//*
ln[val] = rn[val] = cot[val] = cot[0]+cot[1];
val^=1;
ln[val] = rn[val] = cot[val] = 0;
}
void Node::Inv(){
if(this == null)return;
back^=1;
swap(cot[0],cot[1]);
d ^= 1;
if(rep>-1)rep^=1;//!!
swap(ln[0],ln[1]);
swap(rn[0],rn[1]);
}
Node *newNode(){
if(hn<N){house[hn]=Node();return &house[hn++];}
return new Node;
}
Node::Node(){ch[0]=ch[1]=fa=null;cot[0]=cot[1]=rev=back=0;rep=-1;
memset(ln,0,sizeof(ln));memset(rn,0,sizeof(rn));}
struct Splay{
Node *ROOT;
Splay(){
null = newNode();
*null=Node();
}
void Start(){
ROOT=newNode();
ROOT->ch[1] = newNode();
ROOT->ch[1]->fa = ROOT;
ROOT->ch[1]->ch[0] = Build();
ROOT->ch[1]->ch[0]->fa = ROOT->ch[1];
ROOT->d = ROOT->ch[1]->d = 0;
ROOT->ch[1]->count();
ROOT->count();
}
Node *Build(int l=1, int r=n){
if(l>r)return null;
Node *re = newNode();
int mid = (l+r)/2;
if(l<r){
re->ch[0] = Build(l,mid-1);
re->ch[1] = Build(mid+1,r);
if(re->ch[0]!=null)re->ch[0]->fa = re;
if(re->ch[1]!=null)re->ch[1]->fa = re;
}
//re->ln[data[l]] = re->rn[data[l]] =1;
re->d = data[mid];
re->count();
return re;
}
void rotate(Node *k){
Node *r = k->fa;if(r==null||k==null)return;
//if(r->fa!=null)r->fa->push();
r->push();k->push();//???¨????x?°????
int x = k->pl()^1;
r->ch[x^1] = k->ch[x];
r->ch[x^1]->fa = r;
if(r->fa!=null)r->fa->ch[r->pl()]=k;
else ROOT = k;
k->fa = r->fa;k->ch[x]=r;
r->fa = k;
r->count();k->count();
}
void splay(Node *r,Node *tar=null){
for(;r->fa!=tar;rotate(r))
if(r->fa->fa!=tar)rotate(r->pl()==r->fa->pl()?r->fa:r);
}
Node *find(int k){
Node *r = ROOT;
while(r!=null){
r->push();//*
int tmp = r->ch[0]->size();
if(tmp >= k)r = r->ch[0];
else if(tmp+1 >= k)return r;
else r = r->ch[1],k-=tmp+1;
}
}
void pack(int a,int b){
b += 2;
//printf("Pack %d %d\n",a,b);
Node *r = find(a);
splay(r);
//printf("Pack1\n");
r = find(b);
// printf("%d",r->size());
// printf("Pack2\n");
splay(r,ROOT);
// printf("Pack end\n");
}
void Set(int a,int b,int c){
pack(a,b);
// printf("Set\n");
//ROOT->ch[1]->ch[0]->push();
ROOT->ch[1]->ch[0]->replace(c);
}
void Invert(int a,int b){
pack(a,b);
//ROOT->ch[1]->ch[0]->push();
ROOT->ch[1]->ch[0]->Inv();
}
void Swap(int a,int b){
pack(a,b);
//ROOT->ch[1]->ch[0]->push();
ROOT->ch[1]->ch[0]->reverse();
}
int Ask(int a, int b){
pack(a,b);
ROOT->ch[1]->ch[0]->push();
Node r = *ROOT->ch[1]->ch[0];
a = r.rn[0]/2 + r.ln[1]/2;
if(r.rn[0]&1)a+=2;
return a;
}

}St;
void print(Node *r = St.ROOT,short tab=0){
int i;
for(i=1;i<=tab;i++)printf("| ");
printf("Cot:%d %d\n",r->cot[0],r->cot[1]);
for(i=1;i<=tab;i++)printf("| ");
printf("Ln:%d %d\n",r->ln[0],r->ln[1]);
for(i=1;i<=tab;i++)printf("| ");
printf("Ln:%d %d\n",r->rn[0],r->rn[1]);
for(i=1;i<=tab;i++)printf("| ");
printf("F: %s %s %d\n",(r->rev?"[rev]":" rev "),(r->back?"[back]":" back "),r->rep);
for(i=1;i<=tab;i++)printf("| ");printf("ch[0]:\n");
if(r->ch[0]!=null)print(r->ch[0],tab+1);
for(i=1;i<=tab;i++)printf("| ");printf("ch[1]:\n");
if(r->ch[1]!=null)print(r->ch[1],tab+1);
}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;char cc;
n = scan();m = scan();
for(i=1;i<=n;i++){
cc=' ';while(cc==' '||cc=='\r'||cc=='\n'||cc==9)cc=getchar();
if(cc=='(')data[i]=0;
else data[i]=1;
}
//for(i=1;i<=n;i++)printf("%d ",data[i]);
St.Start();
char str[10];
//printf("%d\n",St.ROOT->size());
//printf("%d\n",null->cot[1]);
for(i=1;i<=m;i++){
scanf("%s",str);
//printf("%s\n",str);
//print();
switch(str[0]){
case'R':{
a = scan();b = scan();
cc=' ';while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
St.Set(a,b,cc==')');
break;
}
case'Q':{
a = scan();b = scan();
a = St.Ask(a,b);
printf("%d\n",a);
break;
}
case'S':{
a = scan();b = scan();
St.Swap(a,b);
break;
}
case'I':{
a = scan();b = scan();
St.Invert(a,b);
break;
}
}
}
return 0;
}

题解:
splay维护序列
对于一个区间(l,r)删掉所有已经匹配的括号,可以得到形如“)))(((”这样的东西,分别维护一下长度就行了。
然后答案=左长/2+右长/2,如果有一个长度是奇数就ans+2
注意:
一开始以为可以用线段树做……写了1h后删掉了QuQ
这个题真正蛋疼的地方是要维护三个标记,打一个标记的时候容易忘记改它会影响的标记……
然后我还因为运算优先级挂了一次……
  评论这张
 
阅读(155)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017