NOIP镇海模拟赛 11.10

, , , , ,

今天感觉什么也没模拟。

但还是挂大分了啊。T1 没和长度取 $\min$ 挂了 $50$，T3 乱搞本来可以过原题的，但是因为 return puts("-1"); 还有最大值开 1e16 开小了被卡了，遗憾离场。

T1

Description

不想写了，水题，代码也不想贴了。

T2

Description

image-20231110150843716

$n\le 10^6$

4s

Solution

好题，指科技上。

首先考虑双指针，按 $c_i$ 排序以后，枚举左端点，找满足条件的最小右端点。

此时只需要判断可不可以。所以我们对题目进行一个转化：

  • 给定 $l,r,v$ ，将 $[l,r]$ 中 $h_i\le v_i$ 都变为 $0$。
  • 查询当且集合中的 $h_i$ 是否为 $0$。
  • 删除最早的一个操作。

先不考虑删除。只需要对线段树上的节点维护对应区间 $h_i$ 的最大值与将对应区间内所有 $\ge v$ 的 $h$ 变为 $0$ 的懒标记。

但是有删除就很烦啊。考虑标记永久化，每个节点维护一个单调队列，删除标记就可以做啦！

时空复杂度均为 $O(n\log n)$。

具体实现上，如果每个节点开 vector 或者 list （我也没用过这个）显然是不太可以的，所以可以开个内存池，然后先预处理出每个节点最多需要多少个内存，分配一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int m,n;
const int inf=1e9;
struct yyy {
	int l,r,c,v;
}a[maxn];
int d[maxn];
bool cmp(yyy x,yyy y) {return x.c<y.c;}
int HH;
namespace seg {
	int siz[maxn<<2],f[maxn<<2],Max[maxn<<2];
	int cnt;
	pair<int,int> buff[maxn*60];
	int hd[maxn<<2],tl[maxn<<2];
	pair<int,int> *q[maxn<<2],*tq=buff;
	void modify(int l,int r,int rt,int head,int tail) {
		if (head<=l&&r<=tail) return siz[rt]++,void();
		int mid=l+r>>1;
		if (head<=mid) modify(l,mid,rt<<1,head,tail);
		if (tail>mid)  modify(mid+1,r,rt<<1|1,head,tail);
	}
 	void pushup(int l,int r,int rt) {
		if (l==r) f[rt]=Max[rt];else f[rt]=max(f[rt<<1],f[rt<<1|1]);
		if (hd[rt]<=tl[rt]&&q[rt][hd[rt]].se>=HH&&q[rt][hd[rt]].fi>=f[rt]) f[rt]=0;
	}  
	void build(int l,int r,int rt) {
		q[rt]=tq,tq+=siz[rt]+2;hd[rt]=1,tl[rt]=0;
		if (l==r) return f[rt]=Max[rt]=d[l],void();
		int mid=l+r>>1;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
		Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
		pushup(l,r,rt);
	}
	void Update(int l,int r,int rt,int head,int tail,int fl,int k=0,int t=0) {
		if (head<=l&&r<=tail) {
			while (hd[rt]<=tl[rt]&&q[rt][hd[rt]].se<HH) hd[rt]++;
			if (fl==1) {
				while (hd[rt]<=tl[rt]&&q[rt][tl[rt]].fi<=k) tl[rt]--;
				q[rt][++tl[rt]]=mk(k,t);			
			}
			pushup(l,r,rt);
//			gdb(l,r,head,tail,fl,k,t,f[rt],q[rt][hd[rt]].fi,hd[rt],tl[rt],HH);
			return ;
		}
		int mid=l+r>>1;
		if (head<=mid) Update(l,mid,rt<<1,head,tail,fl,k,t);
		if (tail>mid)  Update(mid+1,r,rt<<1|1,head,tail,fl,k,t);
		pushup(l,r,rt);
//		gdb(l,r,head,tail,fl,k,t,f[rt],q[rt][hd[rt]].fi,hd[rt],tl[rt],HH);
	}
}
int ans=inf+100000;
signed main(void){
	int i,j;
	read(m);read(n);
	for (i=1;i<=n;i++) {
		read(a[i].l),read(a[i].r),read(a[i].c),read(a[i].v);
		seg::modify(1,m,1,a[i].l,a[i].r);
	}
	for (i=1;i<=m;i++) read(d[i]); 
	seg::build(1,m,1);
//	gdb(seg::f[1]);
	sort(a+1,a+1+n,cmp);
//	for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) if (a[j].c-a[i].c==182985819) gdb(i,j);
	j=0;
//	for (i=1;i<=n;i++) gdb(i,a[i].l,a[i].r,a[i].c,a[i].v);
	for (i=1;i<=n;i++) {
		HH=i;
		while (j<n&&seg::f[1]>0) j++,seg::Update(1,m,1,a[j].l,a[j].r,1,a[j].v,j); 
		if (j==n&&seg::f[1]>0) break;
		ans=min(ans,a[j].c-a[i].c);
		HH=i+1;
		seg::Update(1,m,1,a[i].l,a[i].r,-1);
//		gdb(i,j,a[i].c,a[j].c,seg::f[1]);
	}
	printf("%d",ans>=inf?-1:ans);
	return 0;
}

T3

Description

image-20231110151744991 $n\le 2\times 10^6$

4s。

Solution

套皮的期望。实际上就是求一条路径，使得每个点到这个路径上的和权值最小。

注意到关键在于恰好 $k$ 座城市。首先先把无解判了。

如果 $k=1$，换根做一下就好。

显然我们有一个 $O(n^2)$ 暴力和一个大常数的 $O(n\log n)$ 的点分治。

考虑以 $1$ 为根。假如我们有一个答案，实际上就是一条长度为 $k$ 的路径。我们枚举路径的 lca。观察到我们根确定了，一条边的对答案的贡献就是减去边的权值乘上子树大小，这个值是确定的，可以做一个对根的前缀和。

问题就转化为了每个点有一个权值，求在一个点的子树内两个不同子树构成的长度为 $k$ 的路径的权值的最大值。用长链剖分优化。复杂度 $O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 4000005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=998244353;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
const int inf=1e18;
int n,m;
int h[maxn],head=1;
struct yyy {
	int to,z,w;
	void add(int x,int y,int val) {
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn*2];
int dp[maxn],g[maxn];
int siz[maxn],fw[maxn],dis[maxn],deep[maxn],son[maxn];
void dfs(int x,int pre) {
	int i;siz[x]=1;deep[x]=1;
	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
		dfs(a[i].to,x);
		siz[x]+=siz[a[i].to];
		deep[x]=max(deep[x],deep[a[i].to]+1);
		dp[x]+=dp[a[i].to]+siz[a[i].to]*a[i].w;
		if (deep[x]==deep[a[i].to]+1) son[x]=a[i].to;
	}
}
int t[maxn],Ans=inf;
void dfs2(int x,int pre) {
	int i;
	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
		dis[a[i].to]=dis[x]+siz[a[i].to]*a[i].w;
		g[a[i].to]=g[x]+(n-2*siz[a[i].to])*a[i].w;
		dfs2(a[i].to,x);
	}
}
int anss=0,p[maxn];
void dfs4(int x,int pre) {
	int i,Max=0,Maxx=0;p[x]=1;
	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
		dfs4(a[i].to,x);
		if (p[a[i].to]>=Max) Maxx=Max,Max=p[a[i].to];
		else if (p[a[i].to]>=Maxx) Maxx=p[a[i].to]; 
	}
	p[x]=Max+1;
	anss=max(anss,Max+Maxx+1);
}
int buff[maxn],*f[maxn],*pf=buff;
void dfs3(int x,int pre) {
	int i,j;
	if (son[x]) {
		f[son[x]]=f[x]+1;
		dfs3(son[x],x);	
	}
	f[x][0]=dis[x];
	int ans=0;
	for (i=h[x];i;i=a[i].z) if (a[i].to!=son[x]&&a[i].to!=pre) {
		f[a[i].to]=pf;pf+=deep[a[i].to]+1;
		dfs3(a[i].to,x);
		for (j=0;j<deep[a[i].to];j++) if (m-j-2<=deep[x]&&m-j-2>=0) ans=max(ans,f[x][m-j-2]+f[a[i].to][j]-dis[x]*2);
		for (j=0;j<deep[a[i].to];j++) f[x][j+1]=max(f[x][j+1],f[a[i].to][j]);
	}
	if (deep[x]>=m) ans=max(ans,f[x][m-1]-dis[x]);
	Ans=min(Ans,g[x]-ans);
}
signed main(void){
	int i,x,y,z;
	read(n);read(m);
	for (i=1;i<n;i++) {
		read(x),read(y),read(z);
		a[++head].add(x,y,z);
		a[++head].add(y,x,z);
	}
	dfs4(1,0);
	if (anss<m) return puts("-1"),0;
	dfs(1,0);
	g[1]=dp[1];
	dfs2(1,0);
	f[1]=pf;pf+=deep[1]+1;
	dfs3(1,0);
	printf("%lld",Ans%mod*power(n)%mod);
	return 0;
}

顺便贴一下赛时丑陋乱搞。但是忘记判 $k$ 不是恰好等于的情况了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 4000005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=998244353;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
const int inf=1e18;
int head=1,h[maxn],n,k,top[maxn];
struct yyy {
	int to,z,w;
	void add(int x,int y,int val) {
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn*2];
int deep[maxn],siz[maxn],dis[maxn],g[maxn],fa[maxn],fw[maxn],son[maxn];
void dfs(int x,int pre) {
	int i;son[x]=0;siz[x]=1;dis[x]=0;deep[x]=deep[pre]+1;fa[x]=pre;
	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
		fw[a[i].to]=a[i].w;
		dfs(a[i].to,x);
		if (!son[x]||siz[son[x]]<siz[a[i].to]) son[x]=a[i].to;
		siz[x]+=siz[a[i].to];
		dis[x]+=dis[a[i].to]+siz[a[i].to]*a[i].w;
	}
}
int f[maxn];
void dfs2(int x,int pre) {
	int i;f[x]=dis[x];
	if (deep[x]==k) return f[x]=dis[x],void();
	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
		dfs2(a[i].to,x);
		f[x]=min(f[x],f[a[i].to]+dis[x]-dis[a[i].to]-siz[a[i].to]*a[i].w);
	}
}
void dfs3(int x,int pre) {
	int i;
	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
		g[a[i].to]=(g[x]-siz[a[i].to]*fw[a[i].to])+(n-siz[a[i].to])*fw[a[i].to];
		dfs3(a[i].to,x);
	} 
}
int anss=0;
void dfs4(int x,int pre) {
	int i,Max=0,Maxx=0;f[x]=1;
	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
		dfs4(a[i].to,x);
		if (f[a[i].to]>=Max) Maxx=Max,Max=f[a[i].to];
		else if (f[a[i].to]>=Maxx) Maxx=f[a[i].to]; 
	}
	f[x]=Max+1;
	anss=max(anss,Max+Maxx+1);
}
void dfs5(int x,int pre,int u) {
	int i;deep[x]=deep[pre]+1;
	if (u==0&&pre) u=x;top[x]=u; 
	if (deep[x]==k) return void();
	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) {
		if (u) g[a[i].to]=g[x]-a[i].w*siz[a[i].to]; 
		f[a[i].to]=f[x]-a[i].w*siz[a[i].to];
//		gdb(x,a[i].to,f[a[i].to]);
		dfs5(a[i].to,x,u);
	}
}
pair<int,int> t1[maxn],t2[maxn];
int calc(int rt) {
	int i;
	dfs(rt,0);
	for (i=1;i<=n;i++) {
		t1[i]=mk(inf,0);
		t2[i]=mk(inf,0);
		g[i]=dis[i];f[i]=dis[i];
	}
	fw[rt]=0;
	dfs5(rt,0,0);
	f[rt]=dis[rt];
//	gdb(rt,dis[rt]);
	int ans=inf,Min=inf;
	for (i=1;i<=n;i++) if (deep[i]<=k) {
		ans=min(ans,f[i]);
		g[i]=g[i]-dis[top[i]]-siz[top[i]]*fw[top[i]];
		Min=min(Min,g[i]);
//		gdb(i,f[i],g[i],top[i]);
		if (t1[deep[i]].fi>=g[i]) {
			if (t2[deep[i]].se!=t1[deep[i]].se&&t1[deep[i]].se!=top[i]) t2[deep[i]]=t1[deep[i]]; 
			t1[deep[i]]=mk(g[i],top[i]);
		} 
		else if (t2[deep[i]].fi>=g[i]&&t1[deep[i]].se!=top[i]) {
			t2[deep[i]]=mk(g[i],top[i]);
		}
//		gdb(t1[deep[i]].fi,t1[deep[i]].se,t2[deep[i]].fi,t2[deep[i]].se,top[i]);
//		if (t1[deep[i]].se==t2[deep[i]].se&&t2[deep[i]].se) exit(-1);
	}
	for (i=1;i<=n;i++) if (deep[i]<=k) {
		int tmp=k+1-deep[i];
		if (t1[tmp].se!=top[i]) ans=min(ans,t1[tmp].fi+f[i]);
		else //if (t2[tmp].se!=top[i]) 
		ans=min(ans,t2[tmp].fi+f[i]);//,gdb(i,top[i],t2[tmp].se,t1[tmp].se);
	}
//	gdb(ans,rt,Min,dis[rt]);
	return ans;
}
signed main(void){
	int i,x,y,z;int ans=inf;
	read(n);read(k);
	double tt=clock();
	for (i=1;i<n;i++) {
		read(x),read(y),read(z);
		a[++head].add(x,y,z);
		a[++head].add(y,x,z);
	}
	dfs4(1,0);if (anss<k) return puts("-1"),0;
	if (n<=3000) {
		for (i=1;i<=n;i++) {
			dfs(i,0);
			dfs2(i,0);
			ans=min(ans,f[i]);
		}		
		printf("%lld\n",ans%mod*power(n)%mod);
		return 0;
	}
	
	dfs(1,0);
	g[1]=dis[1];
	dfs3(1,0);
	int rt=0;
	for (rt=1,i=1;i<=n;i++) {
		if (g[rt]>g[i]) rt=i;
	} 
	//find root
	mt19937 rnd(time(0));
	ans=calc(rt);
	dfs(1,0);
	for (rt=1,i=1;i<=n;i++) {
		if (max(siz[son[rt]],n-siz[rt])>max(siz[son[i]],n-siz[i])) rt=i;
	}
	ans=min(ans,calc(rt));
	while (1.0*(clock()-tt)/CLOCKS_PER_SEC<3) {
		int rt=rnd()%n+1;
		ans=min(ans,calc(rt));
	}
	gdb(ans);
	printf("%lld\n",ans%mod*power(n)%mod);
	return 0;
}

T4

Description

image-20231110152858174

$n,q\le 2.5\times 10^5$

1s。

Solution

和 https://www.luogu.com.cn/problem/P8959 一样的套路，最大公约数不是真的最大公约数。离线下来，对操作差分一下，按位置从左到右扫，然后线段树维护操作序列，扫描线一下即可。

我比较 nt，跟上面一道题写的一样是线段树合并。不想管了反正过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 300005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,q;
int gcd(int x,int y) {return !y?x:gcd(y,x%y);}
struct node {
	int ls,rs,sum,g;
}f[maxn*60];
int root[maxn];
int a[maxn],cnt,vis[maxn],Ans[maxn];
vector<pair<int,int> > O[maxn];
void pushup(int rt) {
	f[rt].sum=f[f[rt].ls].sum+f[f[rt].rs].sum;
	f[rt].g=gcd(f[f[rt].ls].g,f[f[rt].rs].g);
}
void Update(int l,int r,int &rt,int head,int k) {
	if (!rt) rt=++cnt;
	if (l==r) return f[rt].sum=f[rt].g=k,void();
	int mid=l+r>>1;
	if (head<=mid) Update(l,mid,f[rt].ls,head,k);
	else Update(mid+1,r,f[rt].rs,head,k);
	pushup(rt);
}
int qsum(int l,int r,int &rt,int head,int tail) {
	if (!rt) return 0;
	if (head<=l&&r<=tail) return f[rt].sum;
	int mid=l+r>>1,sum=0;
	if (head<=mid) sum+=qsum(l,mid,f[rt].ls,head,tail);
	if (tail>mid) sum+=qsum(mid+1,r,f[rt].rs,head,tail);
	return sum;
}
int qgcd(int l,int r,int &rt,int head,int tail) {
	if (!rt) return 0;
	if (head<=l&&r<=tail) return f[rt].g;
	int mid=l+r>>1,tmp1=0,tmp2=0;
	if (head<=mid) tmp1=qgcd(l,mid,f[rt].ls,head,tail);
	if (tail>mid) tmp2=qgcd(mid+1,r,f[rt].rs,head,tail);
	return gcd(tmp1,tmp2);
}
int merge(int l,int r,int x,int y) {
	if (!x||!y) return x+y;
	if (l==r) {
		f[x].sum+=f[y].sum;
		f[x].g=f[x].sum;
		return x;
	}
	int mid=l+r>>1;
	f[x].ls=merge(l,mid,f[x].ls,f[y].ls);
	f[x].rs=merge(mid+1,r,f[x].rs,f[y].rs);
	pushup(x);
	return x;
}
signed main(void){
	int i,op,l,r,x;
	read(n),read(q);
	for (i=1;i<=n;i++) read(a[i]),Update(0,q,root[i],0,a[i]-a[i-1]);
	for (i=1;i<=q;i++) {
		read(op);
		if (op==1) {
			read(l);read(r);read(x);
			Update(0,q,root[l],i,x);
			if (r<n) Update(0,q,root[r+1],i,-x);
		}
		else {
			read(l);read(x);
			O[l].push_back(mk(x,i));
			vis[i]=1;
		}
	}
	for (i=1;i<=n;i++) {
		for (auto tmp:O[i]) {
			int tmp1=qsum(0,q,root[i],0,tmp.fi-1);
			int tmp2=qgcd(0,q,root[i],tmp.fi,tmp.se);
			Ans[tmp.se]=abs(gcd(tmp1,tmp2));
		}
		if (i<n) root[i+1]=merge(0,q,root[i+1],root[i]);
	}
	for (i=1;i<=q;i++) if (vis[i]) printf("%lld\n",Ans[i]);
	return 0;
}