Problem Link

[JOI 2021 Final] 雪玉

题目描述

翻译很简洁，不作赘述。

Solution

对于相邻的两个雪球 \(a_i\) 和 \(a_{i+1}\)，两者夹着的区间中的雪要么是被 \(a_i\) 或 \(a_{i+1}\) 卷起，要么不可能被清理掉。

那么思路非常简单了，对于每个区间，只有 \(2\) 种情况：

• 区间左侧雪球的最右点小于区间右侧雪球的最左点：两侧雪球各自加上自己卷起大小即可。

• 区间左侧雪球的最右点大于等于区间右侧雪球的最左点：二分计算各自卷起雪的多少即可。

其他疑问见代码。

Code

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

typedef long long ll;
#define Maxn 200005
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
inline ll lread(ll x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}

int n, m;
ll a[Maxn], l[Maxn], r[Maxn], ans[Maxn], sum;

int main()
{
    n = read(), m = read();
    fo(i, 1, n) a[i] = lread();
    fo(i, 1, m)
    {
        ll x = lread();
        sum += x;
        l[i] = max(l[i-1], -sum), r[i] = max(r[i-1], sum);
    }
    ans[1] += l[m], ans[n] += r[m];
    fo(i, 1, n-1)
    {
        if(l[m] + r[m] <= a[i+1]-a[i]) ans[i] += r[m], ans[i+1] += l[m]; // 两侧雪球没交集。
        else // 有交集。
        {
            int left = 1, right = m, pos = m;
            while(left <= right)
            {
                int mid = (left + right) >> 1;
                if(l[mid] + r[mid] > a[i+1]-a[i]) pos = mid, right = mid-1;
                else left = mid+1;
            }
            // 各自加上卷起的雪。
            if(l[pos-1] == l[pos]) ans[i+1] += l[pos], ans[i] += a[i+1]-a[i]-l[pos];
            else ans[i] += r[pos], ans[i+1] += a[i+1]-a[i]-r[pos];
        }
    }
    fo(i, 1, n) printf("%lld\n", ans[i]);
    return 0;
}

Tips

记得开 long long！