\(\text{Problem}\)
1.询问区间最小值是否大于 \(0\)
2.区间加（可正可负）
3.区间取 \(\max\)
如果某个数经过操作后小于等于 \(0\)，以后的操作就不会再影响这个数
\(\text{Analysis}\)
显然要用线段树维护这个区间
区间加和 \(\max\) 打个双标记就好了，给加法优先
然后考虑区间加的过程中一个数如果加上这个数小于等于了 \(0\)，那么我们把这个点设成无限大，标记一下
一个区间的标记定为区间内有没有被标记了的点
设成无限大后继续操作不会影响后面的情况，这样就好极了
\(\text{Code}\)
#include<cstdio>
#include<iostream>
#define ls (k << 1)
#define rs (ls | 1)
using namespace std;
const int N = 1e5 + 5 , INF = 0x3f3f3f3f;
int n , m , L;
struct segment{
int mn , tag_add , tag_max, fl;
}seg[N << 2];
inline void read(int &x)
{
x = 0; char ch = getchar();
while (ch < ‘0‘ || ch > ‘9‘) ch = getchar();
while (ch >= ‘0‘ && ch <= ‘9‘) x = (x<<3) + (x<<1) + ch - ‘0‘, ch = getchar();
}
inline void pushup(int k)
{
seg[k].mn = min(seg[ls].mn , seg[rs].mn);
seg[k].fl = seg[ls].fl && seg[rs].fl;
}
inline void push_add(int k , int v)
{
seg[k].tag_add += v, seg[k].mn += v;
if (seg[k].tag_max > -INF) seg[k].tag_max += v;
}
inline void push_max(int k , int v)
{
if (v <= seg[k].mn) return;
seg[k].mn = v, seg[k].tag_max = v;
}
inline void pushdown(int k)
{
if (seg[k].tag_add != 0)
{
push_add(ls , seg[k].tag_add);
push_add(rs , seg[k].tag_add);
seg[k].tag_add = 0;
}
if (seg[k].tag_max != -INF)
{
push_max(ls , seg[k].tag_max);
push_max(rs , seg[k].tag_max);
seg[k].tag_max = -INF;
}
}
inline void build(int l , int r , int k)
{
seg[k].tag_max = -INF;
if (l == r)
{
seg[k].mn = L, seg[k].fl = 1;
return;
}
int mid = (l + r) >> 1;
build(l , mid , ls) , build(mid + 1 , r , rs);
pushup(k);
}
inline void update_add(int l , int r , int k , int x , int y , int c)
{
if (x <= l && r <= y)
{
if (seg[k].mn + c > 0) return push_add(k , c);
else if (l == r)
{
seg[k].mn = INF, seg[k].fl = 0;
return;
}
}
pushdown(k);
int mid = (l + r) >> 1;
if (x <= mid) update_add(l , mid , ls , x , y , c);
if (y > mid) update_add(mid + 1 , r , rs , x , y , c);
pushup(k);
}
inline void update_max(int l , int r , int k , int x , int y , int c)
{
if (seg[k].mn >= c) return;
if (x <= l && r <= y)
{
push_max(k, c);
return;
}
pushdown(k);
int mid = (l + r) >> 1;
if (x <= mid) update_max(l , mid , ls , x , y , c);
if (y > mid) update_max(mid + 1 , r , rs , x , y , c);
pushup(k);
}
inline int query(int l , int r , int k , int x, int y)
{
if (x <= l && r <= y) return seg[k].fl;
pushdown(k);
int mid = (l + r) >> 1, res = 1;
if (x <= mid) res = query(l , mid , ls , x, y);
if (y > mid) res = res && query(mid + 1 , r , rs , x, y);
return res;
}
int main()
{
freopen("road.in", "r", stdin);
freopen("road.out", "w", stdout);
read(n), read(m), read(L);
build(1 , n , 1);
int l , r , c, op, ans = 0;
for(int i = 1; i <= m; i++)
{
read(op), read(l), read(r), read(c);
if (op == 1 && (query(1, n, 1, l, r))) ++ans, update_add(1, n, 1, l, r, -c);
else if (op == 2) update_add(1, n, 1, l, r, c);
else if (op == 3) update_max(1, n, 1, l, r, c);
}
printf("%d\n", ans);
}