# BZOJ4355: Play with sequence(吉司机线段树)

## Sol

```#include<cstdio>
#include<algorithm>
#define LL long long
//#define int long long
using namespace std;
const int MAXN = 3 * 1e5 + 10;
const LL INF = 1e10 +10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
#define ls k << 1
#define rs k << 1 | 1
int N, Q;
int a[MAXN];
struct Node {
int l, r, siz, cnt;
LL Mx, add, mn, se, cov;
}T[MAXN << 2];
void update(int k) {
//T[k].mn = min(T[ls].mn, T[rs].mn);
if(T[ls].mn < T[rs].mn)      T[k].cnt = T[ls].cnt, T[k].mn = T[ls].mn, T[k].se = min(T[rs].mn, T[ls].se);
else if(T[ls].mn > T[rs].mn) T[k].cnt = T[rs].cnt, T[k].mn = T[rs].mn, T[k].se = min(T[ls].mn, T[rs].se);
else              T[k].cnt = T[ls].cnt + T[rs].cnt, T[k].mn = T[ls].mn, T[k].se = min(T[ls].se, T[rs].se);
}
void MemP(int k, LL val) {
T[k].cov = val;
T[k].cnt = T[k].siz;
T[k].se = INF;
T[k].Mx = -INF;
T[k].mn = val;
}
void AddP(int k, LL val) {
if(T[k].se != INF)  T[k].se += val;
if(T[k].Mx != -INF) T[k].Mx += val;
T[k].mn += val;
}
void MaxP(int k, LL val) {
T[k].mn = max(T[k].mn, val);//
T[k].Mx = max(T[k].Mx, val);
}
void pushdown(int k) {
if(T[k].cov != INF) MemP(ls, T[k].cov), MemP(rs, T[k].cov), T[k].cov = INF;
if(T[k].Mx != -INF) MaxP(ls, T[k].Mx), MaxP(rs, T[k].Mx), T[k].Mx = -INF;
}
void Build(int k, int ll, int rr) {
T[k] = (Node) {ll, rr, rr - ll + 1, 0, -INF, 0, 0, INF, INF};
if(ll == rr) {
T[k].mn = a[ll]; T[k].cnt = 1;
return ;
}
int mid = T[k].l + T[k].r >> 1;
Build(ls, ll, mid); Build(rs, mid + 1, rr);
update(k);
}
void IntMem(int k, int ll, int rr, LL val) {
if(ll <= T[k].l && T[k].r <= rr) {MemP(k, val); return ;}
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll <= mid) IntMem(ls, ll, rr, val);
if(rr >  mid) IntMem(rs, ll, rr, val);
update(k);
}
void IntAdd(int k, int ll, int rr, LL val) {
if(ll <= T[k].l && T[k].r <= rr) {AddP(k, val); return ;}
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll <= mid) IntAdd(ls, ll, rr, val);
if(rr >  mid) IntAdd(rs, ll, rr, val);
update(k);
}
void IntMax(int k, int ll, int rr, LL val) {
if(val <= T[k].mn) return ;
if(ll <= T[k].l && T[k].r <= rr && T[k].se > val) {//tag
MaxP(k, val);
return ;
}
int mid = T[k].l + T[k].r >> 1;
pushdown(k);
if(ll <= mid) IntMax(ls, ll, rr, val);
if(rr >  mid) IntMax(rs, ll, rr, val);
update(k);
}
LL Query(int k, int ll, int rr) {
// int ans = 0;
if(ll <= T[k].l && T[k].r <= rr)
return (T[k].mn == 0 ? T[k].cnt : 0);
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll > mid) return Query(rs, ll, rr);
else if(rr <= mid) return Query(ls, ll, rr);
else return Query(ls, ll, rr) + Query(rs, ll, rr);
}
main() {
// freopen("4355.in", "r", stdin);
// freopen("4355.out", "w", stdout);
for(int i = 1; i <= N; i++) a[i] = read();
Build(1, 1, N);
while(Q--) {
int opt = read(), l = read(), r = read(), val;
if(opt == 3) printf("%d\n", Query(1, l, r));
else {
if(opt == 1) IntMem(1, l, r, val);
else {
IntAdd(1, l, r, val);
IntMax(1, l, r, 0);
}
}
}
return 0;
}```

1811 篇文章120 人订阅

0 条评论

## 相关文章

### Mysql-7-mysql函数

1.数学函数   用来处理数值数据方面的运算，主要的数学函数有：绝对值函数，三角函数，对数函数，随机函数。使用数学函数过程中，如果有错误产生，该函数会返回nul...

2077

894

1776

### C/C++ 一段代码区分数组指针|指针数组|函数指针|函数指针数组

1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<windows.h> 4 /* 举列子说明什么是...

2915

### Scalaz（52）－ scalaz-stream: 并行运算－parallel processing concurrently by merging

如果scalaz-stream真的是一个实用的数据流编程工具库的话，那它应该能处理同时从多个数据源获取数据以及把数据同时送到多个终点（Sink），最重要的...

2078

1694

### Java位操作

无论说是在哪一门计算机语言，位操作运算对于计算机来说肯定是最高效的，因为计算机的底层是按就是二进制，而位操作就是为了节省开销，加快程序的执行速度，以及...

3558

1022

### 解读C#中的正则表达式

多少年来，许多的编程语言和工具都包含对正则表达式的支持，.NET基础类库中包含有一个名字空间和一系列可以充分发挥规则表达式威力的类，而且它们也都与未...

2317

1684