题解 LOJ P2393 「JOISC 2017 Day 2」门票安排

题意

咕咕咕。

题解

这题太神了，无限膜拜 p_b_p_b，搬运一波题解。

首先考虑二分。题意等价于选一些区间进行反转。首先注意到反转的区间两两有交，不然不反转一定更优。设反转的区间交为 \([x,y]\)，反转前后位置 \(i\) 被覆盖的次数分别为 \(a_i,b_i\)。设 \(t\) 表示 \([x,y]\) 中 \(b\) 最大的位置，那么「容易」观察到：

• 存在最优方案使得 \(b_t \geq \max\{b_x\}-1\)

  如果不，考虑取消反转一个 \(l=x\) 的区间和 \(r=y\) 的区间，只有 \([x,y]\) 中的 \(b\) 会增加，因此对答案不劣。

• 存在最优方案使得 \(a_t = \max\{a_x\}\)

  如果 \(a_t\) 不是最大的，那么最大值 \(a_k\) 一定满足 \(k \notin [x,y]\)，否则 \(b_t\) 不是 \([x,y]\) 中最大的。因此至少一个被反转的区间没有覆盖到 \(k\)，于是 \(a_k - b_k \leq a_t - b_t - 1\)，化简得到 \(b_k - b_t \geq 2\)，与上一条矛盾。

• 存在最优方案使得所有 \(\max\{a_x\}\) 都满足 \(x \in [x,y]\)

  同上。

因此我们可以找到 \(t\) 的位置，然后分类讨论 \(b_t\) 是 \(\max\{b_x\}-1\) 还是取到了 \(\max\{a_x\}\)。

注意到我们二分了答案 \(mid\)，那么有 \(mid = b_t = a_t - cnt\)，或者 \(mid -1 = b_t = a_t - cnt\)，化简得 \(cnt = a_t - mid (+1)\)，其中 \(cnt\) 是反转的区间个数。

于是我们对于二分的答案 \(mid\)，分别检查反转区间个数为 \(a_t - mid\) 和 \(a_t - mid + 1\) 时是否合法即可。考虑如何判断：因为要反转的所有区间均跨过 \(t\)，我们不妨找出这些区间，根据左端点从 \(1\) 到 \(t\) 扫，因为我们知道总的反转区间数，于是可以顺便计算出当前还要反转的区间个数 \(cnt'\) 和已经反转了的区间个数 \(q\)。如果 \(a_i - q + cnt' > mid\)，那么位置 \(i\) 不合法，需要反转 \(\dfrac 12 (a_i - q + cnt')\) （上取整）个区间，因为 \(q\) 每增加 \(1\)，\(cnt'\) 就减少 \(1\)。如果没有足够的区间用来反转，那么不合法。否则我们贪心地选择右端点最大的区间进行反转，对后面的影响更小。

# include <bits/stdc++.h>
# define fir first
# define sec second

const int N=200010,INF=0x3f3f3f3f;

typedef long long ll;

int n,m;
int a[N],b[N],c[N];

ll v[N];
int mx;
typedef std::pair <int,int> pil;

std::vector <pil> seg[N];
std::priority_queue <pil> cur;

ll d[N];

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline bool check(ll lim,ll cnt){
	std::fill(d+1,d+1+n,0);
	while(!cur.empty()) cur.pop();
	ll reved=0;
	for(int i=1;i<=mx;++i){
		for(auto v:seg[i]) cur.push(v);
		while(v[i]-reved+cnt>lim){
			if(cur.empty()) return false;
			pil c=cur.top();
			cur.pop();
			ll crev=std::min(1ll*c.sec,(v[i]-reved+cnt-lim+1)/2);
			reved+=crev,cnt-=crev,d[mx+1]-=crev,d[c.fir]+=2*crev;
			
			if(crev<c.sec) cur.push(std::make_pair(c.fir,c.sec-crev));
		}
	}
	
	for(int i=mx+1;i<=n;++i){
		d[i]+=d[i-1];
		if(d[i]+v[i]>lim) return false;
	}
	
	return true;
}

int main(void){
	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]) std::swap(a[i],b[i]);
		v[a[i]]+=c[i],v[b[i]]-=c[i];
	}
	for(int i=1;i<=n;++i) v[i]+=v[i-1];
	for(int i=1;i<=n;++i) if(v[mx]<v[i]) mx=i;
	for(int i=1;i<=m;++i) if(a[i]<=mx&&b[i]>mx) seg[a[i]].push_back(std::make_pair(b[i],c[i]));
	
	ll l=0,r=v[mx],ans=1e18;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(mid,v[mx]-mid)||check(mid,v[mx]-mid+1)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
	
	return 0;
}