题解：UVA1400 "Ray, Pass me the dishes!"/ ARIS0_0 - 8

Kei__ · 2026-04-21 10:29:02 · 题解

我也有一个朋友叫 Ray，我曾拿这道题开他的玩笑。不过，他已经退役了，于是我开始写这篇题解……

本题解采用一种冷门的做法：带权并查集维护扫描线。

题意

进行 q 次查询，求区间内的一个子区间满足其为区间内的最大子段和且该区间尽可能地靠左。

思路

为了方便，我们用 a,b,c,d 分别来表示最大子段和、区间和、最大前缀和、最大后缀和，u,v 表示合并的左右区间，f 表示合并后的大区间。

1. 最大子段和合并：
   有三种情况，如图：
   
   要么完全包含在左区间或右区间，要么由左区间的后缀与右区间的前缀拼接而成，对这三种情况取最大值就是合并后的最大子段和。

2. 区间和合并：
   直接将两个区间和相加即可。

3. 最大前缀和合并：
   有两种情况，第一种最大前缀和就是 c_u，第二种是 b_u+c_v，然后对两种情况取最大值。

4. 最大后缀和合并：
   同最大前缀和合并一样，有两种情况，第一种是 d_v，第二种是 b_v+d_u，对两种情况取最大值即可。

综上可以得出：

接下来考虑如何让区间尽可能地靠左。每个区间我们需要维护最靠左的最大子段和区间 [l,r]、最大前缀和所达的下标 ls、最大后缀和所达的下标 rs。

当前区间最靠左的最大子段和区间的求法就和求最大子段和一样，判一下是否为最大子段和再改一下比较方式即可。

那么就可以用线段树或者二进制拆位猫树爆破了，不过这里分享另一种特殊的做法，是这篇文章中介绍的算法在链上的应用。

这是一个离线算法，在链上的核心思想是扫描线。我们首先对查询区间按右端点从小到大排序，然后从左往右枚举右端点 j，用带权并查集维护每个左端点 i 到 j 的区间信息。这种带权并查集的权值合并比较特殊，每个结点的权值不会加到父结点那里去，而是与之相反，将父结点的权值加到自身，这里可以看作权值合并的逆操作，而且这种合并可以路径压缩。

注意这种操作不应将根结点的权值合并，因为每次查询都一定会重复合并到其根结点，因此最好的办法就是在路径压缩时不合并根结点，最后在处理答案时再单独加上并特判根节点。

处理完右端点 j 的所有询问，更新其父亲节点为 j+1。

这么做的时间复杂度为 O(q\alpha(n))，其中 \alpha(n) 是反阿克曼函数，近似一个很小的常数，因此这种做法接近线性。相对于猫树，其常数与码量更小，还是比较巧妙的。

代码

#include<bits/stdc++.h>
#define Kei_love_ARIS return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define fi first
#define se second
#define int long long 
#define in(a) a = read()
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f; 
inline int read() {
    int x = 0;
    char ch = getchar();
    bool f = 0;
    while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();
    while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();
    return f ? -x : x;
}
int w[N] , fa[N];
struct node{
    int a , b , c , d , l , r , ls , rs;
    node() {
    }
    node(int l) {
        this->a = this->b = this->c = this->d = w[l];
        this->l = this->r = this->ls = this->rs = l;
    }
    node operator+(node &other) const{
        node ans;
        ans.c = max(c , b + other.c);
        if(ans.c == c) ans.ls = ls;
        else ans.ls = other.ls;
        ans.d = max(d + other.b , other.d);
        if(ans.d == d + other.b) ans.rs = rs;
        else ans.rs = other.rs;
        ans.b = b + other.b;
        ans.a = max(max(a , other.a) , d + other.c);
        ans.l = ans.r = inf;
        if(ans.a == a) {
            ans.l = l , ans.r = r;
        } 
        if(ans.a == d + other.c) {
            int nl = rs , nr = other.ls;
            if(nl < ans.l) ans.l = nl , ans.r = nr;
            else if(nl == ans.l) ans.r = min(ans.r , nr);
        } 
        if(ans.a == other.a){
            int nl = other.l , nr = other.r;
            if(nl < ans.l) ans.l = nl , ans.r = nr;
            else if(nl == ans.l) ans.r = min(ans.r , nr);
        }
        Kei_love_ARIS ans;
    }
}d[N];
int find(int x) { 
    if(fa[x] != fa[fa[x]]){ 
        int root = find(fa[x]);
        d[x] = d[x] + d[fa[x]]; 
        fa[x] = root; 
    }
    Kei_love_ARIS fa[x];
}
struct Q{
    int l , id;
};
vector<Q>q[N];
pair<int , int>ans[N];
signed main() {
    cin_fast;
    int o = 0;
    int n , m;
    while(cin>>n>>m){
        o ++;
        cout << "Case " << o << ":\n";
        for(int i = 1 ; i <= n ; i ++) cin>>w[i] , q[i].clear();
        for(int i = 1 ; i <= m ; i ++) {
            int l , r;
            cin >> l >> r;
            q[r].push_back({l , i});
        }
        for(int i = 1 ; i <= n ; i ++) fa[i] = i , d[i] = node(i);
        for(int i = 1 ; i <= n ; i ++) {
            node x = node(i);
            for(auto v : q[i]) {
                find(v.l);
                node now = d[v.l];
                if(v.l < i) now = now + x;
                ans[v.id] = make_pair(now.l , now.r);
            }
            fa[i] = i + 1;
        }
        for(int i = 1 ; i <= m ; i ++) {
            cout << ans[i].first << ' ' << ans[i].second << '\n';
        }
    }
    Kei_love_ARIS 0;
}
/*
这段记忆随雪花融化
留的空缺要如何充填
积雪伴随寒风飘下
怎样陷入这永恒的冬眠
this is ARIS0_0 8
*/