一、题目：
二、思路：
这将是我NOIP2018前的最后一篇题解，从现在到NOIP我将进入总复习阶段。祝NOIP rp++。
那么这道题显然会有两个标记，一个add标记，一个set标记。那么怎样才能使这两个标记互不影响呢？
我们规定一个顺序，当set标记打过来时，我们首先将add标记清零，再打set标记。
改了改代码风格，具体请见博客置顶文章。
三、代码：
/*
* @Author: 岸芷汀兰
* @Date: 2018-10-15 22:11:37
* @LastEditors: 岸芷汀兰
* @LastEditTime: 2018-10-15 23:13:52
* @Description: 4927 of codevs
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define LL long long
#define mem(s,v) memset(s,v,sizeof(s))
using namespace std;
template<class Type>
inline Type read(void) {
Type x = 0, f = 1; char ch = getchar();
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return f * x;
}
const int maxn = 100005;
int n, m;
LL a[maxn];
struct Segment_Tree {
#define lson (o << 1)
#define rson (o << 1 | 1)
LL set[maxn << 2], add[maxn << 2], sum[maxn << 2], maxv[maxn << 2], minv[maxn << 2], len[maxn << 2];
inline void pushup(int o) {
sum[o] = sum[lson] + sum[rson];
maxv[o] = max(maxv[lson], maxv[rson]);
minv[o] = min(minv[lson], minv[rson]);
}
inline void build(int o, int l, int r) {
len[o] = r - l + 1;
add[o] = sum[o] = maxv[o] = minv[o] = 0;
set[o] = -1;
if (l == r) { sum[o] = a[l]; maxv[o] = a[l]; minv[o] = a[l]; return; }
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(o);
}
inline void Add(int o,int v){
add[o]+=v;
sum[o]+=len[o]*v;
minv[o]+=v;maxv[o]+=v;
return;
}
inline void Set(int o,int v){
set[o]=v;add[o]=0;
sum[o]=len[o]*v;
maxv[o]=minv[o]=v;
return;
}
inline void pushdown(int o){
if(set[o]!=-1){
Set(lson,set[o]);Set(rson,set[o]);
set[o]=-1;
}
if(add[o]){
Add(lson,add[o]);Add(rson,add[o]);
add[o]=0;
}
return;
}
inline void Update(int o,int l,int r,int ql,int qr,int k,LL v){
if(ql<=l&&r<=qr){
if(k==1){//add
Add(o,v);return;
}
else{//set
Set(o,v);return;
}
}
pushdown(o);
int mid=(l+r)>>1;
if(ql<=mid)Update(lson,l,mid,ql,qr,k,v);
if(qr>mid)Update(rson,mid+1,r,ql,qr,k,v);
pushup(o);
}
inline LL query(int o,int l,int r,int ql,int qr,int k){
if(ql<=l&&r<=qr){
switch(k){
case 1://sum
return sum[o];
case 2://max
return maxv[o];
case 3://min
return minv[o];
}
}
pushdown(o);
int mid=(l+r)>>1;LL ans=0;
switch(k){
case 1://sum
if(ql<=mid)ans+=query(lson,l,mid,ql,qr,k);
if(qr>mid)ans+=query(rson,mid+1,r,ql,qr,k);
return ans;
case 2://max
ans=-0x3f3f3f3f3f3f3f3f;
if(ql<=mid)ans=max(ans,query(lson,l,mid,ql,qr,k));
if(qr>mid)ans=max(ans,query(rson,mid+1,r,ql,qr,k));
return ans;
case 3://min
ans=0x3f3f3f3f3f3f3f3f;
if(ql<=mid)ans=min(ans,query(lson,l,mid,ql,qr,k));
if(qr>mid)ans=min(ans,query(rson,mid+1,r,ql,qr,k));
return ans;
}
}
}T;
int main() {
n = read<int>(); m = read<int>();
for (register int i = 1; i <= n; ++i) {
a[i] = read<LL>();
}
T.build(1, 1, n);
for (register int i = 1; i <= m; ++i) {
string s; cin >> s;
if (s == "add") {
int l = read<int>(), r = read<int>(); LL c = read<LL>();
T.Update(1, 1, n, l, r, 1, c);
}
else if (s == "set") {
int l = read<int>(), r = read<int>(); LL c = read<LL>();
T.Update(1, 1, n, l, r, 2, c);
}
else if (s == "sum") {
int l = read<int>(), r = read<int>();
printf("%lld
", T.query(1, 1, n, l, r, 1));
}
else if (s == "max") {
int l = read<int>(), r = read<int>();
printf("%lld
", T.query(1, 1, n, l, r, 2));
}
else if (s == "min") {
int l = read<int>(), r = read<int>();
printf("%lld
", T.query(1, 1, n, l, r, 3));
}
}
return 0;
}