JOI2017春季合宿 切符の手配(Arranging Tickets)

题目大意

有$n$个车站按照顺时针顺序围成一圈,编号为$1,2,…,n$。
有$n$种车票,其中第$i$种车票可以从第$i$个车站前往第$i+1$个车站,也可以从第$i+1$个车站前往第$i$种车站。
有$m$类旅客,第$i$类旅客总共有$c_i$人,要从第$a_i$个车站前往第$b_i$个车站(可以走两个方向)。
你要给每一个旅客决定出行路线,最小化所有种类的车票需要数目的最大值。

$3\leq n\leq2\times10^5,1\leq m\leq10^5$


题目分析

这是一道非常难的题目,需要发现很多性质,证明一些结论。感谢lych_cys耐心教做人qwq

$O(mn^2\log^2n)$(保证$c_i=1$)

首先我们肯定要破环为链,考虑将问题转化成这样:
一个数轴上有$n$个整点,$m$种区间。第$i$种区间覆盖了$[a_i,b_i)$的整点,有$c_i$个。
你可以选择一些区间翻转,原本覆盖$[l,r)$的现在覆盖$[1,l)\bigcup[r,n]$。
请最小化被覆盖的最多的整点被覆盖的次数。
显然,答案具有二分性:如果答案$ans$是可行的,那么$ans+1,ans+2,…$直到理论上界都是可行的。因此考虑二分答案并判定。
我们可以得到一个观察结论:对于区间$[l,r)$和区间$[x,y)$,如果$l\lt r\leq x\lt y$,即区间没有交,它们不可能同时翻转(画一画就知道不翻转显然会更优)。
也就是说所有翻转的区间,一定会有至少一个公共的交点,我们设它为$t$。
考虑枚举这个$t$,然后判定答案是否可行。
假设我们总共需要翻转$cnt$次,答案为$ans$,这两个都是判定前需要确定的参数。
判定过程是这样一个贪心的过程:

  • 维护一个大根堆。
  • For $i=1$ -> $t$
    – 将所有左端点在$i$的,右端点$r>t$的区间都丢到堆里面,关键字是右端点。
    – 如果当前已经翻转过的区间个数还没有达到这个位置合法所需要的次数,选择堆顶区间翻转,如果堆为空返回不合法。
  • 最后检验一次方案是否合法。

注意到我们是按照左端点从小到大的顺序贪心,因此后面的翻转决策可能会导致前面的位置被覆盖次数增加,所以我们不可以单纯按照当前位置初始覆盖次数和$ans$来决定选取的区间个数。
假设前面当前位置现在(即考虑了前面的翻转造成的贡献)被覆盖次数是$y$,后面还有$T$次翻转操作。
那么当前翻转次数$x$应当满足$y-x+T-x\lt ans$。我们取合法的$x$的最小值即可。
注意到上面我们是假定了后面$T$次翻转操作都是会造成当前位置被覆盖次数增加,但实际上并不一定。
不过没有关系,假设后面的实际上造成的当前位置被覆盖次数减少,前面这一次翻转也并不是多余的(不然就不会有后面这一次翻转),而且次数减少的话依然是合法的。
这个贪心为什么是对的呢?
首先它的答案肯定是合法的,因为我们最后会检测一次。
其次,可以发现这个贪心使得$1…t$都合法的同时,最小了$t+1…n$被覆盖的次数(每次都是取右端点最大的区间)。
于是我们二分$ans$,枚举交集的一个点$t$和翻转总次数$cnt$。
当$c_i=1$的时候我们得到了一个$O(mn^2\log^2n)$的多项式做法。
然后可以发现我们有两个复杂度瓶颈:一个是枚举的总翻转次数$cnt$,一个是交集的其中一个位置$t$。
我们要将这两个东西优化下来才可以通过这道题目。

$O(n^2\log^2n)$

我们先来解决第一个问题,在后面的论证中你可以看到,$cnt$其实只需要取两个值检验就好了。
我们假定$a_i$表示的是最初状态下每一个整点被覆盖的次数。
$b_i$表示的是翻转了之后每一个整点被覆盖的次数。
假设有一种最优方案翻转的区间的交集是$[l,r)$,我们取$b_l,b_{l+1},…,b_{r-1}$里面最大的作为$b_t$。

定理:一定存在一种最优的翻转方案,使得$b_t=\max b_i$或者$b_t=\max b_i-1$。
证明:
假定存在一个最优的方案不满足这个上界。$\max b_i$显然不在$[l,r)$。
在所有已经翻转的区间中,我们选择右端点最左的和左端点最右的,它们的交集肯定是$[l,r)$。考虑取消翻转这两个区间(也可能是同一个,没有关系)。
首先最大值肯定不会增加(增加的只有$[l,r)$),其次所有位置肯定依然合法,最后可以发现$b_t$增加了$1$或者$2$。
如果此时还不满足条件,继续做这个过程。最后一定能使得$b_t$达到这个上界。证毕。

又因为在有解的情况下$\max b_i$一定会等于$ans$。
于是我们只需要检验$a_t-ans$或者$a_t-(ans-1)$即可。
时间复杂度成功降成了$O(n^2\log^2n)$。而且现在复杂度和$c_i$的取值没有任何关系了!

$O(n\log^2n)$

然后我们要优化掉最后一个瓶颈$t$。

定理:最优解的$t$一定满足$a_t=\max a_i$。

证明:
假设存在最优解,使得$a_t\neq\max a_i$。假设取反的区间交集是$[l,r)$,那么也就是说存在$i\not\in [l,r)$使得$a_i\geq a_t+1$。
因为$i$不在$[l,r)$,因此一定有一个区间翻转之后覆盖了$i$。
于是肯定有$b_i-a_i\geq b_t-a_t+1$,结合$a_i\geq a_t+1$移项得到$b_t+2\leq b_i$。
和前面的事实矛盾!证毕。

虽然我们确定了$a_t$的取值,但是万一我有好几个$a_t=\max a_i$,那依然要一个一个检测。

这时候我们需要最后一个定理:$t$只需要取满足$a_t=\max a_i$的最左或者最右的$t$就好了。

证明:依然是使用反证法。假设$a_l,a_r$是满足条件的最左/最右值,然后假设最优解选择了$a_t(l\lt t\lt r)$。
我们只需要证明所有覆盖的区间,要么都覆盖了$a_l$,要么都覆盖了$a_r$。
首先因为我们选择了$a_t$,显然没有区间$[x,y)$满足$y\leq l$或者$x>r$。

引理一:不存在区间$[x,y)$满足$l\lt x\lt y\leq r$。

证明:
假定我们不翻转这个区间,对应的$b$数组是$b’$,于是我们可以得到$b’_t=b_t+1,b’_l=b_l-1$。
在不翻转这个区间的时候,显然还是满足$b’_t-a_t\leq b’_l-a_l$,从而有$b’_l\geq b’_t$。
然后就有$b_l\geq b_t+2$,和前面的事实矛盾,证毕!

引理二:假设存在两个区间$[x_1,y_1),[x_2,y_2)$,满足$y_2\leq r$且$x_1>l$。我们同时取消翻转它们,答案不会更劣。

证明:
首先显然有$\max\{b_l,b_{l+1},…,b_r\}=\max(b_i)$。$b’$同理。
那么就有$\max b_i=\max_{i\in[1,l]\bigcup[r,n]}\{b_i\}$。$b’$同理。
显然同时翻转这两个区间,$\max b_i\geq\max b’_i$。证毕。

综上,我们二分答案$ans$,然后取$t$为使得$a_t$最大的位置中最左位置和最右位置,取$cnt=a_t-ans$或$a_t-(ans-1)$,用数据结构贪心检验一下就好了。
时间复杂度$O(n\log^2n)$。


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstdio>
#include <cctype>
#include <vector>
#include <queue>

using namespace std;

typedef long long LL;

inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}

typedef pair<int,int> P;
#define mkp(a,b) make_pair(a,b)
#define ft first
#define sd second

const LL INF=LLONG_MAX;
const int N=200005;
const int M=100005;

LL tag[N],need[N],sum[N];
int a[M],b[M],c[M];
int n,m,la,ra;
LL mx;

priority_queue<P> q;
vector<P> range[N];

inline bool check(LL rvs,int t,LL lim)
{
if (rvs>lim) return 0;
for (int i=1;i<t;++i) need[i]=max(sum[i]+rvs-lim+1>>1,0ll);
need[t]=rvs;
for (int i=1;i<=n;++i) range[i].clear(),tag[i]=0;
for (;!q.empty();q.pop());
for (int i=1;i<=m;++i) if (a[i]<=t&&b[i]>t) range[a[i]].push_back(mkp(b[i],c[i]));
LL cur=0,tmp;
for (int i=1;i<=t;++i)
{
for (auto rg:range[i]) q.push(rg);
for (tmp=need[i]-cur;tmp>0&&!q.empty();)
{
P rg=q.top();q.pop();
if (tmp<rg.sd) cur+=tmp,rg.sd-=tmp,q.push(rg),tag[t]-=tmp,tag[rg.ft]+=tmp<<1,tag[n]-=tmp,tmp=0;
else cur+=rg.sd,tag[t]-=rg.sd,tag[rg.ft]+=rg.sd<<1,tag[n]-=rg.sd,tmp-=rg.sd;
}
if (tmp>0) return 0;
}
for (int i=t+1;i<=n;++i) if ((tag[i]+=tag[i-1])+sum[i]>lim) return 0;
return 1;
}

inline bool judge(LL lim){return check(mx-lim,la,lim)||check(mx-lim+1,la,lim)||check(mx-lim,ra,lim)||check(mx-lim+1,ra,lim);}

LL binary_search()
{
LL l=0,r=mx-1,ret=mx;
for (LL mid;l<=r;)
{
mid=l+r>>1;
if (judge(mid)) r=(ret=mid)-1;
else l=mid+1;
}
return ret;
}

int main()
{
freopen("tickets.in","r",stdin),freopen("tickets.out","w",stdout);
n=read(),m=read();
for (int i=1;i<=m;++i)
{
a[i]=read(),b[i]=read(),c[i]=read();
if (a[i]>b[i]) swap(a[i],b[i]);
sum[a[i]]+=c[i],sum[b[i]]-=c[i];
}
for (int i=1;i<=n;++i) sum[i]+=sum[i-1];
mx=-INF;
for (int i=1;i<=n;++i) mx=max(sum[i],mx);
for (int i=1;i<=n;++i)
if (sum[i]==mx)
{
if (!la) la=i;
ra=i;
}
printf("%lld\n",binary_search());
fclose(stdin),fclose(stdout);
return 0;
}