骄傲无知的现代人不知道珍惜（T5）

C++ 解法, 执行用时: 2878ms, 内存消耗: 29848K, 提交时间: 2021-09-11 12:17:33
#include <bits/stdc++.h>
using namespace std;
#define M 80005
typedef long long  LL;
template<class T>bool tomax(T &x,T y){
	if(x<y)return x=y,1;
	return 0;
}
template<class T>bool tomin(T &x,T y){
	if(x>y)return x=y,1;
	return 0;
}
template<class T>void Rd(T &x){
	static char c;
	while(c=getchar(),!isdigit(c));
	for(x=0;isdigit(c);c=getchar())
		x=(x<<1)+(x<<3)+(c^48);
}
template<class T>void Ps(T x){
	if(x==0)return;
	Ps(x/10);putchar(x%10^48);
}
template<class T>void Printf(T x){
	if(x==0)putchar(48);
	else Ps(x);
	puts("");
}
bool MM1;
vector<int>num;
void exgcd(LL a,LL b,LL &x,LL &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,y,x),y-=a/b*x; 
}
LL Inv(LL a,LL b){
	LL x,y;
	exgcd(a,b,x,y);
	return (x%b+b)%b;
}
LL exCRT(LL a1,LL b1,LL a2,LL b2){
	LL MOD=a1*a2;
	return ( (b2-b1+MOD)*a1%MOD*Inv(a1,a2)+b1 )%MOD;
}
int n,q,P;
void Mul(int &x,int y){
	x=1LL*x*y%P;
}
int qikpow(int a,LL b){
	int ret=1;
	for(;b;b>>=1,Mul(a,a))
		if(b&1)Mul(ret,a);
	return ret;
}
#define calc(x,y) x=((y)+x)%P
int fec[5][1145141];
void Init(int t){
	fec[t][0]=fec[t][1]=1;
	P=num[t];
	int tmp=sqrt(P);
	if(tmp*tmp!=P)tmp=P;
	for(int i=2;i<P;i++){
		if(i%tmp!=0)fec[t][i]=1LL*fec[t][i-1]*i%P;
		else fec[t][i]=fec[t][i-1]; 
	}
}
int Ans[M];
multiset<int>ans;
vector<pair<int,int> >E[M<<2];
pair<LL,int> Fec(LL x,int p,int t){
	if(!x)return make_pair(0,1);
	pair<LL,int> ret=Fec(x/p,p,t);
	ret.first+=x/p;
	Mul(ret.second, qikpow(fec[t][P-1],x/P) );
	Mul(ret.second, fec[t][x%P] );
	return ret;
}
int C(LL a,LL b,int p,int t){
	pair<LL,int>x=Fec(a,p,t),y=Fec(b,p,t),z=Fec(b-a,p,t);
	if(y.first-x.first-z.first>=2)return 0;
	int ret=1LL*y.second*Inv(x.second,P)%P*Inv(z.second,P)%P;
	if(y.first-x.first-z.first==1)return 1LL*ret*p%P;
	return ret;
}
int exLucas(LL a,LL b){
	if(a>b)return 0;
	int p=1,ret=0;
	for(int i=0;i<num.size();i++){
		P=num[i];
		int q=sqrt(P);
		if(q*q!=P)q=P;
		int B=C(a,b,q,i);
		if(i==0)ret=B;
		else ret=exCRT(p,ret,P,B);
		p*=num[i];
	}
	return ret;
}
int Val[M];
struct UNION{
	int f[M],dep[M],sz[M];
	LL A[M];
	void Init(){
		for(int i=1;i<=n;i++)f[i]=i,dep[i]=1,sz[i]=1,A[i]=Val[i];
	}
	int find(int p){
		while(p!=f[p])p=f[p];
		return p;
	}
	struct NODE{
		int a,b,d;
		int x,y,z;
	};
	NODE stk[M];
	int top; 
	bool Merge(int a,int b){
		a=find(a),b=find(b);
		if(a==b)return 0;
		if(dep[a]>dep[b])swap(a,b);
		int x=exLucas(sz[b],A[b]),y=exLucas(sz[a],A[a]),z=exLucas(sz[a]+sz[b],A[a]+A[b]);
		ans.erase(ans.lower_bound(-x));
		ans.erase(ans.lower_bound(-y));
		ans.insert(-z);
		A[b]+=A[a],sz[b]+=sz[a];
		stk[++top]=(NODE){a,b,dep[b],x,y,z};
		tomax(dep[b],dep[a]+1);
		f[a]=b;
		return 1;
	}
	void Back(){
		NODE x=stk[top--];
		f[x.a]=x.a;
		sz[x.b]-=sz[x.a];
		A[x.b]-=A[x.a];
		dep[x.b]=x.d;
		ans.insert(-x.x);
		ans.insert(-x.y);
		ans.erase(ans.lower_bound(-x.z));
	}
}F;
void Push(int l,int r,int L,int R,pair<int,int> x,int p){
	if(l==L&&R==r)return void(E[p].push_back(x));
	int mid=l+r>>1;
	if(R<=mid)Push(l,mid,L,R,x,p<<1);
	else if(L>mid)Push(mid+1,r,L,R,x,p<<1|1);
	else Push(l,mid,L,mid,x,p<<1),Push(mid+1,r,mid+1,R,x,p<<1|1);
}
void Solve(int l,int r,int p){
	int sz=0;
	for(int i=0;i<E[p].size();i++)
		sz+=F.Merge(E[p][i].first,E[p][i].second);
	if(l==r)Ans[l]=-(*ans.begin());
	else{
		int mid=l+r>>1;
		Solve(l,mid,p<<1);
		Solve(mid+1,r,p<<1|1);
	}	
	while(sz--)F.Back();
}
int m,ID[M],mark[M],pri[M],tt;
pair<int,int>edge[M];
bool MM2;
int main(){
//	printf("%lf\n",(&MM2-&MM1)/1024.0/1024.0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int p;
	Rd(n),Rd(q),Rd(p);
	for(int i=1;i<=n;i++)Rd(Val[i]);
	for(int i=1;i<=n;i++)ans.insert(-(Val[i]%p));
	for(int i=1;i<=q;i++){
		int op,x,y;
		Rd(op);
		if(op==0){
			Rd(x),Rd(y);
			edge[++m]=make_pair(x,y);
			ID[m]=i;
		}else{
			Rd(x);
			Push(1,q,ID[x],i-1,edge[x],1);
			ID[x]=0;
		}
	}
	for(int i=1;i<=m;i++)if(ID[i]!=0)Push(1,q,ID[i],q,edge[i],1);
	int ed=sqrt(p);
	for(int i=2;i<=ed;i++){
		if(!mark[i])pri[++tt]=i;
		else continue;
		for(int j=i+i;j<=ed;j+=i)mark[j]=1;
	}
	for(int i=1;i<=tt;i++){
		int t=1;
		while(p%pri[i]==0)t*=pri[i],p/=pri[i];
		if(t>1)num.push_back(t);
	} 
	if(p>1)num.push_back(p);
	for(int i=0;i<num.size();i++)Init(i);
	F.Init();
	Solve(1,q,1);
	for(int i=1;i<=q;i++)Printf(Ans[i]);
	return 0;
}
详情
