RE求调
查看原帖
RE求调
864310
zyn0309楼主2025/7/3 12:05

记录

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO{
	#define IOSIZE 100000
		char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
	#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
	#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
	#define isdigit(ch) (ch>47&&ch<58)
	#define isspace(ch) (ch<33)
		template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
		template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
		template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
		inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
		inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
		inline void print(char x) { putchar(x); }
		inline void print(char *x) { while (*x) putchar(*x++); }
		inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
		inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
		inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
		inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
		inline void print(bool b) { putchar(b+48); }
		template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
		template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
		struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
		template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
		template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
	#define cout io
	#define cin io
}using namespace fast_IO;
const int N=1e6+10;
mt19937 rnd(time(0));
int n,q,head[N],ed[N],cnt,root[N],tot,p[N],ma;
struct node{
	int val,lst,nxt;
}d[N];
inline void add(int x,int val){
	++cnt;
	d[cnt].val=val;
	if(!head[x]){
	  head[x]=ed[x]=cnt;
	  return;
	}
	d[ed[x]].nxt=cnt;
	d[cnt].lst=ed[x];
	ed[x]=cnt;
}
struct tree{
	int lson,rson,siz;
}t[N*50];
inline void update(int &u,int l,int r,int x,int val){
	if(!u)u=++tot;
	t[u].siz+=val;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)update(t[u].lson,l,mid,x,val);
	else update(t[u].rson,mid+1,r,x,val);
}
inline int query(int u,int l,int r,int x){
	if(!t[u].siz)return 0;
	if(l==r)return t[u].siz;
	int mid=(l+r)>>1;
	if(x<=mid)return query(t[u].lson,l,mid,x);
	else return query(t[u].rson,mid+1,r,x);
}
inline int merge(int a,int b){
	if(!a||!b)return a|b;
	t[a].siz+=t[b].siz;
	t[a].lson=merge(t[a].lson,t[b].lson);
	t[a].rson=merge(t[a].rson,t[b].rson);
	return a;
}
inline int kth(int u,int l,int r,int k){
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(t[t[u].lson].siz>=k)return kth(t[u].lson,l,mid,k);
	else return kth(t[u].rson,mid+1,r,k-t[t[u].lson].siz);
}
signed main(){
//	freopen("major.in","r",stdin);
//	freopen("major.out","w",stdout);
	cin>>n>>q;
	ma=n+q;
	for(int i=1;i<=n;++i){
	  int len,x;
	  cin>>len;
	  for(int j=1;j<=len;++j){
		cin>>x;
		add(i,x);
		update(root[i],1,ma,x,1);
	  }
	}
	int opt,x1,x2,x3;
	while(q--){
	  cin>>opt;
	  if(opt==1){
		cin>>x1>>x2;
		add(x1,x2);
		update(root[x1],1,ma,x2,1);
	  }
	  if(opt==2){
	  	cin>>x1;
	  	update(root[x1],1,ma,d[ed[x1]].val,-1);
	  	ed[x1]=d[ed[x1]].lst;
	  	if(!ed[x1])head[x1]=0;
	  }
	  if(opt==4){
	  	cin>>x1>>x2>>x3;
	  	if(!head[x1]||!head[x2]){
	  	  head[x3]=head[x1]|head[x2];
	  	  ed[x3]=ed[x1]|ed[x2]; 
	  	  root[x3]=root[x1]|root[x2];
	  	  continue;
		}
		d[ed[x1]].nxt=head[x2];
		d[head[x2]].lst=ed[x1];
		head[x3]=head[x1];
		ed[x3]=ed[x2];
		root[x3]=merge(root[x1],root[x2]);
	  }
	  if(opt==3){
	  	int len,siz=0;
		cin>>len;
		for(int i=1;i<=len;++i)cin>>p[i],siz+=t[root[p[i]]].siz;
		int limit=30,ans=-1;
		while(limit--){
		  int pos=rnd()%siz+1,val=0,sum=0;
		  for(int i=1;i<=len;++i){
			if(pos<=t[root[p[i]]].siz){
			  val=kth(root[p[i]],1,ma,pos);
			  break;
			}
			else pos-=t[root[p[i]]].siz;
		  }
		  for(int i=1;i<=len;++i)sum+=query(root[p[i]],1,ma,val);
		  if(sum*2>siz){
		  	ans=val;
		  	break;
		  }
		}
		cout<<ans<<"\n";
	  }
	}
	cerr<<"Time: "<<clock()/1.0/CLOCKS_PER_SEC*1000.0<<" ms\n";
	return 0;
}
2025/7/3 12:05
加载中...