HDU 5306 Gorgeous Sequence(线段树)

Description:

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

$0 <mtext> </mtext> x <mtext> </mtext> y <mtext> </mtext> t$ : For every $x \leq i \leq y$ , we use $m i n (a_{i}, t)$ to replace the original $a_{i}$ 's value.

$1 <mtext> </mtext> x <mtext> </mtext> y$ : Print the maximum value of $a_{i}$ that $x \leq i \leq y$ .

$2 <mtext> </mtext> x <mtext> </mtext> y$ : Print the sum of $a_{i}$ that $x \leq i \leq y$ .

Input:

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

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

The second line contains $n$ separated integers $a_{1}, \dots, a_{n}$ ( $\forall 1 \leq i \leq n, 0 \leq a_{i} < 2^{31}$ ).

Each of the following $m$ lines represents one operation ( $1 \leq x \leq y \leq n, 0 \leq t < 2^{31}$ ).

It is guaranteed that $T = 100$ , $\sum n \leq 1000000, <mtext> </mtext> \sum m \leq 1000000$ .

Output:

For every operation of type $1$ or $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$ 个元素的序列 $a r r$ 支持 $m$ 次以下三种操作

0 x y t 对区间 $i \in [x, y]$ 的元素取 $\min (a r r_{i}, t)$
1 x y 求区间 $i \in [x, y]$ 的最大值 $\max (a r r_{i})$
2 x y 求 $\sum_{i = x}^{y} a r r_{i}$

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

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

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

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

$m a \leq x$ ，这种情况下显然 $x$ 对区间无影响，退出
$s e < x < m a$ ，这种情况下显然区间更新时指挥影响到 $t$ 个最大值，所以 $s u m + = t \times (x - m a)$ 并把 $m a$ 更新为 $x$ 即可
$s e \geq 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;
}