Newnode's NOI 模拟赛 第三题 【可持久化线段树优化建图】

题面：

n<=100000

题目分析：

两个宇宙之间的大小关系是确定的，考虑从大的向小的连一条边。
这样连边可能会成环（边双联通分量），按某种顺序排列，环中的点都可能成为环中的最大点，tarjan将环缩点之后，没有入度的连通分量中的点就是可能成为最大宇宙的点。
正确性似乎比较显然，于是考场上打了60分的n²暴力就溜了。
后来一想，边数太多，显然又是什么xxx优化建边。
果然。
以下题解引自Mogician_Evian dalao的博客

可持久化线段树的时候注意一下版本信息的维护就好了，其实还是挺好打的。

Code：

#include<cstdio>
#include<vector>
#include<algorithm>
#define maxn 100005
#define maxp 100005*60
#define maxm maxp*5
using namespace std;
int n,dfn[maxp],low[maxp],tim,stk[maxp],top,scc[maxp],scnt,in[maxp];
int fir[maxp],nxt[maxm],to[maxm],tot;
int a[maxn],b[maxn],c[maxn],Ans;
bool vis[maxp];
vector<int>e[maxp];
int rt,sz,id[maxn],lc[maxp],rc[maxp];
inline void line(int x,int y){
	if(!x||!y) return;
	nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;
}
void addedge(int now,int l,int r,int x,int p){
	if(!now) return;
	if(r<=x) {line(p,now);return;}
	int mid=(l+r)>>1;
	if(x<=mid) addedge(lc[now],l,mid,x,p);
	else line(p,lc[now]),addedge(rc[now],mid+1,r,x,p);
}
void insert(int &now,int l,int r,int x,int p){
	lc[++sz]=lc[now],rc[sz]=rc[now],line(sz,now);
	now=sz;
	if(l==r) {line(now,p);return;}
	int mid=(l+r)>>1;
	if(x<=mid) insert(lc[now],l,mid,x,p),line(now,lc[now]);
	else insert(rc[now],mid+1,r,x,p),line(now,rc[now]);
}
void build(int x[],int y[]){
	for(int i=1;i<=n;i++) id[x[i]]=i;
	rt=0;
	for(int i=1;i<=n;i++) 
		addedge(rt,1,n,y[id[i]],id[i]),insert(rt,1,n,y[id[i]],id[i]);
}

void tarjan(int u){
	dfn[u]=low[u]=++tim;
	stk[++top]=u;
	for(int i=fir[u],v;i;i=nxt[i]){
		if(!dfn[v=to[i]]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(!scc[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		++scnt;
		do{
			scc[stk[top]]=scnt;
			if(stk[top]<=n) vis[scnt]=1;
		}while(stk[top--]!=u);
	}
}
int main()
{
	//freopen("san.in","r",stdin);
	//freopen("san.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
		
	sz=n, build(a,b), build(b,c), build(c,a);
	
	for(int i=1;i<=sz;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=sz;i++)
		for(int j=fir[i];j;j=nxt[j])
			if(scc[i]!=scc[to[j]]) e[scc[i]].push_back(scc[to[j]]),in[scc[to[j]]]++;
	top=0;
	for(int i=1;i<=scnt;i++) if(!in[i]) stk[++top]=i;
	while(top){
		int u=stk[top--];
		if(vis[u]) {Ans=u;break;}
		for(int i=e[u].size()-1;i>=0;i--)
			if(!--in[e[u][i]]) stk[++top]=e[u][i];
	}
	for(int i=1;i<=n;i++) printf("%d\n",scc[i]==Ans);
}