loj2092 「ZJOI2016」大森林

ref不是太懂……
#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, m, tot, val[200005], fa[200005], idx[200005], num, lf[200005], cnt;

int ans[200005], ch[200005][2], sum[200005], rg[200005], opt, uu, vv, ww;

struct Node{

	int pos, idx, u, v;

	bool operator<(const Node &x)const{

		if(pos!=x.pos)	return pos<x.pos;

		return idx<x.idx;

	}

}nd[400005];

int getW(int x){

	return ch[fa[x]][1]==x;

}

void upd(int x){

	sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x];

}

bool isRoot(int x){

	return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;

}

void rotate(int x){

	int old=fa[x], oldf=fa[old], w=getW(x);

	if(!isRoot(old))	ch[oldf][ch[oldf][1]==old] = x;

	ch[old][w] = ch[x][w^1]; ch[x][w^1] = old;

	fa[ch[x][w^1]] = x; fa[ch[old][w]] = old; fa[x] = oldf;

	upd(old); upd(x);

}

void splay(int x){

	while(!isRoot(x)){

		int f=fa[x];

		if(!isRoot(f))	rotate(getW(f)==getW(x)?f:x);

		rotate(x);

	}

	upd(x);

}

int access(int x){

	int y=0;

	while(x){

		splay(x);

		ch[x][1] = y;

		upd(x);

		y = x;

		x = fa[x];

	}

	return y;

}

void cut(int x){

	access(x);

	splay(x);

	fa[ch[x][0]] = 0;

	ch[x][0] = 0;

	upd(x);

}

int main(){

	cin>>n>>m;

	val[1] = lf[1] = tot = num = idx[1] = 1;

	rg[1] = n;

	fa[++tot] = 1;

	int now=tot;

	for(int i=1; i<=m; i++){

		scanf("%d", &opt);

		if(!opt){

			scanf("%d %d", &uu, &vv);

			val[++tot] = 1; idx[++num] = tot; lf[num] = uu; rg[num] = vv;

			fa[tot] = now;

		}

		else if(opt==1){

			scanf("%d %d %d", &uu, &vv, &ww);

			uu = max(uu, lf[ww]); vv = min(vv, rg[ww]);

			if(uu>vv)	continue;

			fa[++tot] = now;

			nd[++cnt] = (Node){uu, i-m, tot, idx[ww]};

			nd[++cnt] = (Node){vv+1, i-m, tot, now};

			now = tot;

		}

		else{

			scanf("%d %d %d", &ww, &uu, &vv);

			nd[++cnt] = (Node){ww, i, idx[uu], idx[vv]};

		}

	}

	sort(nd+1, nd+1+cnt);

	int k=1;

	memset(ans, -1, sizeof(ans));

	for(int i=1; i<=n; i++){

		for(; k<=cnt && nd[k].pos==i; k++){

			if(nd[k].idx<=0){

				cut(nd[k].u);

				fa[nd[k].u] = nd[k].v;

			}

			else{

				access(nd[k].u); splay(nd[k].u); int qwq=sum[nd[k].u];

				int t=access(nd[k].v); splay(nd[k].v); qwq += sum[nd[k].v];

				access(t); splay(t); qwq -= sum[t] << 1;

				ans[nd[k].idx] = qwq;

			}

		}

	}

	for(int i=1; i<=m; i++)

		if(ans[i]>=0)

			printf("%d\n", ans[i]);

	return 0;

}
巴特西

loj2092 「ZJOI2016」大森林

最新文章

热门文章
