P9993 [Ynoi Easy Round 2024] TEST_133 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$ 和 $b$（初始为 $a$），有 $m$ 个操作分两种：

• $\mathrm{add}(l,r,x)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i+x$.
• $\mathrm{query}(l,r,x)$：求 $\underset{i\in [l,r],a_i<x}{\max }{b}_i$，若没有满足的 $i$ 输出 $-\infty$.

每次操作后，对每个 $i\in [1,n]$ 执行 $b_i\leftarrow \max (a_i,b_i)$.

Limitations

$1\le n,m\le 5\times 10^5$
$|a_i|,|x|\le 10^9$
$40\text{s},512\text{MB}$

Solution

发现线段树不能维护，考虑分块.
维护 $a_i$ 和其历史最大值 ${\text{hist}}_i$.
对于每个块，维护块内 $a_i$ 排序后结果 $p_i$，排序后 $b_i$ 前缀和 $hpr{e}_i$，$a_i$ 加标记 $\text{add}$，$b_i$ 加标记 $\text{hadd}$.
下传标记及修改仿照吉司机就行，查询时散块暴力，整块二分.
时间复杂度 $O((n+m)\sqrt{n}\log n)$，时限很大所以能过.

Code

$4.05\text{KB},3.67\text{min},23.41\text{MB}\text{(in total, C++ with O2)}$

// Problem: P9993 [Ynoi Easy Round 2024] TEST_133
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9993
// Memory Limit: 512 MB
// Time Limit: 40000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

const i64 inf = 3e18;
struct Block {
    int n, B, blocks;
    vector<int> belong, L, R, id;
    vector<i64> a, hist, hpre, add, hadd, p;
    
    inline Block() {}
    inline Block(const vector<i64>& a) {
        this->a = a;
        this->hist = a;
        n = a.size();
        B = sqrt(n);
        blocks = n / B + (n % B > 0);
        
        belong.resize(n);
        L.resize(blocks);
        R.resize(blocks);
        hpre.resize(n);
        add.resize(blocks);
        hadd.resize(blocks);
        id.resize(n);
        p.resize(n);
        
        for (int i = 0; i < blocks; i++) {
            L[i] = i * B;
            R[i] = min(L[i] + B - 1, n - 1);
            for (int j = L[i]; j <= R[i]; j++) belong[j] = i;
            rebuild(i);
        }
    }
    
    inline void pushdown(int u) {
        for (int i = L[u]; i <= R[u]; i++) {
            hist[i] = max(hist[i], a[i] + hadd[u]);
            a[i] += add[u];
        }
        add[u] = hadd[u] = 0;
    }
    
    inline void rebuild(int u) {        
        iota(id.begin() + L[u], id.begin() + R[u] + 1, L[u]);
        sort(id.begin() + L[u], id.begin() + R[u] + 1, [&](int x, int y) {
            return a[x] < a[y];
        });
        
        for (int i = L[u]; i <= R[u]; i++) p[i] = a[id[i]];
        hpre[L[u]] = hist[id[L[u]]];
        for (int i = L[u] + 1; i <= R[u]; i++) hpre[i] = max(hpre[i - 1], hist[id[i]]);
    }
    
    inline void brute_modify(int l, int r, int k) {
        pushdown(belong[l]);
        for (int i = l; i <= r; i++) {
            a[i] += k;
            hist[i] = max(hist[i], a[i]);
        }
        rebuild(belong[l]);
    }
    
    inline void modify(int l, int r, int k) {
        if (belong[l] == belong[r]) return brute_modify(l, r, k);
        brute_modify(l, R[belong[l]], k);
        for (int i = belong[l] + 1; i < belong[r]; i++) {
            add[i] += k;
            hadd[i] = max(hadd[i], add[i]);
        }
        brute_modify(L[belong[r]], r, k);
    }
    
    inline i64 brute_query(int l, int r, int k) {
        i64 ans = -inf;
        for (int i = l; i <= r; i++) {
            if (a[i] + add[belong[i]] < k) {
                ans = max(ans, hist[i]);
                ans = max(ans, a[i] + hadd[belong[i]]);
            }
        }
        return ans;
    }
    
    inline i64 query(int l, int r, int k) {
        if (belong[l] == belong[r]) return brute_query(l, r, k);
        i64 ans = brute_query(l, R[belong[l]], k);
        for (int i = belong[l] + 1; i < belong[r]; i++) {
            auto it = lower_bound(p.begin() + L[i], p.begin() + R[i] + 1, k - add[i]) - 1;
            if (p.begin() + L[i] <= it) {
                ans = max(ans, hpre[it - p.begin()]);
                ans = max(ans, *it + hadd[i]);
            }
        }
        ans = max(ans, brute_query(L[belong[r]], r, k));
        return ans;
    }
};

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	scanf("%d %d", &n, &m);
	
	vector<i64> a(n);
	for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
	
	Block blk(a);
	for (int i = 0, op, l, r, k; i < m; i++) {
	    scanf("%d %d %d %d", &op, &l, &r, &k);
	    l--, r--;
	    
	    if (op == 1) blk.modify(l, r, k);
	    else {
	        i64 ans = blk.query(l, r, k);
	        if (ans == -inf) printf("-inf\n");
	        else printf("%lld\n", ans);
	    }
	}
	
	return 0;
}