HDU 5306 Gorgeous Sequence(线段树)

Description:

There is a sequence $a$a of length $n$n. We use $a_i$ai​ to denote the $i$i-th element in this sequence. You should do the following three types of operations to this sequence.

$0xyt$0 x y t: For every $x\le i\le y$x≤i≤y, we use $min(a_i,t)$min(ai​,t) to replace the original $a_i$ai​'s value.

$1xy$1 x y: Print the maximum value of $a_i$ai​ that $x\le i\le y$x≤i≤y.

$2xy$2 x y: Print the sum of $a_i$ai​ that $x\le i\le y$x≤i≤y.

Input:

The first line of the input is a single integer $T$T, indicating the number of testcases.

The first line contains two integers $n$n and $m$m denoting the length of the sequence and the number of operations.

The second line contains $n$n separated integers $a_1,\dots ,a_n$a1​,…,an​ ( $\forall 1\le i\le n,0\le a_i\&lt;2^{31}$∀1≤i≤n,0≤ai​<231).

Each of the following $m$m lines represents one operation ( $1\le x\le y\le n,0\le t\&lt;2^{31}$1≤x≤y≤n,0≤t<231).

It is guaranteed that $T=100$T=100, $\sum n\le 1000000,\sum m\le 1000000$∑n≤1000000, ∑m≤1000000.

Output:

For every operation of type $1$1 or $2$2, print one line containing the answer to the corresponding query.

Sample Input:

1
5 5
1 2 3 4 5
1 1 5
2 1 5
0 3 5 3
1 1 5
2 1 5

Sample Output:

5
15
3
12

Hint:

Please use efficient IO method

题目链接

对 $n$n 个元素的序列 $arr$arr 支持 $m$m 次以下三种操作

• 0 x y t 对区间 $i\in [x,y]$i∈[x,y] 的元素取 $\min (ar{r}_i,t)$min(arri​,t)
• 1 x y 求区间 $i\in [x,y]$i∈[x,y] 的最大值 $\max \left(ar{r}_i\right)$max(arri​)
• 2 x y 求 ${\sum }_{i=x}^{y}ar{r}_i$i=x∑y​arri​

jls2016年信息学奥林匹克中国国家队候选队员论文中的一道例题，被无情的卡常了……结构体和 $STL$STL 都被卡掉了……真毒瘤

因为在一节点打上区间取 $\min$min 标记的时候无法快速更新区间和，所以不能通过传统的 $lazy$lazy 惰性标记解决

考虑另一种做法，线段树中每个节点维护区间最大值 $ma$ma 、区间严格次大值 $se$se 、区间最大值数量 $t$t 、区间和 $sum$sum

当我们进行区间更新对 $x$x 取 $\min$min 时会遇到三种情况

• $ma\le x$ma≤x ，这种情况下显然 $x$x 对区间无影响，退出
• $se\&lt;x\&lt;ma$se<x<ma ，这种情况下显然区间更新时指挥影响到 $t$t 个最大值，所以 $sum+=t\times (x-ma)$sum+=t×(x−ma) 并把 $ma$ma 更新为 $x$x 即可
• $se\ge x$se≥x ，这种情况下无法至今进行更新，所以递归向小区间更新直到遇到前两种情况

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

template <class T>
inline bool Read(T &ans) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) {
        return false;
    }
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ans = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        ans = ans * 10 + (c - '0');
    }
    ans *= sgn;
    return true;
}

class seg_tree{
  public:
    int ma[maxn << 2], t[maxn << 2], se[maxn << 2];
    long long sum[maxn << 2];

    void Pull(int o) {
      sum[o] = sum[o << 1] + sum[o << 1 | 1];
      ma[o] = max(ma[o << 1], ma[o << 1 | 1]);
      se[o] = max(se[o << 1], se[o << 1 | 1]);
      t[o] = 0;
      if (ma[o << 1] != ma[o << 1 | 1]) se[o] = max(se[o], min(ma[o << 1], ma[o << 1 | 1]));
      if (ma[o] == ma[o << 1]) t[o] += t[o << 1];
      if (ma[o] == ma[o << 1 | 1]) t[o] += t[o << 1 | 1];
    }

    void Push(int o, int l, int r) {
      int m = (l + r) >> 1;
      if (ma[o] < ma[o << 1]) {
        sum[o << 1] += 1ll * (ma[o] - ma[o << 1]) * t[o << 1];
        ma[o << 1] = ma[o];
      }
      if (ma[o] < ma[o << 1 | 1]) {
        sum[o << 1 | 1] += 1ll * (ma[o] - ma[o << 1 | 1]) * t[o << 1 | 1];
        ma[o << 1 | 1] = ma[o];
      }
    }

    void Build(int o, int l, int r) {
      if (l == r) {
        Read(sum[o]);
        ma[o] = sum[o];
        t[o] = 1; se[o] = -1;
        return;
      }
      int m = (l + r) >> 1;
      Build(o << 1, l, m);
      Build(o << 1 | 1, m + 1, r);
      Pull(o);
    }

    void Modify(int o, int l, int r, int ll, int rr, int v) {
      if (ll <= l && rr >= r && v > se[o]) {
        if (v < ma[o]) {
          sum[o] += 1ll * (v - ma[o]) * t[o];
          ma[o] = v;
        }
        return;
      }
      Push(o, l, r);
      int m = (l + r) >> 1;
      if (ll <= m) Modify(o << 1, l, m, ll, rr, v);
      if (rr > m) Modify(o << 1 | 1, m + 1, r, ll, rr, v);
      Pull(o);
    }

    int QueryMax(int o, int l, int r, int ll, int rr) {
      if (ll <= l && rr >= r) return ma[o];
      Push(o, l, r);
      int m = (l + r) >> 1, ans = 0;
      if (ll <= m) ans = max(ans, QueryMax(o << 1, l, m, ll, rr));
      if (rr > m) ans = max(ans, QueryMax(o << 1 | 1, m + 1, r, ll, rr));
      return ans;
    }

    long long QuerySum(int o, int l, int r, int ll, int rr) {
      if (ll <= l && rr >= r) return sum[o];
      Push(o, l, r);
      int m = (l + r) >> 1;
      long long ans = 0;
      if (ll <= m) ans += QuerySum(o << 1, l, m, ll, rr);
      if (rr > m) ans += QuerySum(o << 1 | 1, m + 1, r, ll, rr);
      return ans;
    }
};

seg_tree sgt;

int main() {
  int t; Read(t);
  for (int cas = 1; cas <= t; ++cas) {
    int n, m; Read(n); Read(m);
    sgt.Build(1, 1, n);
    for (int i = 0, op, l, r, v; i < m; ++i) {
      Read(op); Read(l); Read(r);
      if (op == 0) {
        Read(v);
        sgt.Modify(1, 1, n, l, r, v);
      }
      else if (op == 1) printf("%d\n", sgt.QueryMax(1, 1, n, l, r));
      else printf("%lld\n", sgt.QuerySum(1, 1, n, l, r));
    }
  }
  return 0;
}