专栏文章

[线段树] [分段函数] P5609 [Ynoi2013] 对数据结构的爱

__Cheems
P5609题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0tuyr
此快照首次捕获于
2025/12/02 11:31
3 个月前
此快照最后确认于
2025/12/02 11:31
3 个月前
查看原文
尝试更自然地叙述思路。唯一一处跳跃性步骤也是符合人类直觉的。
题意：给你长为 nn 的操作序列 aa 及定值 pp，mm 次询问，每次给出 [l,r,x][l,r,x]，求出 xx 依次进行操作 [l,r][l,r] 后的值。一次操作会使得 x←x+aix\gets x+a_i，然后若 x≥px\ge p 则 x←x−px\gets x-p。n≤106,m≤2×105n\le 10^6,m\le 2\times 10^5。
不妨从函数的视角出发，容易发现这是一个由若干段 k=1k=1 线段构成的分段函数。显然初值越大就会被减去更多次 pp，于是这个分段函数可以用一个序列 xix_i 描述，初值在 [xi,xi+1)[x_i,x_{i+1}) 都满足恰被减去 ii 次 pp。
由于 ∣x∣|x| 是操作个数级别的，很自然想到上线段树，对每个区间维护其分段函数。假如能预处理出 xx，那么每次查询只需拆分区间后，依次二分得到会被减去几次 pp 即可 O(log⁡2n)O(\log^2 n) 算出答案。
重点是怎么实现 push_up 函数。考虑朴素合并，对于左边区间 ii，若其终值区间覆盖了右边区间 jj 的左端点，则可以向 xi+jx_{i+j} 贡献，记这个贡献是 f(i,j)f(i,j)，显然 f(i,j)∈[xi,xi+1)f(i,j)\in [x_i,x_{i+1})，于是 f(i,j)<f(i+1,j−1)f(i,j)<f(i+1,j-1)，于是 jj 最大即可取到最小值。
（为了方便，不妨放宽限制化区间为前缀，只不过贡献时与 aia_i 取个 max⁡\max 即可。）
合法 i,ji,j 判定条件即为：xi+1−1+slson−ip≥xjx_{i+1}-1+s_{lson}-ip\ge x_j。于是 ii 合法的 jj 是段前缀。同时合理猜想 ii 的合法 jj 前缀边界随着 ii 增大而增大，即 jj 合法的 ii 是段后缀。
那么直接双指针即可，复杂度为 O(nlog⁡n)O(n\log n)。
证明：等价于 xi−ipx_i-ip 递增，接下来证 xi+1−xi≥px_{i+1}-x_i\ge p。你考虑代初值为 xix_i 时，恰好做完 ii 次减法后值必然为 00 且之后值不能超过 00，不然 xix_i 可取更小，因此至少再加上 pp 才能多减一次。
总结：本题运用线段树维护分段函数，重点为合并儿子信息。需要一定的直觉。

代码

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

#define int long long
#define MIN(a, b) a = min(a, b)
const int N = 1e6 + 5, inf = 1e17, M = 3e7 + 5;
int n, m, p, a[N], now, l, r, lstans;

namespace SGT{
    #define lt (u << 1)
    #define rt (u << 1 | 1)
    #define mid (l + r >> 1)
    int s[N << 2], x[M], beg[N << 2], siz[N << 2], tot;
    
    inline void build(int u, int l, int r){
        beg[u] = tot, siz[u] = r - l + 3; tot += siz[u];
        for(int i = 0; i <= r - l + 2; ++i) x[beg[u] + i] = inf;
        if(l == r) {x[beg[u]] = -inf, x[beg[u] + 1] = p - a[l], s[u] = a[l]; return ;}
        build(lt, l, mid), build(rt, mid + 1, r);
        s[u] = s[lt] + s[rt];
        int lsiz = mid - l + 1, rsiz = r - mid;
        for(int i = 0, j = 0; i <= lsiz; ++i){
            while(1){
                MIN(x[beg[u] + i + j], max(x[beg[lt] + i], x[beg[rt] + j] - s[lt] + i * p));
                ++j;
                if(j > rsiz) {j = rsiz; break;}
                if(x[beg[lt] + i + 1] - 1 + s[lt] - i * p < x[beg[rt] + j]) {--j; break;}    
            }
        }
    }
    inline void fid(int u, int l, int r, int ll, int rr){
        if(ll <= l && r <= rr){
            int val = upper_bound(x + beg[u], x + beg[u] + siz[u], now) - (x + beg[u]) - 1;
            now = now + s[u] - val * p;
            return ;
        }
        if(ll <= mid) fid(lt, l, mid, ll, rr);
        if(rr > mid) fid(rt, mid + 1, r, ll, rr);
    }
}using namespace SGT;
signed main(){
    cin >> n >> m >> p;
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    build(1, 1, n);
    while(m--){
        scanf("%lld%lld%lld", &l, &r, &now);
        l ^= lstans, r ^= lstans, now ^= lstans;
        assert(l <= r);
        fid(1, 1, n, l, r);
        printf("%lld\n", now);
        lstans = (now % n + n) % n;
    }    
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...