BZOJ 3673&3674 可持久化并查集 by zky 【主席树】

tonyfang posted @ 2016年3月01日 16:58 in BZOJ with tags C++ OI , 489 阅读

只需要随便yy一下主席数就可以咯

两题用同一个代码就可以啦

 

# include <stdio.h>
# include <algorithm>
using namespace std;
int n,m,cnt=0;
const int M=12000010;
int root[M],ch[M][2],s[M],d[M];
void build(int &rt,int l,int r) {
	if(!rt) rt=++cnt;
	if(l==r) {s[rt]=l;return;}
	int mid=l+r>>1;
	build(ch[rt][0],l,mid);
	build(ch[rt][1],mid+1,r);
}
void modify(int l,int r,int oldrt,int &rt,int pos,int val) {
	rt=++cnt;
	if(l==r) {
		s[rt]=val;
		d[rt]=d[oldrt];
		return ;
	}
	ch[rt][0]=ch[oldrt][0],ch[rt][1]=ch[oldrt][1];
	int mid=l+r>>1;
	if(pos<=mid) modify(l,mid,ch[oldrt][0],ch[rt][0],pos,val);
	else modify(mid+1,r,ch[oldrt][1],ch[rt][1],pos,val);
}

int query(int rt,int l,int r,int pos) {
	if(l==r) return rt;
	int mid=l+r>>1;
	if(pos<=mid) return query(ch[rt][0],l,mid,pos);
	else return query(ch[rt][1],mid+1,r,pos);
}

void add(int rt,int l,int r,int pos) {
	if(l==r) {
		d[rt]++;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) add(ch[rt][0],l,mid,pos);
	else add(ch[rt][1],mid+1,r,pos);
}

int get(int rt,int x) {
	int rtt=query(rt,1,n,x);
	if(x==s[rtt]) return rtt;
	return get(rt,s[rtt]);
}

int main() {
	scanf("%d%d",&n,&m);
	build(root[0],1,n);
	for (int i=1;i<=m;++i) {
		int buf,a,b,k;
		scanf("%d",&buf);
		if(buf==1) {
			root[i]=root[i-1];
			scanf("%d%d",&a,&b);
			int p=get(root[i],a),q=get(root[i],b);
			if(s[p]==s[q]) continue;
			if(d[p]>d[q]) swap(p,q);
			modify(1,n,root[i-1],root[i],s[p],s[q]);
			if(d[p]==d[q]) add(root[i],1,n,s[q]);
		} else if(buf==2) {
			scanf("%d",&k);
			root[i]=root[k];
		} else if(buf==3) {
			root[i]=root[i-1];
			scanf("%d%d",&a,&b);
			int p=get(root[i],a),q=get(root[i],b);
			if(s[p]==s[q]) puts("1");
			else puts("0");
		}
	}
}
badi9.in 说:
2023年4月21日 20:51

Badi9 is open in PDF plan In download. directorate of Government Assessment, Open Test on June 2023. Snap on the association of the specific subject referred to in the table underneath. badi9.in A Pdf record will be opened on the screen. Snap on ‘Free Download’ Option and Download the We gave standard emodelpaper to all subjects both in english and tamil Medium.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter