记录编号	578425	评测结果	AAAAAAAAAA
题目名称	[雅礼集训 2017 Day1] 市场	最终得分	100
用户昵称	zxhhh	是否通过	通过
代码语言	C++	运行时间	7.340 s
提交时间	2023-03-14 20:44:26	内存使用	13.09 MiB

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 5;
 
int n, q;
ll a[N];
 
inline ll read () {
	ll num = 0; int f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') num = (num<<1)+(num<<3)+(ch^48), ch = getchar();
	return num*f; 
}
 
ll get_chu (ll x, ll k) {
	if (x >= 0) return x/k;
	return (x-k+1)/k;
}
 
struct node {
	ll s, add, maxn, minn;
}nodes[N << 2];
 
inline void upd (int p, int l, int r, ll k) {
	nodes[p].s +=  k*(r-l+1);
	nodes[p].maxn += k; nodes[p].minn += k; nodes[p].add += k;
}
 
inline void push_up (int p) {
	nodes[p].s = nodes[p<<1].s+nodes[p<<1|1].s;
	nodes[p].minn = min(nodes[p<<1].minn, nodes[p<<1|1].minn);
	nodes[p].maxn = max(nodes[p<<1].maxn, nodes[p<<1|1].maxn); 
}
 
inline void push_down (int p, int l, int r) {
	int mid = (l+r)>>1;
	upd(p<<1, l, mid, nodes[p].add); upd(p<<1|1, mid+1, r, nodes[p].add);
	nodes[p].add = 0;
}
 
void build (int p, int l, int r) {
	if (l == r) {
		nodes[p].s = nodes[p].maxn = nodes[p].minn = a[l];
		return;
	}
	int mid = (l+r)>>1;
	build (p<<1, l, mid); build (p<<1|1, mid+1, r);
	push_up(p);
}
 
void add (int p, int l, int r, int tl, int tr, ll k) {
	if (l >= tl && r <= tr) {
		upd(p, l, r, k);
		return;
	}
	push_down(p, l, r);
	int mid = (l+r)>>1;
	if (tl <= mid) add(p<<1, l, mid, tl, tr, k);
	if (tr > mid) add(p<<1|1, mid+1, r, tl, tr, k);
	push_up(p);
}
 
void chu (int p, int l, int r, int tl, int tr, ll k) {
	if (l >= tl && r <= tr && get_chu(nodes[p].maxn, k)-nodes[p].maxn == get_chu(nodes[p].minn, k)-nodes[p].minn) {
		upd(p, l, r, get_chu(nodes[p].minn, k) - nodes[p].minn);
//		upd(p, l, r, get_chu(nodes[p].minn, k) - nodes[p].minn);
		return;
//		nodes[p].maxn = nodes[p].minn = get_chu(nodes[p].maxn, k);
//		nodes[p].s = get_chu(nodes[p].maxn, k)*(r-l+1);
	} 
	int mid = (l+r)>>1;
	push_down(p, l, r);
	if (tl <= mid) chu(p<<1, l, mid, tl, tr, k); if (tr > mid) chu(p<<1|1, mid+1, r, tl, tr, k);
	push_up(p);
}
 
ll minn (int p, int l, int r, int tl, int tr) {
	if (l >= tl && r <= tr) return nodes[p].minn;
	int mid = (l+r)>>1; ll res = 0x3f3f3f3f3f3f3f3f;
	push_down(p, l, r);
	if (tl <= mid) res = minn(p<<1, l, mid, tl, tr);
	if (tr > mid) res = min(res, minn(p<<1|1, mid+1, r, tl, tr)); 
	return res;
}
 
ll sum (int p, int l, int r, int tl, int tr) {
	if (l >= tl && r <= tr) return nodes[p].s;
	int mid = (l+r)>>1; ll res = 0;
	push_down(p, l, r);
	if (tl <= mid) res += sum(p<<1, l, mid, tl, tr); if (tr > mid) res += sum(p<<1|1, mid+1, r, tl, tr);
	return res; 
}
 
int main () {
	freopen("2017market.in", "r", stdin);
	freopen("2017market.out", "w", stdout);
	n = read(); q=  read();
	for (int i = 1;i <= n;i++) a[i] = read();
	build (1, 1, n);
	while (q--) {
		int op = read(), l =read(), r = read(); ll k;
		l++; r++;
		if (op == 1) {
			k = read();
			add(1, 1, n, l, r, k); 
		}
		else if (op == 2) {
			k = read();
			chu(1, 1, n, l, r, k);
		}
		else if (op == 3) printf("%lld\n", minn(1, 1, n, l, r));
		else printf("%lld\n", sum(1, 1, n, l, r));
//		cout << sum(1, 1, n, 1, n) << endl;
	}
	return 0;
}