自动搬运

查看原文

来自洛谷，原作者为

	Y25t 我从来没觉得打算法竞赛开心过。

搬运于2025-08-24 22:15:21，当前版本为作者最后更新于2020-03-09 21:44:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

二维单点修改区间求$\gcd$（题目描述得已经很清楚了吧qwq）

题解

这种二维问题大概什么树套树都能过，我这里用的是线段树套线段树，以下是一些需要注意的细节：

• 因为$R,C\leq10^9$，所以需要离散化（意味着不能强制在线）；

• 由于空间限制，里层线段树需要动态开点且只能开到$O(N_U)$大小，外层可以开到$O(N_U+N_Q)$；

• 注意$\gcd$只满足区间可加，于是每一次修改都必须从下往上依次合并；

• 本题约定$\gcd(0,a)=\gcd(a,0)=a$

时空效率$O(Nlog^2N)$（这里认为$N,N_U,N_Q$同级）

以下代码：

#include<cstdio>
#include<algorithm>
#define ll long long
#define NU 22005
#define NQ 250005

inline void rd(int &x){
	x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
}
inline void rdll(ll &x){
	x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
}

int n;
struct query{
	int opt,x1,y1,x2,y2;
	ll val;
}qry[NU+NQ];

int Valu[NU],_Valu,Valq[NU+(NQ<<1)],_Valq;
inline void unq(){
	std::sort(Valu+1,Valu+_Valu+1);
	_Valu=std::unique(Valu+1,Valu+_Valu+1)-Valu-1;
	std::sort(Valq+1,Valq+_Valq+1);
	_Valq=std::unique(Valq+1,Valq+_Valq+1)-Valq-1;
}
inline int idu(int val){
	return std::upper_bound(Valu+1,Valu+_Valu+1,val)-Valu-1;
}
inline int idq(int val){
	return std::upper_bound(Valq+1,Valq+_Valq+1,val)-Valq-1;
}

inline ll gcd(ll x,ll y){
	while(x&&y){
		ll tmp=x%y;
		x=y;
		y=tmp;
	}
	return x+y;
}

int _t;
struct node{
	int son[2];
	ll val;
}t[NU<<9];
#define lson t[p].son[0],L,mid
#define rson t[p].son[1],mid+1,R
inline void ins(int &p,int L,int R,int pos,ll val){
	if(!p)
		p=++_t;
	if(L==R){
		t[p].val=val;
		return;
	}
	int mid=(L+R)>>1;
	if(pos<=mid)
		ins(lson,pos,val);
	else
		ins(rson,pos,val);
	t[p].val=gcd(t[t[p].son[0]].val,t[t[p].son[1]].val);
}
inline void mrg(int &p,int L,int R,int q1,int q2,int pos){
	if(!p)
		p=++_t;
	if(L==R){
		t[p].val=gcd(t[q1].val,t[q2].val);
		return;
	}
	int mid=(L+R)>>1;
	if(pos<=mid)
		mrg(lson,t[q1].son[0],t[q2].son[0],pos);
	else
		mrg(rson,t[q1].son[1],t[q2].son[1],pos);
	t[p].val=gcd(t[t[p].son[0]].val,t[t[p].son[1]].val);
}
inline ll Cal(int p,int L,int R,int l,int r){
	if(!p||Valu[L]>r||Valu[R]<l)
		return 0;
	if(l<=Valu[L]&&Valu[R]<=r)
		return t[p].val;
	int mid=(L+R)>>1;
	return gcd(Cal(lson,l,r),Cal(rson,l,r));
}
#undef lson
#undef rson

int rt[(NU+(NQ<<1))<<2];
#define lson p<<1,L,mid
#define rson p<<1|1,mid+1,R
inline void mdf(int p,int L,int R,int pos,int pos2,ll val){
	if(pos<L||pos>R)
		return;
	if(L==R){
		ins(rt[p],1,_Valu,pos2,val);
		return;
	}
	int mid=(L+R)>>1;
	mdf(lson,pos,pos2,val);
	mdf(rson,pos,pos2,val);
	mrg(rt[p],1,_Valu,rt[p<<1],rt[p<<1|1],pos2);
}
inline ll cal(int p,int L,int R,int l,int r,int l2,int r2){
	if(L>r||R<l)
		return 0;
	if(l<=L&&R<=r)
		return Cal(rt[p],1,_Valu,l2,r2);
	int mid=(L+R)>>1;
	return gcd(cal(lson,l,r,l2,r2),cal(rson,l,r,l2,r2));
}
#undef lson
#undef rson

int main(){
	rd(n),rd(n),rd(n);
	for(int i=1;i<=n;i++){
		rd(qry[i].opt);
		if(qry[i].opt==1){
			rd(qry[i].x1),rd(qry[i].y1),rdll(qry[i].val);
			Valu[++_Valu]=qry[i].y1;
			Valq[++_Valq]=qry[i].x1;
		}
		else{
			rd(qry[i].x1),rd(qry[i].y1),rd(qry[i].x2),rd(qry[i].y2);
			Valq[++_Valq]=qry[i].x1;
			Valq[++_Valq]=qry[i].x2;
		}
	}
	unq();
	for(int i=1;i<=n;i++)
		if(qry[i].opt==1)
			mdf(1,1,_Valq,idq(qry[i].x1),idu(qry[i].y1),qry[i].val);
		else
			printf("%lld\n",cal(1,1,_Valq,idq(qry[i].x1),idq(qry[i].x2),qry[i].y1,qry[i].y2));
  
  #define w 0
  return ~~('0')?(0^w^0):(0*w*0);
}