CodeForces - 1417F Graph and Queries(克魯斯卡爾重構樹的dfs序上建線段樹)

題目鏈接：點擊查看

題目大意：給出一個 n 個點 m 條邊組成的無向圖，每個點初始時都有一個權值 val，滿足：

1. 每個點的 val[ i ] 各不相同
2. val[ i ] ∈ [ 1 , n ]

現在有 m 次操作，每次操作分為以下兩種型別：

1. 1 x：詢問點 x 所在的連通塊內 val 的最大值，設 val[ y ] 最大，輸出 val[ y ]，且進行賦值操作：val[ y ] = 0
2. 2 x：將第 x 條邊洗掉

題目分析：難點比較多，且也很具有誤導性，第一個難點就是如何處理連通塊內的最大值問題，之前我只涉及過在一棵樹上求子樹內的最大值（用線段樹維護），再就是洗掉邊的操作，很容易誤導去思考正難則反，然后倒著進行并查集

但這個題目的提示也蠻足的：可以到達的連通塊問題，這類問題其實可以轉換為克魯斯卡爾重構樹的問題

考慮克魯斯卡爾重構樹的簡化模型：對于原圖中的一條邊將其轉換為一個點與其相連，并將邊權賦給點權，如下圖所示：

因為是按照克魯斯卡爾演算法的思想去建樹的，所以相對于根節點而言，深度越淺的節點權值越大，利用這個性質就可以實作，在一個所有邊的權值不大于某個閾值的聯通塊內互相可達，來個例題？洛谷 - P4197

這樣一來就可以給每條邊賦權了，對于永遠都不會被洗掉掉的邊，賦權為 0 ，對于第 i 條被洗掉的邊，賦權為 inf - i，最后再用邊權為 inf 的邊用來聯通整個圖（因為初始時的圖不保證聯通）

建立克魯斯卡爾重構樹，在其 dfs 序上維護一棵線段樹，線段樹的作用是查找區間最大值以及其位置，這樣就可以查找某個子樹內的最大值了

于是模型轉換如下，初始時設定閾值 val = inf - 1，意為沒有一條邊被洗掉：

1. 1 x：查找點 x 在閾值 val 下所在的子樹內的最大值
2. 2 x：閾值減一，代表將第 i 條邊洗掉

代碼：

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;
     
typedef long long LL;
     
typedef unsigned long long ull;
     
const int inf=0x3f3f3f3f;
   
const int N=1e6+100;

int n,m,q;

struct Qu
{
	int op,x;
}qu[N];

struct Edge
{
	int u,v,w;
	bool operator<(const Edge& t)const
	{
		return w<t.w;
	}
}edge[N];

struct Max
{
	int val,pos;
	Max(){}
	Max(int val,int pos):val(val),pos(pos){}
	static Max inf()
	{
		return Max(-0x3f3f3f3f,0);
	}
	bool operator<(const Max& t)const
	{
		return val<t.val;
	}
};

struct Node
{
	int l,r;
	Max mmax;
}tree[N<<2];

int a[N],f[N],val[N],dp[N][25],L[N],R[N],id[N],tot;

vector<int>node[N];
/*線段樹*/
void pushup(int k)
{
	tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);
}

void build(int k,int l,int r)
{
	tree[k].l=l;
	tree[k].r=r;
	if(l==r)
	{
		tree[k].mmax.val=a[id[l]];
		tree[k].mmax.pos=l;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}

void update(int k,int pos)
{
	if(tree[k].l==tree[k].r)
	{
		tree[k].mmax.val=0;
		return;
	}
	int mid=tree[k].l+tree[k].r>>1;
	if(pos<=mid)
		update(k<<1,pos);
	else
		update(k<<1|1,pos);
	pushup(k);
}

Max query(int k,int l,int r)
{
	if(tree[k].l>r||tree[k].r<l)
		return Max::inf();
	if(tree[k].l>=l&&tree[k].r<=r)
		return tree[k].mmax;
	return max(query(k<<1,l,r),query(k<<1|1,l,r));
}
/*線段樹*/
/*dfs序+樹上倍增*/
void dfs(int u,int fa)
{
	dp[u][0]=fa;
	for(int i=1;i<=20;i++)
		dp[u][i]=dp[dp[u][i-1]][i-1];
	L[u]=++tot;
	id[tot]=u;
	for(auto v:node[u])
		dfs(v,u);
	R[u]=tot;
}

int get_pos(int u,int up)//樹上倍增找滿足的祖先 
{
	for(int i=20;i>=0;i--)
		if(dp[u][i]!=0&&val[dp[u][i]]<=up)
			u=dp[u][i];
	return u;
}
/*dfs序+樹上倍增*/
/*并查集+克魯斯卡爾重構樹*/
int find(int x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}

int Ex_Kruskal()
{
	for(int i=1;i<=n<<1;i++)
		f[i]=i;
	int index=n;
	sort(edge+1,edge+1+m);
	for(int i=1;i<=m;i++)
	{
		int xx=find(edge[i].u),yy=find(edge[i].v);
		if(xx!=yy)
		{
			f[xx]=f[yy]=++index;
			val[index]=edge[i].w;
			node[index].push_back(xx);
			node[index].push_back(yy);
		}
	}
	int last=1;
	for(int i=1;i<=n;i++)
	{
		int xx=find(last),yy=find(i);
		if(xx!=yy)
		{
			f[xx]=f[yy]=++index;
			val[index]=inf;
			node[index].push_back(xx);
			node[index].push_back(yy);
			last=index;
		}
	}
	return index;
}
/*并查集+克魯斯卡爾重構樹*/
int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&edge[i].u,&edge[i].v);
		edge[i].w=0;
	}
	int val=inf;
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&qu[i].op,&qu[i].x);
		if(qu[i].op==2)
			edge[qu[i].x].w=--val;
	}
	int root=Ex_Kruskal();
	dfs(root,0);
	build(1,1,root);
	val=inf-1;
	for(int i=1;i<=q;i++)
	{
		if(qu[i].op==1)
		{
			int x=get_pos(qu[i].x,val);
			Max ans=query(1,L[x],R[x]);
			printf("%d\n",ans.val);
			update(1,ans.pos);
		}
		else
			val--;
	}














    return 0;
}