85pts求调
查看原帖
85pts求调
257173
rish楼主2025/6/26 13:50
#include <bits/stdc++.h>
using namespace std;
#define For(i, a, b) for(int i=(a);i<=(b);i++)
#define Ror(i, a, b) for(int i=(a);i>=(b);i--)
const int N = 5e5+10;
const int NN = 4e7+10;
typedef long long ll;
int n, q, cnt, tot, tt;
int a[N], rt[N], p[N];
int head[N], ori[N];
ll sum[N];
struct Node{
	int ls, rs;
	ll num;
}f[NN];

struct Nod{
	int to, pre;
}g[N<<1];
int read()
{
	int s = 0;char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch))
	{
		s = (s<<1)+(s<<3)+(ch^48);
		ch = getchar();
	}
	return s;
}
void write(int x)
{
	if(x<0) putchar('-'), x = -x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
void add(int x, int y)
{
	g[++tot].to = y;
	if(!head[x]) ori[x] = tot;
	g[tot].pre = head[x];
	head[x] = tot;
}
void update(int &k, int l, int r, int x, int v)
{
	if(!k) k = ++cnt;
	if(l==r) return f[k].num+=1ll*v, void();
	int mid = l+r>>1;
	if(mid>=x) update(f[k].ls, l, mid, x, v);
	else update(f[k].rs, mid+1, r, x, v);
	f[k].num = f[f[k].ls].num + f[f[k].rs].num;
}
int bing(int l, int r, int x)
{
	if(l==r) return l;
	int res = 0, mid = l+r>>1;
	For(i, 1, tt) res+=f[f[p[i]].ls].num;
	if(res>=x) 
	{
		For(i, 1, tt) p[i] = f[p[i]].ls; 
		return bing(l, mid, x);
	}
	res = 0;
	For(i, 1, tt) res+=f[f[p[i]].rs].num;
	if(res>=x)
	{
		For(i, 1, tt) p[i] = f[p[i]].rs;
		return bing(mid+1, r, x);
	}
	return -1;
}
void merge(int &k1, int &k2, int l, int r)
{
	if(!k1) return k1 = k2, void();
	if(l==r) return f[k1].num+=f[k2].num, void();
	int mid = l+r>>1;
	if(f[k2].ls) merge(f[k1].ls, f[k2].ls, l, mid);
	if(f[k2].rs) merge(f[k1].rs, f[k2].rs, mid+1, r);
	f[k1].num = f[f[k1].ls].num + f[f[k1].rs].num;
}
int main()
{
	n = read(), q = read();
	For(i, 1, n)
	{
		cin >> sum[i];
		For(j, 1, sum[i])
		{
			int y = read();
			update(rt[i], 0, n+q, y, 1);
			add(i, y);
		}
	}
	For(i, 1, q)
	{
		int op = read(), x, y, z;
		if(op==1)
		{
			x = read(), y = read();
			++sum[x];
			update(rt[x], 0, n+q, y, 1);
			add(x, y);
		}
		else if(op==2)
		{
			cin >> x;
			update(rt[x], 0, n+q, g[head[x]].to, -1);
			if(head[x]==ori[x]) head[x] = ori[x] = 0;
			else head[x] = g[head[x]].pre;
			--sum[x];
		}
		else if(op==3)
		{
			tt = read();
			ll S = 0;
			For(j, 1, tt)
			{
				p[j] = read();
				S += sum[p[j]];
				p[j] = rt[p[j]];
			}
			write(bing(0, n+q, ((S>>1)+1))), puts("");
		}
		else
		{
			x = read(), y = read(), z = read();
			merge(rt[x], rt[y], 0, n+q);
			sum[z] = sum[x]+sum[y];
			rt[z] = rt[x];
			if(ori[x]) 
			{
				ori[z] = ori[x];
				if(ori[y]) g[ori[y]].pre = head[x], head[z] = head[y];
				else head[z] = head[x];
			}
			else if(ori[y]) ori[z] = ori[y], head[z] = head[y];
		}
	}
	return 0;
}
2025/6/26 13:50
加载中...