DimitryL 讲的好啊

picks loves segment tree I

#include <bits/stdc++.h>

#define NS (500005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, m, A[NS];

struct N {int m1, m2, cnt; LL sum;} e[NS << 2];

void tag(int a, int d)
{
e[a].sum -= 1ll * (e[a].m1 - d) * e[a].cnt, e[a].m1 = d;
}

void pup(int a)
{
int l = LS(a), r = RS(a);
e[a].sum = e[l].sum + e[r].sum;
if (e[l].m1 == e[r].m1)
{
e[a].m1 = e[l].m1, e[a].cnt = e[l].cnt + e[r].cnt;
e[a].m2 = max(e[l].m2, e[r].m2);
return;
}
if (e[l].m1 < e[r].m1) swap(l, r);
e[a].m1 = e[l].m1, e[a].cnt = e[l].cnt, e[a].m2 = max(e[r].m1, e[l].m2);
}

void pdown(int a)
{
int l = LS(a), r = RS(a);
if (e[a].m1 < e[l].m1) tag(l, e[a].m1);
if (e[a].m1 < e[r].m1) tag(r, e[a].m1);
}

void Build(int l, int r, int a)
{
if (l == r)
{
e[a].sum = e[a].m1 = A[l], e[a].m2 = INT_MIN, e[a].cnt = 1;
return;
}
int mid = (l + r) >> 1;
Build(l, mid, LS(a)), Build(mid + 1, r, RS(a)), pup(a);
}

void Update(int l, int r, int d, int L, int R, int a)
{
if (d >= e[a].m1) return;
if (l <= L && R <= r && d > e[a].m2) {tag(a, d); return;}
pdown(a);
int Mid = (L + R) >> 1;
if (l <= Mid) Update(l, r, d, L, Mid, LS(a));
if (r > Mid) Update(l, r, d, Mid + 1, R, RS(a));
pup(a);
}

LL Query(int l, int r, int L, int R, int a)
{
if (l <= L && R <= r) return e[a].sum;
pdown(a);
LL res = 0; int Mid = (L + R) >> 1;
if (l <= Mid) res = Query(l, r, L, Mid, LS(a));
if (r > Mid) res += Query(l, r, Mid + 1, R, RS(a));
return res;
}

int main(int argc, char const* argv[])
{
IN(n), IN(m);
for (int i = 1; i <= n; i += 1) IN(A[i]);
Build(1, n, 1);
for (int C = 1, o, a, b, c; C <= m; C += 1)
{
IN(o), IN(a), IN(b);
if (o) IN(c), Update(a, b, c, 1, n, 1);
else printf("%lld\n", Query(a, b, 1, n, 1));
}
return 0;
}


picks loves segment tree II

#include <bits/stdc++.h>

#define NS (500005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, m, A[NS];

struct N {LL m1, m2, sum, tag; int cnt;} e[NS << 2];

void tmin(int a, LL d)
{
e[a].sum -= 1ll * (e[a].m1 - d) * e[a].cnt, e[a].m1 = d;
}

void tadd(int a, int l, LL d)
{
e[a].m1 += d, e[a].m2 += d;
e[a].sum += 1ll * l * d, e[a].tag += d;
}

void pup(int a)
{
int l = LS(a), r = RS(a);
e[a].sum = e[l].sum + e[r].sum;
if (e[l].m1 == e[r].m1)
{
e[a].m1 = e[l].m1, e[a].cnt = e[l].cnt + e[r].cnt;
e[a].m2 = max(e[l].m2, e[r].m2);
return;
}
if (e[l].m1 < e[r].m1) swap(l, r);
e[a].m1 = e[l].m1, e[a].cnt = e[l].cnt, e[a].m2 = max(e[r].m1, e[l].m2);
}

void pdown(int L, int R, int a)
{
int l = LS(a), r = RS(a);
if (e[a].tag)
{
int Mid = (L + R) >> 1;
tadd(l, Mid - L + 1, e[a].tag), tadd(r, R - Mid, e[a].tag);
e[a].tag = 0;
}
if (e[a].m1 < e[l].m1) tmin(l, e[a].m1);
if (e[a].m1 < e[r].m1) tmin(r, e[a].m1);
}

void Build(int l, int r, int a)
{
if (l == r)
{
e[a].sum = e[a].m1 = A[l], e[a].m2 = -1e17, e[a].cnt = 1;
return;
}
int mid = (l + r) >> 1;
Build(l, mid, LS(a)), Build(mid + 1, r, RS(a)), pup(a);
}

void Up_Min(int l, int r, int d, int L, int R, int a)
{
if (d >= e[a].m1) return;
if (l <= L && R <= r && d > e[a].m2) {tmin(a, d); return;}
pdown(L, R, a);
int Mid = (L + R) >> 1;
if (l <= Mid) Up_Min(l, r, d, L, Mid, LS(a));
if (r > Mid) Up_Min(l, r, d, Mid + 1, R, RS(a));
pup(a);
}

void Up_Add(int l, int r, int d, int L, int R, int a)
{
if (l <= L && R <= r) {tadd(a, R - L + 1, d); return;}
pdown(L, R, a);
int Mid = (L + R) >> 1;
if (l <= Mid) Up_Add(l, r, d, L, Mid, LS(a));
if (r > Mid) Up_Add(l, r, d, Mid + 1, R, RS(a));
pup(a);
}

LL Query(int l, int r, int L, int R, int a)
{
if (l <= L && R <= r) return e[a].sum;
pdown(L, R, a);
LL res = 0; int Mid = (L + R) >> 1;
if (l <= Mid) res = Query(l, r, L, Mid, LS(a));
if (r > Mid) res += Query(l, r, Mid + 1, R, RS(a));
return res;
}

int main(int argc, char const* argv[])
{
IN(n), IN(m);
for (int i = 1; i <= n; i += 1) IN(A[i]);
Build(1, n, 1);
for (int C = 1, o, a, b, c; C <= m; C += 1)
{
IN(o), IN(a), IN(b);
if (o == 1) IN(c), Up_Min(a, b, c, 1, n, 1);
else if (o == 2) IN(c), Up_Add(a, b, c, 1, n, 1);
else printf("%lld\n", Query(a, b, 1, n, 1));
}
return 0;
}


#### Remmina

No puzzle that couldn't be solved.

### 3 条评论

#### Remmina · 2020年7月13日 10:01 上午

具体好像真不记得了，隐约记得是 boshi 做了数据放在 yzoj 上了

#### Qiuly · 2020年7月13日 10:06 上午

感谢，到时候去看看 qwq