Description：

区间加，区间除并向下取整，区间取 $\min$ ，区间求和。

$1\leqslant n\leqslant 10^5$

Solution：

线段树，维护一个 $min$ 和一个 $max$ ，最大的问题在于区间除怎么更新 $sum$ ，因为向下取整是没法整体更新的，也就不能打标记，由于最多除 $\log$ 次就除完了，所以重要的是要在适当的时候不向下更新。

题解的做法是维护一个再 $\max$ ，区间除的时候 $\max$ 相当于减了 $\max-\lfloor\frac \max k\rfloor$ ， $\min$ 相当于减了 $\min-\lfloor\frac \min k\rfloor$ ，如果他们相同，那就直接做一个区间减法退出，否则递归下去。

时间复杂度应该是 $O(n\log^2n)$ 吧。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,q;

#define MAXN 100010

typedef long long ll;

ll a[MAXN];

struct node

{

	int lc,rc;

	ll minv,maxv,sum,tag;

}t[MAXN << 1];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	t[rt].tag = 0;

	if(l == r)

	{

		t[rt].sum = t[rt].maxv = t[rt].minv = a[l];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	return;

}

inline void pushdown(int rt,int l,int r)

{

	t[t[rt].lc].tag += t[rt].tag;

	t[t[rt].lc].minv += t[rt].tag;t[t[rt].lc].maxv += t[rt].tag;

	t[t[rt].lc].sum += (mid - l + 1) * t[rt].tag;

	t[t[rt].rc].tag += t[rt].tag;

	t[t[rt].rc].minv += t[rt].tag;t[t[rt].rc].maxv += t[rt].tag;

	t[t[rt].rc].sum += (r - mid) * t[rt].tag;

	t[rt].tag = 0;

	return;

}

void add(int rt,int L,int R,ll k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].sum += (r - l + 1) * k;

		t[rt].minv += k;t[rt].maxv += k;

		t[rt].tag += k;

		return;

	}

	pushdown(rt,l,r);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	return;

}

void div(int rt,int L,int R,ll k,int l,int r)

{

	if(L <= l && r <= R)

	{

		if((t[rt].maxv - (ll)floor(double(t[rt].maxv) / k)) == (t[rt].minv - (ll)floor(double(t[rt].minv) / k)))

		{

			add(rt,l,r,-(t[rt].maxv - (ll)floor(double(t[rt].maxv) / k)),l,r);

			return;

		}

	}

	pushdown(rt,l,r);

	if(L <= mid)div(t[rt].lc,L,R,k,l,mid);

	if(R > mid)div(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	return;

}

ll calc_min(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].minv;

	register ll minv = 0x3f3f3f3f;

	pushdown(rt,l,r);

	if(L <= mid)minv = min(minv,calc_min(t[rt].lc,L,R,l,mid));

	if(R > mid)minv = min(minv,calc_min(t[rt].rc,L,R,mid + 1,r));

	return minv;

}

ll calc_sum(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].sum;

	register ll res = 0;

	pushdown(rt,l,r);

	if(L <= mid)res += calc_sum(t[rt].lc,L,R,l,mid);

	if(R > mid)res += calc_sum(t[rt].rc,L,R,mid + 1,r);

	return res;

}

int main()

{

	scanf("%d%d",&n,&q);

	for(register int i = 1;i <= n;++i)a[i] = rd();

	build(root,1,n);

	register int opt,l,r;

	register ll x;

	for(register int i = 1;i <= q;++i)

	{

		opt = rd();l = rd();r = rd();

		++l;++r;

		if(opt == 1)

		{

			x = rd();

			add(root,l,r,x,1,n);

		}

		if(opt == 2)

		{

			x = rd();

			div(root,l,r,x,1,n);

		}

		if(opt == 3)

		{

			printf("%lld\n",calc_min(root,l,r,1,n));

		}

		if(opt == 4)

		{

			printf("%lld\n",calc_sum(root,l,r,1,n));

		}

	}

	return 0;

}