题目大意
二维单点修改区间求$\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$同级）
以下代码：
1 #include<cstdio>
2 #include<algorithm>
3 #define ll long long
4 #define NU 22005
5 #define NQ 250005
6
7 inline void rd(int &x){
8 x=0;
9 char c=getchar();
10 while(c<'0'||c>'9')
11 c=getchar();
12 while(c>='0'&&c<='9'){
13 x=x*10+c-'0';
14 c=getchar();
15 }
16 }
17 inline void rdll(ll &x){
18 x=0;
19 char c=getchar();
20 while(c<'0'||c>'9')
21 c=getchar();
22 while(c>='0'&&c<='9'){
23 x=x*10+c-'0';
24 c=getchar();
25 }
26 }
27
28 int n;
29 struct query{
30 int opt,x1,y1,x2,y2;
31 ll val;
32 }qry[NU+NQ];
33
34 int Valu[NU],_Valu,Valq[NU+(NQ<<1)],_Valq;
35 inline void unq(){
36 std::sort(Valu+1,Valu+_Valu+1);
37 _Valu=std::unique(Valu+1,Valu+_Valu+1)-Valu-1;
38 std::sort(Valq+1,Valq+_Valq+1);
39 _Valq=std::unique(Valq+1,Valq+_Valq+1)-Valq-1;
40 }
41 inline int idu(int val){
42 return std::upper_bound(Valu+1,Valu+_Valu+1,val)-Valu-1;
43 }
44 inline int idq(int val){
45 return std::upper_bound(Valq+1,Valq+_Valq+1,val)-Valq-1;
46 }
47
48 inline ll gcd(ll x,ll y){
49 while(x&&y){
50 ll tmp=x%y;
51 x=y;
52 y=tmp;
53 }
54 return x+y;
55 }
56
57 int _t;
58 struct node{
59 int son[2];
60 ll val;
61 }t[NU<<9];
62 #define lson t[p].son[0],L,mid
63 #define rson t[p].son[1],mid+1,R
64 inline void ins(int &p,int L,int R,int pos,ll val){
65 if(!p)
66 p=++_t;
67 if(L==R){
68 t[p].val=val;
69 return;
70 }
71 int mid=(L+R)>>1;
72 if(pos<=mid)
73 ins(lson,pos,val);
74 else
75 ins(rson,pos,val);
76 t[p].val=gcd(t[t[p].son[0]].val,t[t[p].son[1]].val);
77 }
78 inline void mrg(int &p,int L,int R,int q1,int q2,int pos){
79 if(!p)
80 p=++_t;
81 if(L==R){
82 t[p].val=gcd(t[q1].val,t[q2].val);
83 return;
84 }
85 int mid=(L+R)>>1;
86 if(pos<=mid)
87 mrg(lson,t[q1].son[0],t[q2].son[0],pos);
88 else
89 mrg(rson,t[q1].son[1],t[q2].son[1],pos);
90 t[p].val=gcd(t[t[p].son[0]].val,t[t[p].son[1]].val);
91 }
92 inline ll Cal(int p,int L,int R,int l,int r){
93 if(!p||Valu[L]>r||Valu[R]<l)
94 return 0;
95 if(l<=Valu[L]&&Valu[R]<=r)
96 return t[p].val;
97 int mid=(L+R)>>1;
98 return gcd(Cal(lson,l,r),Cal(rson,l,r));
99 }
100 #undef lson
101 #undef rson
102
103 int rt[(NU+(NQ<<1))<<2];
104 #define lson p<<1,L,mid
105 #define rson p<<1|1,mid+1,R
106 inline void mdf(int p,int L,int R,int pos,int pos2,ll val){
107 if(pos<L||pos>R)
108 return;
109 if(L==R){
110 ins(rt[p],1,_Valu,pos2,val);
111 return;
112 }
113 int mid=(L+R)>>1;
114 mdf(lson,pos,pos2,val);
115 mdf(rson,pos,pos2,val);
116 mrg(rt[p],1,_Valu,rt[p<<1],rt[p<<1|1],pos2);
117 }
118 inline ll cal(int p,int L,int R,int l,int r,int l2,int r2){
119 if(L>r||R<l)
120 return 0;
121 if(l<=L&&R<=r)
122 return Cal(rt[p],1,_Valu,l2,r2);
123 int mid=(L+R)>>1;
124 return gcd(cal(lson,l,r,l2,r2),cal(rson,l,r,l2,r2));
125 }
126 #undef lson
127 #undef rson
128
129 int main(){
130 rd(n),rd(n),rd(n);
131 for(int i=1;i<=n;i++){
132 rd(qry[i].opt);
133 if(qry[i].opt==1){
134 rd(qry[i].x1),rd(qry[i].y1),rdll(qry[i].val);
135 Valu[++_Valu]=qry[i].y1;
136 Valq[++_Valq]=qry[i].x1;
137 }
138 else{
139 rd(qry[i].x1),rd(qry[i].y1),rd(qry[i].x2),rd(qry[i].y2);
140 Valq[++_Valq]=qry[i].x1;
141 Valq[++_Valq]=qry[i].x2;
142 }
143 }
144 unq();
145 for(int i=1;i<=n;i++)
146 if(qry[i].opt==1)
147 mdf(1,1,_Valq,idq(qry[i].x1),idu(qry[i].y1),qry[i].val);
148 else
149 printf("%lld\n",cal(1,1,_Valq,idq(qry[i].x1),idq(qry[i].x2),qry[i].y1,qry[i].y2));
150
151 #define w 0
152 return ~~('0')?(0^w^0):(0*w*0);
153 }