记录编号	592423	评测结果	WWWWWWWWWA
题目名称	数列操作	最终得分	10
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	1.816 s
提交时间	2024-07-23 00:51:37	内存使用	22.25 MiB

//2016 吉如一论文 例题 4 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e5+10,M = N<<2;
const ll inf = 1e17;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,m; 
ll a[N];
struct STB{
	ll mx1[M],mx2[M],mi1[M],mi2[M],mic[M],mxc[M];
	ll add1[M],add2[M],add3[M],sum[M];
#define ls p<<1
#define rs p<<1|1
	void pushup(int p){
		sum[p] = sum[ls] + sum[rs];
		
		mx1[p] = max(mx1[ls],mx1[rs]);
		if(mx1[ls] > mx1[rs])mxc[p] = mxc[ls],mx2[p] = max(mx1[rs],mx2[ls]);
		else if(mx1[ls] < mx1[rs])mxc[p] = mxc[rs],mx2[p] = max(mx1[ls],mx2[rs]);
		else mxc[p] = mxc[ls] + mxc[rs],mx2[p] = max(mx2[ls],mx2[rs]);
		
		mi1[p] = min(mi1[ls],mi1[rs]);
		if(mi1[ls] < mi1[rs])mic[p] = mic[ls],mi2[p] = min(mi1[rs],mi2[ls]);
		else if(mi1[ls] > mi1[rs])mic[p] = mic[rs],mi2[p] = min(mi1[ls],mi2[rs]);
		else mic[p] = mic[ls] + mic[rs],mi2[p] = min(mi2[ls],mi2[rs]);
	}
	void update(int p,int l,int r,int k1,int k2,int k3){
		if(mx1[p] == mi1[p]){
			if(k1 || k2)sum[p] += mxc[p];
		}
		else sum[p] += (k1 == 0 ? 0:mic[p]) + (k2 == 0 ? 0:mxc[p]) + (k3 == 0 ? 0:r-l+1-mxc[p]-mic[p]);
		
		if(mi2[p] == mx1[p])mi2[p] += k2;
		else if(mi2[p] != inf) mi2[p] += k3;
		
		if(mx2[p] == mi1[p])mx2[p] += k1;
		else if(mx2[p] != -inf)mx2[p] += k3;
		
		mi1[p] += k1,mx1[p] += k2;
		add1[p] += k2,add2[p] += k2,add3[p] += k3;
	}
	void pushdown(int p,int l,int r){
		int mid = l + r >> 1;
		update(ls,l,mid,mi1[ls] == mi1[p] ? add1[p]:add3[p],mx1[ls] == mx1[p] ? add2[p]:add3[p],add3[p]);
		update(rs,mid+1,r,mi1[rs] == mi1[p] ? add1[p]:add3[p],mx1[rs] == mx1[p] ? add2[p]:add3[p],add3[p]);
		add1[p] = add2[p] = add3[p] = 0;
	}
	void build(int p,int l,int r){
		if(l == r){
			mi1[p] = mx1[p] = a[l],mic[p] = mxc[p] = 1;
			mi2[p] = inf,mx2[p] = -inf;return; 
		}
		int mid = l + r >> 1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushup(p); 
	}
	void modify1(int p,int l,int r,int L,int R,int k){
		if(k <= mi1[p])return;
		if(L <= l && r <= R && k > mi1[p] && k < mi2[p])return update(p,l,r,k-mi1[p],0,0),void();
		int mid = l + r >> 1;
		pushdown(p,l,r);
		if(L <= mid)modify1(ls,l,mid,L,R,k);
		if(R > mid)modify1(rs,mid+1,r,L,R,k);
		pushup(p);
	}
	void modify2(int p,int l,int r,int L,int R,int k){
		if(k >= mx1[p])return;
		if(L <= l && r <= R && k < mx1[p] && k > mx2[p])return update(p,l,r,0,k-mx1[p],0),void();
		int mid = l + r >> 1; 
		pushdown(p,l,r);
		if(L <= mid)modify2(ls,l,mid,L,R,k);
		if(R > mid)modify2(rs,mid+1,r,L,R,k);
		pushup(p);
	}
	void modify3(int p,int l,int r,int L,int R,int k){
		if(L <= l && r <= R)return update(p,l,r,k,k,k);
		int mid = l + r >> 1;
		pushdown(p,l,r);
		if(L <= mid)modify3(ls,l,mid,L,R,k);
		if(R > mid)modify3(rs,mid+1,r,L,R,k);
		pushup(p);
	} 
	ll cal(int p,int l,int r,int L,int R){
		if(L <= l && r <= R)return sum[p];
		int mid = l + r >> 1;
		pushdown(p,l,r);
		if(R <= mid)return cal(ls,l,mid,L,R);
		else if(L > mid)return cal(rs,mid+1,r,L,R);
		else return cal(ls,l,mid,L,R) + cal(rs,mid+1,r,L,R); 
	}
}t;


int main(){
	freopen("hihocoderD.in","r",stdin);
	freopen("hihocoderD.out","w",stdout);
	n = read(),m = read();
	for(int i = 1;i <= n;i++)a[i] = read();
	t.build(1,1,n);
	for(int i = 1;i <= m;i++){
		int op = read(),l = read(),r = read(),k;
		if(op <= 3)k = read();
		if(op == 1)t.modify1(1,1,n,l,r,k);
		else if(op == 2)t.modify2(1,1,n,l,r,k);
		else if(op == 3)t.modify3(1,1,n,l,r,k);
		else printf("%lld\n",t.cal(1,1,n,l,r));
	}

	return 0;

}