2
29
2016
1

[BZOJ4320] ShangHai2006 Homework

最近感觉状态差极了

这种题要调40min……

UR水题不会做

以我3个月前的水平反而会了

感觉极其不爽,为什么有些人没有你努力竞赛照样比你搞得好那是因为这些人太假了,刷题都用小号给你造成不怎么刷题的假象(2016.3.10才发现……)

我觉得这和智商没什么关系

不说了,这是一个裸并查集

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,f[300005],is[300005],stx[555];

struct Read{
int opt,v,ans;
}read[100005];

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){if(sa<sb)f[sa]=sb;else f[sb]=sa;}

int main(){
freopen("4320.in","r",stdin);
freopen("4320.out","w",stdout);
scanf("%d",&n);
memset(stx,127,sizeof(stx));
for(int i=1;i<=n;i++){
	char s[10];
	int val;
	scanf("%s %d",s,&val);
	read[i].opt=s[0]-'A';
	read[i].v=val;
	if(read[i].opt==0){
		for(int j=1;j<=550;j++)stx[j]=min(stx[j],val%j);
		is[val]=1;
	}
	else if(val<=550){
		read[i].ans=stx[val];
	}
}
f[300001]=300001;
for(int i=300000;i>=1;i--){if(!is[i])f[i]=Find(f[i+1]);else f[i]=i;}
for(int i=n;i>=1;i--){
	if(read[i].opt==0){
		Union(Find(read[i].v),Find(read[i].v+1));
	}
	else if(read[i].v>550){
		read[i].ans=2100000000;
		for(int j=0;j*read[i].v<=300000;j++){
			read[i].ans=min(read[i].ans,(Find(read[i].v*j==0?1:read[i].v*j)==300001?read[i].v-1:Find(read[i].v*j==0?1:read[i].v*j))%read[i].v);
		}
	}
}
for(int i=1;i<=n;i++){
	if(read[i].opt)printf("%d\n",read[i].ans);
}
return 0;
}
Category: BZOJ | Tags: 随笔 OI bzoj
2
27
2016
0

[BZOJ1087] [SCOI2005]互不侵犯King

状压DP

f[i][j][k]表示当前在第i行,包括第i行一共放了j个国王,而且这一行状态为k的方案数

那么f[i][j][k]=Sigma(f[i-1][j-cnt[l]][l],其中l为一种可行方案且不和k状态冲突)

然后搞个ans加一下就没了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

long long n,K,cnt[1<<10],f[15][105][1<<10],rule[1<<10],ed,ans;

int Cnt(int s){
int ans=0;
while(s){
	ans+=s&1;
	s>>=1;
}
return ans;
}

int CheckNot(int s,int l){
return (s&l)||(s&(l>>1))||(s&(l<<1));
}

int CheckGood(int s){
int flg=0;
while(s){
	if(s&1 && flg)return 0;
	flg=s&1;
	s>>=1;
}
return 1;
}

void Get(){
for(int i=0;i<=ed;i++){cnt[i]=Cnt(i);rule[i]=CheckGood(i);}
}

int main(){
freopen("1087.in","r",stdin);
freopen("1087.out","w",stdout);
scanf("%lld %lld",&n,&K);
ed=(1<<n)-1;
Get();
for(int i=0;i<=ed;i++)if(rule[i])f[1][cnt[i]][i]=1;
for(int i=2;i<=n;i++){
	for(int j=0;j<=ed;j++){
		if(!rule[j])continue;
        for(int k=0;k<=ed;k++){
			if(!rule[k] || CheckNot(j,k))continue;
			for(int l=cnt[k];l+cnt[j]<=K;l++)f[i][l+cnt[j]][j]+=f[i-1][l][k];
        }
	}
}
for(int i=0;i<=ed;i++)ans+=f[n][K][i];
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
26
2016
0

[BZOJ1084] [SCOI2005]最大子矩阵

m<=2。。。

所以直接DP

m=1时

f[i][1][k]表示这一列前i个数选了k个子矩阵(中间的1没有用处)

那么转移就很像最大子段和:f[i][1][k]=max(f[i-1][1][k],f[j][1][k-1]+sum[i]-sum[j]);

前面表示不选择,后面表示选择j-i这一段所能带来的当前情况下的最大得分

m=2时复杂一些

f[i][j][k]表示第一列前i个数第二列前j个数选了k个子矩阵

那么转移分4种情况

1:f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);表示继承上一个状态的结果,不选择i或者j

2:f[i][j][k]=max(f[i][j][k],f[ix][j][k-1]+sum[i][1]-sum[ix][1]);表示选择ix-i这一段所能带来的当前情况下的最大得分

3:f[i][j][k]=max(f[i][j][k],f[i][jx][k-1]+sum[j][2]-sum[jx][2]);表示选择jx-j这一段所能带来的当前情况下的最大得分

4:if(i==j)f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+sum[i][1]-sum[x][1]+sum[j][2]-sum[x][2]);表示同时选择两排所能带来的最大得分

最后输出f[n][n][k]就可以了,表示第一列和第二列都选完了,一共选择了k个子矩阵

难得写一次详细的题解……主要是因为我在狂补DP,DP渣到连前几年的普及组题目都写不出来……

去年NOIP D2T2居然不会写

这都坚定了我要补DP的决心……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int sum[105][5],f[105][105][15],a[105][5],n,m,K;

int main(){
freopen("1084.in","r",stdin);
freopen("1084.out","w",stdout);
scanf("%d %d %d",&n,&m,&K);
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		scanf("%d",&a[i][j]);
		sum[i][j]=sum[i-1][j]+a[i][j];
	}
}
memset(f,-127,sizeof(f));
if(m==1){
	for(int i=0;i<=n;i++)f[i][1][0]=0;
	for(int i=1;i<=n;i++){
		for(int k=1;k<=K;k++){
			f[i][1][k]=f[i-1][1][k];
			for(int j=0;j<i;j++){
				f[i][1][k]=max(f[i][1][k],f[j][1][k-1]+sum[i][1]-sum[j][1]);
			}
		}
	}
	printf("%d\n",f[n][1][K]);
}
else if(m==2){
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)f[i][j][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=K;k++){
				f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
				for(int ix=0;ix<i;ix++)f[i][j][k]=max(f[i][j][k],f[ix][j][k-1]+sum[i][1]-sum[ix][1]);
				for(int jx=0;jx<j;jx++)f[i][j][k]=max(f[i][j][k],f[i][jx][k-1]+sum[j][2]-sum[jx][2]);
				if(i==j)for(int x=0;x<i;x++)f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+sum[i][1]-sum[x][1]+sum[j][2]-sum[x][2]);
			}
		}
	}
	printf("%d\n",f[n][n][K]);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
25
2016
1

[BZOJ2631] tree

又做了一道叫"tree"的题目。。

这题要开unsigned int!!!!

开int会WA!开int会WA!开int会WA!重要的事说三遍

#include<cstdio>
#include<algorithm>
using namespace std;

unsigned int n,q;

struct Node{
unsigned int v,sum,add,rev,mul,siz;
Node *ch[2],*fa;
Node(unsigned int val,Node *fat);
void Pushdown();
void Pushup();
}*root[100005],*Null;

Node::Node(unsigned int val,Node *fat){
v=sum=val;
mul=siz=1;
add=rev=0;
ch[0]=ch[1]=Null;
fa=fat;
}

void Node::Pushdown(){
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
}
if(mul!=1){
	if(ch[0]!=Null){
		ch[0]->mul=(ch[0]->mul*mul)%51061;
		ch[0]->add=(ch[0]->add*mul)%51061;
		ch[0]->sum=(ch[0]->sum*mul)%51061;
		ch[0]->v=(ch[0]->v*mul)%51061;
	}
	if(ch[1]!=Null){
		ch[1]->mul=(ch[1]->mul*mul)%51061;
		ch[1]->add=(ch[1]->add*mul)%51061;
		ch[1]->sum=(ch[1]->sum*mul)%51061;
		ch[1]->v=(ch[1]->v*mul)%51061;
	}
	mul=1;
}
if(add){
	if(ch[0]!=Null){
		ch[0]->add=(ch[0]->add+add)%51061;
		ch[0]->sum=(ch[0]->sum+ch[0]->siz%51061*add)%51061;
		ch[0]->v=(ch[0]->v+add)%51061;
	}
	if(ch[1]!=Null){
		ch[1]->add=(ch[1]->add+add)%51061;
		ch[1]->sum=(ch[1]->sum+ch[1]->siz%51061*add)%51061;
		ch[1]->v=(ch[1]->v+add)%51061;
	}
	add=0;
}
}

void Node::Pushup(){
siz=1;
sum=v;
if(ch[0]!=Null){siz+=ch[0]->siz;sum=(sum+ch[0]->sum)%51061;}
if(ch[1]!=Null){siz+=ch[1]->siz;sum=(sum+ch[1]->sum)%51061;}
}

int Notroot(Node *p){
return (p->fa->ch[0]==p)||(p->fa->ch[1]==p);
}

void Prepare(Node *p){
if(Notroot(p))Prepare(p->fa);
p->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
swap(x->ch[0],x->ch[1]);
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){x->fa=Null;y->ch[0]=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

Node *ToLct(int x){
return root[x];
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->siz=0;
return p;
}

void Add(int x,int y,int z){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
q->add=(q->add+z)%51061;
q->v=(q->v+z)%51061;
q->Pushup();
}

void Mul(int x,int y,int z){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
q->mul=(q->mul*z)%51061;
q->v=(q->v*z)%51061;
q->Pushup();
}

unsigned int Div(int x,int y){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
return q->sum;
}

int main(){
freopen("2631.in","r",stdin);
freopen("2631.out","w",stdout);
scanf("%d %d",&n,&q);
Null=GetNull();
for(int i=1;i<=n;i++)root[i]=new Node(1,Null);
for(int i=1;i<n;i++){
	int u,v;
    scanf("%d %d",&u,&v);
    Link(ToLct(u),ToLct(v));
}
for(int i=1;i<=q;i++){
    char s[3];
    scanf("%s",s);
    if(s[0]=='+'){
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		Add(u,v,c);
    }
    if(s[0]=='-'){
		int u1,v1,u2,v2;
		scanf("%d %d %d %d",&u1,&v1,&u2,&v2);
        Cut(ToLct(u1),ToLct(v1));
        Link(ToLct(u2),ToLct(v2));
    }
    if(s[0]=='*'){
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		Mul(u,v,c);
    }
    if(s[0]=='/'){
		int u,v;
		scanf("%d %d",&u,&v);
		printf("%d\n",Div(u,v));
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
24
2016
0

[BZOJ2654] tree

怎么说呢……神奇的二分

每次把白色边加上一个二分的权值,再做最小生成树

如果大于need条边就说明加上的权值太小了需要增大

反之亦然(因为题目保证有解,所以必然会存在这样的一个权值)

注意排序时权值相等时白色边放在前面

#include<cstdio>
#include<algorithm>
using namespace std;

int V,E,need,f[100005],test=0,ne=0;

struct Edge{
int a,b,v,co;
friend bool operator<(Edge a,Edge b){
return a.v==b.v?a.co<b.co:a.v<b.v;
}
}e[100005];

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){
if(sa<sb)f[sb]=sa;
else f[sa]=sb;
}

int Check(int ans){
test=ne=0;
for(int i=1;i<=V;i++)f[i]=i;
for(int i=1;i<=E;i++){
	if(!e[i].co)e[i].v+=ans;
}
sort(e+1,e+E+1);
for(int i=1;i<=E;i++){
	if(Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		test+=e[i].v;
		if(!e[i].co)ne++;
	}
}
for(int i=1;i<=E;i++){
	if(!e[i].co)e[i].v-=ans;
}
return ne>=need;
}

int main(){
freopen("2654.in","r",stdin);
freopen("2654.out","w",stdout);
scanf("%d %d %d",&V,&E,&need);
for(int i=1;i<=E;i++){
	scanf("%d %d %d %d",&e[i].a,&e[i].b,&e[i].v,&e[i].co);
	e[i].a++;
	e[i].b++;
}
int l=-105,r=105,ans;
while(l<=r){
	int mid=l+r>>1;
	if(Check(mid)){ans=test-need*mid;l=mid+1;}
	else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
23
2016
0

[BZOJ1305] [CQOI2009]dance跳舞

最大流

拆点,男孩和女孩各拆成2个点ix,iy,jx,jy,互相喜欢ix->jx:1 不互相喜欢iy->jy:1

然后ix->iy=k,jy->jx=k,S->ix=ans,jy->T=ans

枚举ans跑最大流,不满流答案就是ans-1

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
 
int en,n,k,level[1005],S,T,cur[1005],POINT_N,h[1005];
char s[55][55];
 
struct Edge{
int b,f,back,next;
}e[1000005];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
 
int BFS(){
queue<int> Q;
Q.push(S);
memset(level,0,sizeof(level));
level[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(level[v] || !e[i].f)continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
 
int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))){
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
int Dinic(){
int ans=0;
while(BFS()){
    for(int i=1;i<=POINT_N;i++)cur[i]=h[i];
    ans+=DFS(S,2100000000);
}
return ans;
}
 
int main(){
freopen("1305.in","r",stdin);
freopen("1305.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
S=4*n+1;
T=4*n+2;
POINT_N=4*n+2;
int ans=1;
while(ans<=1000){
    memset(h,0,sizeof(h));
    for(int i=1;i<=n;i++){
        AddEdge(i,i+n,k);
        AddEdge(i+3*n,i+2*n,k);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s[i][j]=='Y'){
                AddEdge(i,j+2*n,1);
            }
            else {
                AddEdge(i+n,j+3*n,1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        AddEdge(S,i,ans);
        AddEdge(i+2*n,T,ans);
    }
    int an=Dinic();
    //printf("%d\n",ans);
    if(an<ans*n){printf("%d\n",ans-1);return 0;}
    ans++;
}
return 0;
}

Category: BZOJ | Tags: OI bzoj
2
23
2016
0

[BZOJ1266] [AHOI2006]上学路线route

这题有2问

第一问SPFA

第二问先从1->n 求一遍最短路,再从n->1求一遍最短路,然后判定每条边是否可能在最短路上

即D[e[i].a]+Di[e[i].b]+e[i].t==ans

注意每条边的反向边也需要判断一下

然后跑一遍最大流就行了(最小割=最大流)

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int h[505],n,m,en,en1,D[505],Di[505],flag[505],S,T,cur[505];

struct Es{
int a,b,t,c;
}E[200005];

struct Edge1{
int b,v,next;
}e1[300005];

struct Edge{
int b,f,next,back;
}e[300005];

void AddEdge1(int sa,int sb,int sc){
e1[++en1].b=sb;
e1[en1].v=sc;
e1[en1].next=h[sa];
h[sa]=en1;
}

void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].next=h[sa];
e[en].back=en+1;
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].next=h[sa];
e[en].back=en-1;
h[sa]=en;
}

int Spfa(int S,int T){
queue<int> Q;
memset(D,127,sizeof(D));
memset(flag,0,sizeof(flag));
Q.push(S);
D[S]=0;
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	flag[u]=0;
	for(int i=h[u];i;i=e1[i].next){
		int v=e1[i].b;
		if(D[u]+e1[i].v<D[v]){
			D[v]=D[u]+e1[i].v;
            if(!flag[v]){
				Q.push(v);
				flag[v]=1;
            }
		}
	}
}
return D[T];
}

int Spfa2(int S,int T){
queue<int> Q;
memset(Di,127,sizeof(Di));
memset(flag,0,sizeof(flag));
Q.push(S);
Di[S]=0;
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	flag[u]=0;
	for(int i=h[u];i;i=e1[i].next){
		int v=e1[i].b;
		if(Di[u]+e1[i].v<Di[v]){
			Di[v]=Di[u]+e1[i].v;
            if(!flag[v]){
				Q.push(v);
				flag[v]=1;
            }
		}
	}
}
return Di[T];
}

int Bfs(){
queue<int> Q;
Q.push(S);
memset(flag,0,sizeof(flag));
flag[S]=1;
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(flag[v] || !e[i].f)continue;
		flag[v]=flag[u]+1;
		Q.push(v);
	}
}
return flag[T];
}

int Dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int v=e[i].b,fl;
	if(flag[v]==flag[u]+1 && e[i].f && (fl=Dfs(v,min(f,e[i].f)))){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(f==0)return flow;
	}
}
return flow-f;
}

int Dinic(){
int ans=0;
while(Bfs()){
	for(int i=1;i<=n;i++)cur[i]=h[i];
	ans+=Dfs(S,2100000000);
}
return ans;
}

int main(){
freopen("1266.in","r",stdin);
freopen("1266.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
	scanf("%d %d %d %d",&E[i].a,&E[i].b,&E[i].t,&E[i].c);
	AddEdge1(E[i].a,E[i].b,E[i].t);
	AddEdge1(E[i].b,E[i].a,E[i].t);
}
int ans1=Spfa(1,n),ans2=Spfa2(n,1);
memset(h,0,sizeof(h));
printf("%d\n",ans1);
for(int i=1;i<=m;i++){
	if(D[E[i].a]+Di[E[i].b]+E[i].t==ans1){AddEdge(E[i].a,E[i].b,E[i].c);}
	if(Di[E[i].a]+D[E[i].b]+E[i].t==ans1){AddEdge(E[i].b,E[i].a,E[i].c);}
}
S=1;T=n;
ans2=Dinic();
printf("%d\n",ans2);
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
22
2016
0

[BZOJ1269] [AHOI2006]文本编辑器editor

这题写了我1.5h……

以后写题目必须认真、仔细!

Pushdown居然写错了……调试了半天

所以以后必须仔细想好细节再写,这样才能节省时间。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,move_to=0;
char s[2000005];

struct Node{
char v;
int rev,siz;
Node *ch[2],*fa;
Node(char ch,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;

Node::Node(char c,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
siz=1;
rev=0;
v=c;
}

void Node::Pushdown(){
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}

void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place)Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else {Rotate(y,1);Rotate(x,1);}
	}
}
if(place==Null)root=x;
}

Node *Find(Node *splay,int k){
splay->Pushdown();
if(k==splay->ch[0]->siz+1)return splay;
if(k<=splay->ch[0]->siz)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}

Node *Split(int pos,int tot){
Node *x=Find(root,pos),*y=Find(root,pos+tot+1);
Splay(x,Null);
Splay(y,root);
return y->ch[0];
}

Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(s[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}

void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}

Node *GetNull(){
Node *p=new Node('#',Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->siz=p->rev=0;
}

void Build_First(){
Null=GetNull();
s[1]='H';
s[2]='i';
root=Build(1,2);
}

void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}

void Delete(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}

void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->rev^=1;
swap(seq->ch[0],seq->ch[1]);
fat->Pushup();
fat->fa->Pushup();
}

char GetKey(int pos){
Node *u=Split(pos,1);
return u->v;
}

void GetString(int len){
char ch;
while((ch=getchar())=='\n');
s[1]=ch;
for(int i=2;i<=len;i++){s[i]=getchar();}
s[len+1]='\0';
}

int main(){
freopen("1269.in","r",stdin);
freopen("1269.out","w",stdout);
scanf("%d",&n);
Build_First();
for(int i=1;i<=n;i++){
	char opt[10];
	scanf("%s",opt);
	if(opt[0]=='M'){
		int k;
		scanf("%d",&k);
		move_to=k;
	}
	if(opt[0]=='I'){
		int tot;
		scanf("%d",&tot);
		GetString(tot);
		Insert(move_to,tot);
	}
	if(opt[0]=='D'){
		int tot;
		scanf("%d",&tot);
        Delete(move_to+1,tot);
	}
	if(opt[0]=='R'){
		int tot;
		scanf("%d",&tot);
		Reverse(move_to+1,tot);
	}
	if(opt[0]=='G'){
        printf("%c\n",GetKey(move_to+1));
	}
	if(opt[0]=='P')move_to--;
	if(opt[0]=='N')move_to++;
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
22
2016
0

[BZOJ3673&3674] 可持久化并查集 by zky & 可持久化并查集加强版

两个都是可持久化线段树,相当于复习一下算法。。

第一个程序我没加路径压缩,第二个加了

第二个读入的操作编号不要异或lastans……在这里卡了一下

#include<cstdio>
#include<algorithm>
using namespace std;

struct SegTree{
int l,r,ls,rs,v;
}tree[2000005];

int root[20005],cnt,deep[200005],n,m;

void Build(int &rt,int l,int r){
if(!rt)rt=++cnt;
if(l==r){tree[rt].v=l;return;}
int mid=l+r>>1;
tree[rt].l=l;
tree[rt].r=r;
Build(tree[rt].ls,l,mid);
Build(tree[rt].rs,mid+1,r);
}

void Change(int x,int &y,int pos,int val){
y=++cnt;
tree[y].l=tree[x].l;
tree[y].r=tree[x].r;
if(tree[x].l==tree[x].r){tree[y].v=val;deep[y]=deep[x];return;}
tree[y].ls=tree[x].ls;
tree[y].rs=tree[x].rs;
int mid=tree[x].l+tree[x].r>>1;
if(pos<=mid)Change(tree[x].ls,tree[y].ls,pos,val);
if(pos>mid)Change(tree[x].rs,tree[y].rs,pos,val);
}

int Query(int rt,int pos){
if(tree[rt].l==tree[rt].r)return rt;
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(tree[rt].ls,pos);
if(pos>mid)return Query(tree[rt].rs,pos);
}

void Add(int rt,int pos){
if(tree[rt].l==tree[rt].r){deep[rt]++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Add(tree[rt].ls,pos);
if(pos>mid)Add(tree[rt].rs,pos);
}

int Find(int rt,int x){
int tp=Query(rt,x);
if(x==tree[tp].v)return tp;
return Find(rt,tree[tp].v);
}

int main(){
freopen("3673.in","r",stdin);
freopen("3673.out","w",stdout);
scanf("%d %d",&n,&m);
Build(root[0],1,n);
for(int i=1;i<=m;i++){
    int opt;
    scanf("%d",&opt);
    if(opt==1){
		int x,y,px,py;
        scanf("%d %d",&x,&y);
        root[i]=root[i-1];
        px=Find(root[i],x);py=Find(root[i],y);
        if(tree[px].v==tree[py].v)continue;
        if(deep[px]>deep[py])swap(px,py);
        Change(root[i-1],root[i],tree[px].v,tree[py].v);
        if(deep[px]==deep[py])Add(root[i],tree[py].v);
    }
    if(opt==2){
		int k;
		scanf("%d",&k);
		root[i]=root[k];
    }
    if(opt==3){
		int x,y;
		root[i]=root[i-1];
		scanf("%d %d",&x,&y);
		if(tree[Find(root[i],x)].v!=tree[Find(root[i],y)].v)puts("0");
		else puts("1");
    }
}
return 0;
}
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,cnt,lastans=0,deep[10000005],root[200005];

struct SegTree{
int l,r,ls,rs,v;
}tree[10000005];

void Build(int &rt,int l,int r){
if(!rt)rt=++cnt;
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].v=l;return;}
int mid=l+r>>1;
Build(tree[rt].ls,l,mid);
Build(tree[rt].rs,mid+1,r);
}

void Change(int x,int &y,int pos,int val){
y=++cnt;
tree[y].l=tree[x].l;
tree[y].r=tree[x].r;
if(tree[x].l==tree[x].r){tree[y].v=val;deep[y]=deep[x];return;}
tree[y].ls=tree[x].ls;
tree[y].rs=tree[x].rs;
int mid=tree[x].l+tree[x].r>>1;
if(pos<=mid)Change(tree[x].ls,tree[y].ls,pos,val);
if(pos>mid)Change(tree[x].rs,tree[y].rs,pos,val);
}

void Add(int rt,int pos){
if(tree[rt].l==tree[rt].r){deep[rt]++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Add(tree[rt].ls,pos);
if(pos>mid)Add(tree[rt].rs,pos);
}

int Query(int rt,int pos){
if(tree[rt].l==tree[rt].r){return rt;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(tree[rt].ls,pos);
if(pos>mid)return Query(tree[rt].rs,pos);
}

int Find(int rt,int x){
int p=Query(rt,x);
if(x==tree[p].v){return p;}
int tp=Find(rt,tree[p].v);
Change(rt,rt,tree[p].v,tp);
return tp;
}

int main(){
freopen("3674.in","r",stdin);
freopen("3674.out","w",stdout);
scanf("%d %d",&n,&m);
Build(root[0],1,n);
for(int i=1;i<=m;i++){
    int opt;
    scanf("%d",&opt);
    if(opt==1){
		int x,y,p,q;
		scanf("%d %d",&x,&y);
		x^=lastans;y^=lastans;
        root[i]=root[i-1];
        p=Find(root[i],x);
        q=Find(root[i],y);
        if(tree[p].v==tree[q].v)continue;
        if(deep[p]>deep[q])swap(p,q);
        Change(root[i-1],root[i],tree[p].v,tree[q].v);
        if(deep[p]==deep[q])Add(root[i],tree[q].v);
    }
    if(opt==2){
		int k;
		scanf("%d",&k);
		k^=lastans;
        root[i]=root[k];
    }
    if(opt==3){
		int x,y;
		scanf("%d %d",&x,&y);
		x^=lastans;y^=lastans;
		root[i]=root[i-1];
        if(tree[Find(root[i],x)].v==tree[Find(root[i],y)].v){puts("1");lastans=1;}
        else {puts("0");lastans=0;}
	}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
21
2016
0

[BZOJ1500] [NOI2005]维修数列

Splay模版题

调试两天总算A啦!

2016/2/21 *1

2016/3/20 *1

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1000005],m;

struct Node{
int v,mx,sum,lx,rx,siz,tag,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;

Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=sum=mx=val;
tag=rev=0;
siz=1;
if(v>=0)lx=rx=v;
else lx=rx=0;
}

void Node::Pushdown(){
if(tag){
	tag=rev=0;
	if(ch[0]!=Null){ch[0]->tag=1;ch[0]->sum=ch[0]->siz*v;ch[0]->v=v;}
	if(ch[1]!=Null){ch[1]->tag=1;ch[1]->sum=ch[1]->siz*v;ch[1]->v=v;}
	if(v>=0){
        if(ch[0]!=Null){ch[0]->lx=ch[0]->mx=ch[0]->rx=v*ch[0]->siz;}
        if(ch[1]!=Null){ch[1]->lx=ch[1]->mx=ch[1]->rx=v*ch[1]->siz;}
	}
	else {
		if(ch[0]!=Null){ch[0]->mx=v;ch[0]->lx=ch[0]->rx=0;}
        if(ch[1]!=Null){ch[1]->mx=v;ch[1]->lx=ch[1]->rx=0;}
	}
}
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
	swap(ch[0]->lx,ch[0]->rx);
	swap(ch[1]->lx,ch[1]->rx);
}
}

void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
sum=ch[0]->sum+ch[1]->sum+v;
mx=max(ch[0]->mx,ch[1]->mx);
mx=max(mx,ch[0]->rx+v+ch[1]->lx);
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place)Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
if(place==Null)root=x;
}

Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}

Node *Split(int pos,int tot){
Node *x=Find(root,pos);
Splay(x,Null);
Node *y=Find(root,pos+tot+1);
Splay(y,root);
return y->ch[0];
}

Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}

void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->fa=p->ch[0]=p->ch[1]=p;
p->mx=p->v=-1000000000;
p->rev=p->tag=p->siz=p->sum=p->lx=p->rx=0;
return p;
}

void Build_First(){
Null=GetNull();
a[1]=-1000000000;
a[n+2]=-1000000000;
root=Build(1,n+2);
}

void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}

void Delete(int pos,int val){
Node *seq=Split(pos,val),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}

void MakeSame(int pos,int tot,int val){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->tag=1;
seq->sum=seq->siz*val;
seq->v=val;
if(val>=0)seq->lx=seq->rx=seq->mx=seq->siz*val;
else seq->lx=seq->rx=0,seq->mx=val;
fat->Pushup();
fat->fa->Pushup();
}

void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
if(!seq->tag){
	seq->rev^=1;
	swap(seq->ch[0],seq->ch[1]);
	swap(seq->lx,seq->rx);
	fat->Pushup();
	fat->fa->Pushup();
}
}

int GetSum(int pos,int tot){
Node *seq=Split(pos,tot);
return seq->sum;
}

int main(){
freopen("1500.in","r",stdin);
freopen("1500.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);
Build_First();
for(int i=1;i<=m;i++){
	char s[10];
    scanf("%s",s);
    if(s[0]=='I'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		for(int i=1;i<=tot;i++)scanf("%d",&a[i]);
		Insert(pos,tot);
	}
	if(s[0]=='D'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		Delete(pos,tot);
	}
	if(s[0]=='M' && s[2]=='K'){
		int pos,tot,val;
		scanf("%d %d %d",&pos,&tot,&val);
        MakeSame(pos,tot,val);
	}
	if(s[0]=='M' && s[2]=='X'){
		printf("%d\n",root->mx);
	}
	if(s[0]=='R'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		Reverse(pos,tot);
	}
	if(s[0]=='G'){
		int pos,tot;
		scanf("%d %d",&pos,&tot);
		printf("%d\n",GetSum(pos,tot));
	}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com