题解 P5893 【[IOI2013]game 游戏】
题目大意
二维单点修改区间求题目描述得已经很清楚了吧qwq）
题解
这种二维问题大概什么树套树都能过，我这里用的是线段树套线段树，以下是一些需要注意的细节：
-
因为
R,C\leq10^9 ，所以需要离散化（意味着不能强制在线）； -
由于空间限制，里层线段树需要动态开点且只能开到
O(N_U) 大小，外层可以开到O(N_U+N_Q) ； -
注意
\gcd 只满足区间可加，于是每一次修改都必须从下往上依次合并； -
本题约定
\gcd(0,a)=\gcd(a,0)=a
时空效率
以下代码：
#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);
}