[数据结构与算法]bzoj4695 最佳女选手

bzoj4695 最佳女选手

题意：

给定一个序列，让我们实现六种操作

1. 区间[l, r] 加 x
2. 区间[l, r] 里小于x的数变成x
3. 区间[l, r] 里大于x的数变成x
4. 区间[l, r] 求和
5. 区间 [l, r] 求max
6. 区间 [l, r] 求min

题解：

? 对于区间加维护一个tag即可，区间求和、求max、求min都是基本操作，这里要考虑对于2，3两个操作怎么去维护？

? 想一些比较特殊的情况来剪枝，来降低复杂度，对于操作2来说如果当前区间[l, r] 的 最小值mn都大于x我们就不需要处理当前这个区间，直接砍掉。如果区间最小值mn < x 并且 区间次小值 mnn >= x 我们就可以不去暴力的单点修改了，进而直接修改整个区间相当于把mn 变成 x，因为 mnn >= x 所以 mn还是最小值，并不会影响mn和mnn的相对关系，但是有可能会影响mx和mxx的值(记得特判一下是否改变)。

然后每次做down操作时如果左儿子的mn 小于父节点的mn则证明左儿子的mn需要被更改，这样就完成了对于子区间的维护，因为当前区间的mn可能改变，mn的改变会影响区间和sum的值，因此需要多维护一个[l, r] 区间mn的数量cmn去改变sum的值，这样才能维护整个区间。

? 操作3同理。

所以线段树需要维护的信息是

l, r 区间

mx mn mxx mnn 区间最大、最小 、次大、次小值

cmx cmn 区间最大、最小值的数目

sum lazy 区间和，区间tag

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 5e5 + 5, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n, m, k;
struct Node {
    int l, r;
    LL mx, mn, mxx, mnn, cmx, cmn;
    LL sum, lazy;
}tr[N * 4];
LL a[N];
void pushup(int u) { 
// 向上push维护 和为左右儿子的sum  mx为左右儿子中最大的  cmx的值为左儿子中mx的数量加右儿子中mx的数量  
// mxx为左儿子中不等于mx的最大的和右儿子中不等于mx的最大的的最大的
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; 
    tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx);
    tr[u].cmx = (tr[u].mx == tr[u << 1].mx ? tr[u << 1].cmx : 0) 
                + (tr[u].mx == tr[u << 1 | 1].mx ? tr[u << 1 | 1].cmx : 0);
    tr[u].mxx = max(tr[u].mx == tr[u << 1].mx ? tr[u << 1].mxx : tr[u << 1].mx,
                   tr[u].mx == tr[u << 1 | 1].mx ? tr[u << 1 | 1].mxx : tr[u << 1 | 1].mx);
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
    tr[u].cmn = (tr[u].mn == tr[u << 1].mn ? tr[u << 1].cmn : 0) + 
                (tr[u].mn == tr[u << 1 | 1].mn ? tr[u << 1 | 1].cmn : 0);
    tr[u].mnn = min(tr[u].mn == tr[u << 1].mn ? tr[u << 1].mnn : tr[u << 1].mn,
                tr[u].mn == tr[u << 1 | 1].mn ? tr[u << 1 | 1].mnn : tr[u << 1 | 1].mn);
}
void pushnow_mx(int u, LL v) {  // 操作三， 可以更新则 更新sum 更新mn mnn 和 mx 
    if (tr[u].mx <= v) return ; 
    tr[u].sum += tr[u].cmx * (v - tr[u].mx); 
    tr[u].mx = v, tr[u].mn = min(tr[u].mn, v); 
    if (tr[u].mn == tr[u].mx) 
       tr[u].sum = 1ll * (tr[u].cmn = tr[u].cmx = (tr[u].r - tr[u].l + 1)) 
        * (tr[u].mx = tr[u].mn = v), tr[u].mnn = INF, tr[u].mxx = -INF;
    else tr[u].mnn = min(tr[u].mnn, v);
}
void pushnow_mn(int u, LL v ) {   // 操作二， 可以更新则 更新sum 更新mx mxx 和 mn
    if (tr[u].mn >= v) return; 
    tr[u].sum += tr[u].cmn * (v - tr[u].mn); 
    tr[u].mn = v, tr[u].mx = max(tr[u].mx, v);
    if (tr[u].mn == tr[u].mx) tr[u].sum =   
        1ll * (tr[u].cmn = tr[u].cmx = (tr[u].r - tr[u].l + 1)) 
        * (tr[u].mx = tr[u].mn = v), tr[u].mnn = INF, tr[u].mxx = -INF;
    else tr[u].mxx = max(tr[u].mxx, v);        
}
void pushnow(int u, LL x) { // 标记tag
    tr[u].lazy += x, tr[u].sum += 1ll * (tr[u].r - tr[u].l + 1) * x;
    tr[u].mn += x, tr[u].mnn += x;
    tr[u].mx += x, tr[u].mxx += x;
}
void pushdown(int u) { 
    if (tr[u].lazy) {
        pushnow(u << 1, tr[u].lazy), pushnow(u << 1 | 1, tr[u].lazy);
        tr[u].lazy = 0;
    }
    // 更新子区间的mx mn
    pushnow_mn(u << 1, tr[u].mn), pushnow_mn(u << 1 | 1, tr[u].mn);
    pushnow_mx(u << 1, tr[u].mx), pushnow_mx(u << 1 | 1, tr[u].mx); 
}
void build(int u, int l, int r) { // 建树
    tr[u].l = l, tr[u].r = r, tr[u].lazy = 0;
    if (l == r) {
        tr[u].sum = tr[u].mn = tr[u].mx = a[l];
        tr[u].cmn = tr[u].cmx = 1;
        tr[u].mxx = -INF, tr[u].mnn = INF;
        return ; 
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void update(int u, int l, int r, int x) { // 区间修改
    if (l > tr[u].r || r < tr[u].l) return ;
    if (l <= tr[u].l && tr[u].r <= r) {
        pushnow(u, x);
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) update(u << 1, l, r, x);
    if (r > mid)  update(u << 1 | 1, l, r, x);
    pushup(u); 
}
void modifymx(int u, int l, int r, int x) {
    if (l > tr[u].r || r < tr[u].l || tr[u].mx <= x) return ; // 剪枝 
    if (l <= tr[u].l && tr[u].r <= r && tr[u].mxx < x) {  // 符合条件
        pushnow_mx(u, x); 
        return ;
    } 
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modifymx(u << 1, l, r, x);
    if (r > mid)  modifymx(u << 1 | 1, l, r, x);
    pushup(u);
}
void modifymn(int u, int l, int r, LL x) {
    if (l > tr[u].r || r < tr[u].l || tr[u].mn >= x) return ; // 剪枝
    if (l <= tr[u].l && tr[u].r <= r && tr[u].mnn > x) {
        pushnow_mn(u, x);
        return ;
    } 
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modifymn(u << 1, l, r, x);
    if (r > mid)  modifymn(u << 1 | 1, l, r, x);
    pushup(u);
}
LL query_sum(int u, int l, int r) {
    if (tr[u].r < l || tr[u].l > r) return 0;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if(l <= mid) sum = query_sum(u << 1, l, r);
    if (r > mid) sum += query_sum(u << 1 | 1, l, r);
    return sum;
}
int query_max(int u, int l, int r) {
    if (tr[u].r < l || tr[u].l > r) return -INF;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].mx;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int res = -INF;
    if (l <= mid) res = query_max(u << 1, l, r);
    if (r > mid)  res = max(res, query_max(u << 1 | 1, l, r));
    return res;
}
int query_min(int u, int l, int r) {
    if (tr[u].r < l || tr[u].l > r) return INF;
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].mn;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int res = INF;
    if (l <= mid) res = query_min(u << 1, l, r);
    if (r > mid)  res = min(res, query_min(u << 1 | 1, l, r));
    return res;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    build(1, 1, n);
    cin >> m;
    while (m -- ) {
        int op, l, r;
        LL x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            update(1, l, r, x);
        }
        else if (op == 2) {
            cin >> x;
            modifymn(1, l, r, x);
        }
        else if (op == 3) {
            cin >> x;
            modifymx(1, l, r, x);
        }
        else if (op == 4) cout << query_sum(1, l, r) << endl;
        else if (op == 5) cout << query_max(1, l, r) << endl;
        else cout << query_min(1, l, r) << endl;
    }
return 0;
}