BZOJ 1493 NOI 2007 목걸이 공장 밸 런 스 트 리
경계 처리, 환상 처리 가 완전히 구역질 이 나 서 이미 치 료 를 포기 했다
저 는 그냥 귀여운 코드 짐꾼 입 니 다.......................................................................
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*WDZRMPCBIT begin
typedef struct NODE{
int c,v,s,lc,rc;
bool same,rev;
NODE *f,*child[2];
NODE(){}
NODE(int _v,NODE *_f):v(_v),lc(_v),rc(_v),f(_f){}
} *TREE;
TREE root,Null;
int N,Q,C,a[MAXN];
char s[6+2];
TREE NewNode(int v,TREE f){
TREE x=new NODE(v,f);
x->c=x->s=1;
x->same=x->rev=0;
x->child[0]=x->child[1]=Null;
return x;
}
void Pushup(TREE x){
if(x==Null) return;
x->c=x->child[0]->c+x->child[1]->c+1;
x->lc=x->rc=x->v;
if(x->child[0]!=Null) x->lc=x->child[0]->lc;
if(x->child[1]!=Null) x->rc=x->child[1]->rc;
x->s=x->child[0]->s+x->child[1]->s;
if(x->child[0]!=Null && x->v==x->child[0]->rc) x->s--;
if(x->child[1]!=Null && x->v==x->child[1]->lc) x->s--;
}
void Pushdown(TREE x){
if(x==Null) return;
if(x->rev){
x->child[0]->rev^=1,x->child[1]->rev^=1,x->rev=0;
if(x->child[0]!=Null){
swap(x->child[0]->child[0],x->child[0]->child[1]);
swap(x->child[0]->lc,x->child[0]->rc);
}
if(x->child[1]!=Null){
swap(x->child[1]->child[0],x->child[1]->child[1]);
swap(x->child[1]->lc,x->child[1]->rc);
}
}
if(x->same){
x->same=0;
if(x->child[0]!=Null){
x->child[0]->same=1,x->child[0]->v=x->v,x->child[0]->c=1;
x->child[0]->lc=x->child[0]->rc=x->v;
}
if(x->child[1]!=Null){
x->child[1]->same=1,x->child[1]->v=x->v,x->child[1]->c=1;
x->child[1]->lc=x->child[1]->rc=x->v;
}
}
}
void Initialise(){
Null=NewNode(0,0),Null->c=0;
root=NewNode(0,Null);
root->child[1]=NewNode(0,root);
Null->s=root->s=root->child[1]->s=0;
}
void Rotate(TREE x,bool t){
TREE y=x->f;
Pushdown(x->child[0]),Pushdown(x->child[1]),Pushdown(y->child[t]);
y->child[!t]=x->child[t],x->child[t]->f=y,x->f=y->f;
if(y->f->child[0]==y) y->f->child[0]=x;
else y->f->child[1]=x;
y->f=x,x->child[t]=y;
Pushup(y),Pushup(x);
if(root==y) root=x;
}
void Splay(TREE x,TREE y){
Pushdown(x);
while(x->f!=y)
if(x->f->f==y)
if(x->f->child[0]==x) Rotate(x,1);
else Rotate(x,0);
else if(x->f->f->child[0]==x->f)
if(x->f->child[0]==x) Rotate(x->f,1),Rotate(x,1);
else Rotate(x,0),Rotate(x,1);
else
if(x->f->child[0]==x) Rotate(x,1),Rotate(x,0);
else Rotate(x->f,0),Rotate(x,0);
}
void Select(int p,TREE y){
TREE x=root;Pushdown(x);
while(p!=x->child[0]->c+1){
if(p<=x->child[0]->c) x=x->child[0];
else p-=x->child[0]->c+1,x=x->child[1];
Pushdown(x);
}
Splay(x,y);
}
void Visit(TREE x){
if(x==Null) return;
Visit(x->child[0]);
cout << x->c << " " << x->s << " " << x->lc << " " << x->rc << endl;
Visit(x->child[1]);
}
void Insert(int p,int n,int *a){
TREE s,t;
s=t=NewNode(a[1],Null);
for(int i=2;i<=n;i++) t=t->child[1]=NewNode(a[i],t);
Select(p+1,Null),Select(p+2,root);
root->child[1]->child[0]=s,s->f=root->child[1];
Splay(t,Null);
Visit(root);
}
void Reverse(int p,int n){
Select(p,Null),Select(p+n+1,root);
root->child[1]->child[0]->rev^=1;
Splay(root->child[1]->child[0],Null);
}
void Change(int p,int n,int v){
Select(p,Null),Select(p+n+1,root);
root->child[1]->child[0]->same=1,root->child[1]->child[0]->v=v;
Splay(root->child[1]->child[0],Null);
}
void Move(int p,int n){
Select(p+1,Null),Select(p+n+2,root);
TREE x=root->child[1]->child[0];
root->child[1]->child[0]=Null;
Pushup(root->child[1]),Pushup(root);
Select(1,Null),Select(2,root);
root->child[1]->child[0]=x,x->f=x->child[1];
Pushup(root->child[1]),Pushup(root);
}
void Swap(int a,int b){
Select(a,Null),Select(b,root);
int v=root->v;
Change(a,1,root->child[1]->v),Change(b,1,v);
}
int Query_Total(){
Selct(1,Null),Select(N+2,root);
TREE x=root->child[1]->child[0];
return max(1,x->s-(x->lc==x->rc));
}
int Query_Part(int a,int b){
if(a<=b){
Select(a,Null),Select(b+2,root);
return x->child[1]->child[0]->s;
}
Select(a,Null),Select(N+2,root);
int ret=root->child[1]->child[0]->s,c=root->child[1]->child[0]->rc;
Select(1,Null),Select(b+2,root);
return ret+root->child[1]->child[0]->s-(c==root->child[1]->child[0]->lc);
}
WDZRMPCBIT end*/
//PoPoQQQ begin
struct color_segment{
int cnt,lcolor,rcolor;
color_segment(int x){
cnt=(!x?0:1);
lcolor=rcolor=x;
}
};
color_segment operator + (const color_segment x,const color_segment y)
{
color_segment re(0);
re.lcolor=x.lcolor?x.lcolor:y.lcolor;
re.rcolor=y.rcolor?y.rcolor:x.rcolor;
re.cnt=x.cnt+y.cnt-(x.rcolor==y.lcolor);
return re;
}
struct NODE{
int num,siz;
NODE *fa,*ls,*rs;
color_segment *s;
int rev_mark,change_mark;
NODE(int x);
void Push_Up();
void Push_Down();
}*null=new NODE(0),*root=null;
int N,M,C;
char p[10];
NODE::NODE(int x){
num=x,siz=1;
if(!x) siz=0;
fa=ls=rs=null;
rev_mark=change_mark=0;
s=new color_segment(x);
}
void NODE::Push_Up(){
siz=ls->siz+rs->siz+1;
*s=(*ls->s)+color_segment(num)+(*rs->s);
}
void NODE::Push_Down(){
if(rev_mark){
ls->rev_mark^=1,rs->rev_mark^=1;
swap(ls->ls,ls->rs),swap(rs->ls,rs->rs);
swap(ls->s->lcolor,ls->s->rcolor),swap(rs->s->lcolor,rs->s->rcolor);
rev_mark=0;
}
if(change_mark){
if(ls!=null){
ls->num=ls->change_mark=change_mark;
*ls->s=color_segment(change_mark);
}
if(rs!=null){
rs->num=rs->change_mark=change_mark;
*rs->s=color_segment(change_mark);
}
change_mark=0;
}
}
void Zig(NODE *x)
{
NODE *y=x->fa;
y->Push_Down();
x->Push_Down();
y->ls=x->rs;
x->rs->fa=y;
x->rs=y;
x->fa=y->fa;
if(y==y->fa->ls)
y->fa->ls=x;
else if(y==y->fa->rs)
y->fa->rs=x;
y->fa=x;
y->Push_Up();
if(y==root)
root=x;
}
void Zag(NODE *x)
{
NODE *y=x->fa;
y->Push_Down();
x->Push_Down();
y->rs=x->ls;
x->ls->fa=y;
x->ls=y;
x->fa=y->fa;
if(y==y->fa->ls)
y->fa->ls=x;
else if(y==y->fa->rs)
y->fa->rs=x;
y->fa=x;
y->Push_Up();
if(y==root)
root=x;
}
void Splay(NODE *x,NODE *Tar)
{
while(1)
{
NODE *y=x->fa,*z=y->fa;
if(y==Tar)
break;
if(z==Tar)
{
if(x==y->ls) Zig(x);
else Zag(x);
break;
}
if(x==y->ls)
{
if(y==z->ls)
Zig(y);
Zig(x);
}
else
{
if(y==z->rs)
Zag(y);
Zag(x);
}
}
x->Push_Up();
}
void Find(NODE *x,int y,NODE *z){
while(1){
x->Push_Down();
if(y<=x->ls->siz) x=x->ls;
else{
y-=x->ls->siz;
if(y==1) break;
y--,x=x->rs;
}
}
Splay(x,z);
}
void Insert(NODE *&x,int y,NODE *z){
if(x==null){
x=new NODE(y);
x->fa=z;
Splay(x,null);
return;
}
x->Push_Down();
Insert(x->rs,y,x);
}
int main(){
cin >> N >> C;
Insert(root,INT_MAX,null);
for(int i=1,x;i<=N;i++) scanf("%d",&x),Insert(root,x,null);
Insert(root,INT_MAX,null);
cin >> M;
for(int i=1,x,y,z;i<=M;i++){
scanf("%s",p);
if(p[0]=='R'){
scanf("%d",&x);
Find(root,N-x+1,null),Find(root,N+2,root);
NODE *temp=root->rs->ls;
root->rs->ls=null,root->rs->Push_Up();
root->Push_Up();
Find(root,1,null),Find(root,2,root);
root->rs->ls=temp;
temp->fa=root->rs;
root->rs->Push_Up();
root->Push_Up();
}
else if(p[0]=='F'){
Find(root,2,null),Find(root,N+2,root);
NODE *temp=root->rs->ls;
temp->rev_mark^=1;
swap(temp->ls,temp->rs),swap(temp->s->lcolor,temp->s->rcolor);
}
else if(p[0]=='S'){
scanf("%d%d",&x,&y);
if(x==y) continue;
if(x>y) swap(x,y);
Find(root,x+1,null),Find(root,y+1,root);
swap(root->rs->num,root->num);
root->rs->Push_Up(),root->Push_Up();
}
else if(p[0]=='P'){
scanf("%d%d%d",&x,&y,&z);
if(x<=y){
Find(root,x,null),Find(root,y+2,root);
NODE *temp=root->rs->ls;
temp->num=temp->change_mark=z;
*temp->s=color_segment(z);
}
else{
Find(root,x,null),Find(root,N+2,root);
NODE *temp=root->rs->ls;
temp->num=temp->change_mark=z;
*temp->s=color_segment(z);
Find(root,1,null),Find(root,y+2,root);
temp=root->rs->ls;
temp->num=temp->change_mark=z;
*temp->s=color_segment(z);
}
}
else if(p[0]=='C'&&p[1]==0){
Find(root,1,null),Find(root,N+2,root);
NODE *temp=root->rs->ls;
printf("%d
",max(1,temp->s->cnt-(temp->s->lcolor==temp->s->rcolor)));
}
else{
scanf("%d%d",&x,&y);
if(x<=y){
Find(root,x,null),Find(root,y+2,root);
NODE *temp=root->rs->ls;
printf("%d
",temp->s->cnt);
}
else{
Find(root,x,null),Find(root,N+2,root);
NODE *temp=root->rs->ls;
color_segment s=*temp->s;
Find(root,1,null),Find(root,y+2,root);
temp=root->rs->ls,s=s+*temp->s;
printf("%d
",s.cnt);
}
}
}
return 0;
}
//PoPoQQQ end
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
