HDU 5306 Gorgeous Sequence

\(HDU\) \(5306\) \(Gorgeous\) \(Sequence\)

标签：

区间最值操作,吉司机线段树,简单模板题

一、题目描述

现在有这样的一个问题：
你有一个长度为\(n\)(\(n≤1e6\))的序列，你将会进行\(m\)(\(m≤1e6\))次操作，每次操作属于下列三种形式之一：

• \(0\) \(l\) \(r\) \(x\) ，表示对于每一个\(i(l≤i≤r)\)，进行\(a_i=min(a_i,x)\)操作。
• \(1\) \(l\) \(r\)，询问区间\([l,r]\)内当前的区间最大值
• \(2\) \(l\) \(r\)，询问区间\([l,r]\)内的区间和，即 \(\displaystyle \sum_{i=l}^ra_i\)

二、解题思路

对于这样的问题（包括其各种加强版），\(jls\)在\(2016\)的国家集训队论文集中给出了如下的解法，即\(segment\) \(tree\) \(beats\)，一种采用势能思想的线段树。

吉老师论文：

三、实现代码

#include <iostream>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;

#define ls u << 1
#define rs u << 1 | 1

//快读
char buf[1 << 23], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

struct Node {
    int l, r, mx, se, cnt; // 区间最大值mx, 区间次大值se, 区间最大值个数cnt
    LL sum;                //区间和
} tr[N << 2];

//向上一级推送统计信息
void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
    tr[u].mx = max(tr[ls].mx, tr[rs].mx);

    if (tr[ls].mx == tr[rs].mx) {             //左右儿子最大值样等
        tr[u].cnt = tr[ls].cnt + tr[rs].cnt;  //父亲的最大值个数=左儿子最大值个数+右儿子最大值个数
        tr[u].se = max(tr[ls].se, tr[rs].se); //次大的，就需要讨论一下左右儿子谁的次大比较大
    }
    if (tr[ls].mx > tr[rs].mx) {              //如果左儿子最大值大于右儿子最大值
        tr[u].cnt = tr[ls].cnt;               //记录左儿子最大值个数
        tr[u].se = max(tr[ls].se, tr[rs].mx); //次大变成左儿子次大值，与右儿子最大值PK
    }
    if (tr[ls].mx < tr[rs].mx) {
        tr[u].cnt = tr[rs].cnt;
        tr[u].se = max(tr[rs].se, tr[ls].mx);
    }
}

//构建线段树
void build(int u, int l, int r) {
    // 每个都认真初始化,全部赋值一遍最稳妥
    // 此题卡时间卡的比较严重，如果不用下面的方法，每次memset(tr,0,sizeof(tr));就会TLE
    tr[u].l = l, tr[u].r = r, tr[u].mx = tr[u].cnt = tr[u].sum = 0;
    tr[u].se = -INF; //初始时没有次大值,最小值是0，所以设置成-INF就肯定小于最小值了

    if (l == r) {
        tr[u].sum = tr[u].mx = read();
        tr[u].cnt = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(u);
}

//将modify拆分成两个，独立出来
void update_min(int u, int k) {
    if (tr[u].mx <= k) return; //最大值都没有k大，k就是无用的东西
    tr[u].sum += ((LL)k - tr[u].mx) * tr[u].cnt; // 区间整体命中，并且比最大值小，能修改的只有最大值
    tr[u].mx = k;                                // 最大值修改为k
}

//向下一级传递懒标记tag标记,此时的懒标记就是tr[u].mx也就是区间最大值
void pushdown(int u) {
    update_min(ls, tr[u].mx), update_min(rs, tr[u].mx);
}

void modify_min(int u, int l, int r, int k) {
    // ①与修改区间与当前区间无次，或，k>=tr[u].mx 时，没有修改的必要
    if (r < tr[u].l || l > tr[u].r || k >= tr[u].mx) return;

    // ②整个区间命中，不用再分裂，并且，tr[u].se<k<tr[u].mx ，update(u,k)将只改最大
    if (l <= tr[u].l && tr[u].r <= r && tr[u].se < k) {
        update_min(u, k);
        return;
    }

    //③ k <=tr[u].se 时，无法实现只对最大值的修改，只能继续分裂，直到区间可以被上面两种条件覆盖到
    pushdown(u); //先下传lazy懒标记,防止有上次的累计懒标记没有处理，造成标记错乱或丢失

    //递归左右儿子
    modify_min(ls, l, r, k), modify_min(rs, l, r, k);

    //叶子节点修改后，别忘了再上传统计信息,比如什么最大值个数，次大值是谁啥的，上面可都没管，但最终修改后要更新一次
    pushup(u);
}

//普通线段树的区间最大值
int query_max(int u, int l, int r) {
    if (r < tr[u].l || l > tr[u].r) return -INF;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].mx;
    pushdown(u);
    return max(query_max(ls, l, r), query_max(rs, l, r));
}

//普通线段树的区间和
LL query_sum(int u, int l, int r) {
    if (r < tr[u].l || l > tr[u].r) return 0;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum; //完全在查询区间内，直接返回tr[u].sum

    pushdown(u);
    return query_sum(ls, l, r) + query_sum(rs, l, r);
}

void solve() {
    int n = read(), m = read();
    //构建线段树
    build(1, 1, n);

    while (m--) {
        int op = read(), l = read(), r = read();

        if (op == 0) {
            int k = read();
            modify_min(1, l, r, k); //将区间[l,r]中a[i](i∈[l,r]),与x取min,最后，将整个区间修改为min(x,a[i])
        }
        if (op == 1) printf("%d\n", query_max(1, l, r)); //查询区间最大值

        if (op == 2) printf("%lld\n", query_sum(1, l, r)); // 查询区间和
    }
}

int main() {
//文件输入输出
#ifndef ONLINE_JUDGE
    freopen("HDU5306.in", "r", stdin);
#endif
    int T = read();
    for (int i = 1; i <= T; i++) solve(); //多组测试数据，提取solve函数，然后执行T次是一个好方法
    return 0;
}