学步园

题意：n个点m条边，q个操作 1：查询x所在集合里面的权值最大的那个点，没有输出-1。2：删除连接a~b的边。

将所有的操作保存下来，然后倒着推，建完边之后删去所有的边，然后每次遇到删边操作的时候就重新添上要删的边，（即把连接边的两点加紧同一个集合里），查询的话就是普通的并查集

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 10010;

vector <int> ve[N];
stack <int> s;

int fa[N], r[N], p[N];

struct node{
	int u, v;
}a[N * 5];
int n, m, q;

void init()
{
	while( !s.empty() )
		s.pop();
	for( int i = 1; i <= n; ++i )
	{
		fa[i] = -1;
		r[i] = 0;
		ve[i].clear();
	}
}

int bch( int x, int y )
{
	int l = 0, r = ve[x].size();
	while( l <= r )
	{
		int mid = ( l + r ) >> 1;
		if( ve[x][mid] == y )
		{
			return mid;
		}
		else if( ve[x][mid] > y )
			r = mid - 1;
		else
			l = mid + 1;
	}
}

int dfs( int x )
{
	if( fa[x] == -1 )
		return x;
	return fa[x] = dfs( fa[x] );
}

void merge( int z, int x )
{
	z = dfs( z );
	x = dfs( x );
	if( z != x )
	{
		if( p[z] > p[x] )
			fa[x] = z;
		else if( p[x] > p[z] )
			fa[z] = x;
		else
		{
			if( z < x )
				fa[x] = z;
			else
				fa[z] = x;
		}
	}
}

int main()
{
	bool t = 0;
	while( ~scanf("%d", &n) )
	{
		if( t )
			puts("");
		t = 1;
		init();
		for( int i = 1; i <= n; ++i )
			scanf("%d", &p[i]);
		int z, x;
		scanf("%d", &m);
		while( m-- )
		{
			scanf("%d%d", &z, &x);
			z++, x++;
			ve[z].push_back(x);
			ve[x].push_back(z);
		}
		for( int i = 1; i <= n; ++i )
		{
			sort( ve[i].begin(), ve[i].end() );
		}
		scanf("%d", &q);
		char op[10];
		for( int i = 1; i <= q; ++i )
		{
			scanf("%s", op);
			if( op[0] == 'd' )
			{
				scanf("%d%d", &a[i].u, &a[i].v);
				++a[i].u, ++a[i].v;
				int vv = bch( a[i].u, a[i].v );
				int uu = bch( a[i].v, a[i].u );
				int u = a[i].u, v = a[i].v;
				ve[ u ].erase( ve[ u ].begin() + vv );
				ve[ v ].erase( ve[ v ].begin() + uu );
			}
			else
			{
				scanf("%d", &a[i].u);
				++a[i].u;
				a[i].v = -1;
			}
		}
		for( int i = 1; i <= n; ++i )
		{
			int sz = ve[i].size();
			for( int j = 0; j < sz; ++j )
			{
				merge( i, ve[i][j] );
			}
		}
		for( int i = q; i; --i )
		{
			if( a[i].v == -1 )
			{
				int ani = dfs( a[i].u );
				if( p[ani] > p[ a[i].u ] )
					s.push( ani );
				else
					s.push( -1 );
			}
			else
				merge( a[i].u, a[i].v );
		}
		while( !s.empty() )
		{
			if( s.top() != -1 )
				printf("%d\n", s.top()-1);
			else
				puts("-1");
			s.pop();
		}
	}
	return 0;
}