题解 AT2536 切符の手配 (Arranging Tickets)

· · 题解

JOISC 2017 Day2 T1，神题。

我们转化一下题意，转化为有若干个区间 [l,r]，你可以选择一些区间将其覆盖的范围反转成 [1,l-1] 和 [r+1,n] 使得所有位置被覆盖次数的最大值最小。我们先设不将区间反转时每个位置被覆盖次数为 a_i，定义确定一种反转方案后每个位置的覆盖次数为 b_i。

因为如果为空，那么一定能找到两个反转的区间使得它们不交。如果两个区间不交，那么将其反转肯定不优，因为会覆盖原来有的位置。

也就是说，我们一定能找到一个位置 x 使得这个位置被所有反转的区间所包含。

先二分答案 mid 表示最大的覆盖次数。设 pre_i(1\leq i\leq x) 为第 i 个位置被反转的区间包含的个数，即反转区间中左端点小于等于 i 的个数。那么可以得到当前方案下 b_i=a_i-pre_i+pre_x-pre_i。又因为 b_i\leq mid，所以 a_i-pre_i+pre_x-pre_i\leq mid，pre_i\geq \left\lceil \frac{a_i+pre_x-mid}{2}\right\rceil，我们得到了 pre_i 的下界。

也就是说我们先枚举 x 再枚举 pre_x 然后再贪心将 pre_i 补齐到下界即可，具体做法就是每次选当前能选的右端点最大的区间反转。最后判一下 [x+1,n] 的这段是否合法。

时间复杂度 O(n^3\log n \log V)。

接下来的部分就越来越牛了。

证明考虑如果当前 b_x\leq \max(b_i)-2 并且是当前被所有反转区间包含的位置中 b 的最大值，那么设 \max(b_i) 的 i 为 t，所有反转区间的交为 [L,R]。我们取消反转一个左端点为 L 的区间和一个右端点为 R 一定能更优。

也就是说我们不用枚举 pre_x 了。

时间复杂度变成了 O(n^2 \log n\log V) 。

考虑性质 2 反证，假设 a_y>a_x，首先 y 不在 [L,R] 中，所以有 a_y-a_x\geq 1，又因为性质二有 b_x-b_y\geq -1，所以 a_y-b_y+b_x-a_x\geq 0，所以 a_y-b_y\geq a_x-b_x 然后你会发现因为 a_x-b_x 等于所有反转的区间的个数，显然 a_y-b_y 不可能大于等于这个。

证明方法和性质 3 的方法差不多，考虑性质 2 反证即可，留给读者思考。

代码难度很小，但是这个思考真的很神，从一个看上去复杂度上天的做法通过不断证明合法的位置只有 O(1) 个优化到了 O(n\log n\log V) 的做法。

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long 
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define int ll
#define N 300005
using namespace std;
inline char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
#define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int f[N],b[N],Pre[N],l[N],r[N],w[N];
vector<pa>G[N];
int a[N];
int n,m;
int nowx;
int ans,ans1;
bool chk(int x,int y)
{
    for (int i=1;i<=n;i++)
        Pre[i]=0,f[i]=0,b[i]=0;
    Pre[nowx]=a[nowx]-x+y;
    for (int i=1;i<=nowx;i++)
        Pre[i]=max(0ll,(int)((a[i]+Pre[nowx]-x+1)/2));
    priority_queue<pair<pa,int>>q;
    int nowy=0;
    for (int i=1;i<=nowx;i++)
    {
        for (auto U:G[i])
        {
            int u=U.fi,w=U.se;
            if (u>=nowx)
            {
                q.push(mp(mp(u,i),w));
            }
        }
        while (!q.empty()&&f[i]+nowy<Pre[i])
        {
            int x=q.top().fi.se,y=q.top().fi.fi,w=q.top().se;
            q.pop();
            if (f[i]+w+nowy>Pre[i])
            {
                int z=min(Pre[i]-f[i]-nowy,w);
                nowy+=z;
                b[x]-=z,b[y+1]+=z;
                b[1]+=z,b[x]-=z,b[y+1]+=z;
                q.push(mp(mp(y,x),w-z));
                break;
            }
            int z=w;
            nowy+=z;
            b[x]-=z,b[y+1]+=z;
            b[1]+=z,b[x]-=z,b[y+1]+=z;
        }
        if (f[i]+nowy<Pre[i]) return 0;
    }
    for (int i=1;i<=n;i++) b[i]+=b[i-1];
    for (int i=1;i<=n;i++)
        if (b[i]+a[i]>x) return 0;
    return 1;
}

void BellaKira()
{
    n=read(),m=read();
    int t=0;
    int sg=0;
    for (int i=1;i<=m;i++)
    {
        l[i]=read(),r[i]=read(),w[i]=read();
        sg+=w[i];
        if (l[i]>r[i]) swap(l[i],r[i]);
        r[i]--;
    }
    for (int i=1;i<=m;i++) a[l[i]]+=w[i],a[r[i]+1]-=w[i],G[l[i]].push_back(mp(r[i],w[i]));
    nowx=0;
    for (int i=1;i<=n;i++)
    {
        a[i]+=a[i-1];
        if (a[i]>a[nowx]) nowx=i;
    }
    int l=0,r=sg;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        if (chk(mid,0)||chk(mid,1)) 
        {
            ans1=mid;
            r=mid-1;
        } else l=mid+1;
    }
    writeln(ans1);
}
signed main()
{
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}
/*

*/