题解

题意重述：有一条 $N$ 站的环线，套餐内含 $N$ 张“边票”，第 $i$ 张可供一人往返通过边 $(i,i+1)$（$N\to 1$ 也算一条边）。有 $M$ 批需求，第 $i$ 批有 $C_i$ 人从 $A_i$ 到 $B_i$，每人可选顺时针或逆时针路线。每走过一条边都要消耗该边的一张票。求最小套餐数 $X$ 使得能为所有人分配路径且任一边被使用不超过 $X$ 次。

建模与等价转化：

• 若先令所有人都选顺时针，则每条边 $e$ 的使用次数可通过差分前缀得到数组 $a[1\ldots N]$，其中 $a[i]$ 表示边 $(i,i+1)$ 被顺时针选择时的累计通过人数。
• 将某一批需求改为逆时针，等价于：其顺时针覆盖的边负载 $-1$，逆时针补集上的边负载 $+1$。因此只有那些“顺时针路径覆盖边 $pos$”的需求被反向，才能降低边 $pos$ 的负载。
• 设 $pos=\arg\max_i a[i]$，直觉上最优解会尽力降低该“瓶颈边”的负载，并保证其它边也不超过同一上界 $mid$。于是我们只考虑“包含 $pos$ 的顺时针区间集合”，从中挑选若干批次反向。

二分答案 + 线性可行性：

• 对答案 $mid$ 二分。给定一个 $mid$，问能否通过把“覆盖 $pos$ 的顺时针区间”中的若干批改为逆时针，使得所有边负载 $\le mid$。
• 记选择反向的、且覆盖 $pos$ 的总人数为 $cnt$。对每条边 $i$，要满足$$a[i] - f(i) + g(i) \le mid,$$ 其中 $f(i)$ 为被反向、且原本顺时针覆盖边 $i$ 的总人数，$g(i)$ 为被反向、且原本顺时针不覆盖 $i$（即覆盖补集）的总人数。对“仅从覆盖 $pos$ 的区间中选人反向”这一策略，有 $g(pos)=0$ 且 $f(pos)=cnt$。
• 将上式整理为对每个 $i$ 的“至少需要反向的覆盖 $i$ 的人数”下界：$$L[i] = \left\lceil \frac{a[i] + cnt - mid}{2} \right\rceil, $$并强制 $L[pos]=cnt$。直观理解：想让边 $i$ 的负载不超过 $mid$，就必须有至少 $L[i]$ 的“覆盖 $i$ 的顺时针区间”被反向（这些区间也都覆盖 $pos$，我们只在这类区间中选）。

区间贪心装入（优先队列）：

• 把所有“覆盖 $pos$ 的顺时针区间”视作在线段 $[1,\ldots,pos]$ 上起点为 $l$、终点为 $r$ 的闭区间，权重为可反向人数 $w$，并归入桶 $v[l]$。
• 从 $i=1\to pos$ 扫描，维护一个按“右端点 $r$ 优先”的优先队列。当来到位置 $i$，将所有起点为 $i$ 的区间入堆；若当前堆中总可用人数 $now$ 小于需求 $L[i]$，就贪心地从“最靠右的区间”取人数补足（取到终点后用差分数组把人数在 $r+1$ 位置删除）。若在某个 $i$ 无法补足，则该 $mid$ 不可行。
• 扫描 $pos+1\to N$ 只需按差分回退人数并检查不出现“过度使用”的情形。
• 外层二分 $mid\in[0,a[pos]]$。实现中对 $cnt$ 与取整的细节，用两次 check(a[pos]-mid, mid) 和 check(a[pos]-mid+1, mid) 兜底以处理奇偶与边界。

正确性要点：

• 只从“覆盖 $pos$”的区间里反向是无损的：反向不覆盖 $pos$ 的区间只会增加 $a[pos]$，不利于降低最大值。
• 扫描时用“最靠右优先”的贪心满足每个位置的最小需要量 $L[i]$，是典型的区间覆盖最小失效策略，避免把短区间留到其未来唯一可用的位置之外，保证可行则能装满。

复杂度：

• 每次可行性检查线性（堆操作均摊）$O(N\log N)$ 或 $O(N)$（若使用双端队列优化），二分 $\log a[pos] \le \log \sum C_i$，总复杂度约 $O((N+M)\log \sum C)$，空间 $O(N+M)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4e5+5,M=4e5+5;
ll n,m,a[N],c[N],d[N],L[N],pos,p1[N],p2[N],w[N];
struct line{ll r,w;};vector<line>v[N]; 
inline bool operator < (line x,line y){return x.r<y.r;}
priority_queue<line> que;
bool check(ll cnt,ll mid){
	if(cnt<0) return 0;
	for(ll i=1;i<=n;i++) L[i]=(a[i]+cnt-mid+1ll)/2ll,d[i]=0ll;
//	for(ll i=1;i<=n;i++) printf("%lld ",L[i]); puts("");
	L[pos]=cnt; while(!que.empty()) que.pop();
	ll now=0ll;
	for(ll i=1,x;i<=pos;i++){
		for(line e:v[i]) que.push(e);
		while(now<L[i]){
			if(!que.empty()){
				line e=que.top(); que.pop();
				x=min(e.w,L[i]-now);
				d[e.r+1ll]+=x,e.w-=x,now+=x;
				if(e.w>=1ll) que.push(e);
			}
			else return 0;}
	}
	for(ll i=pos+1;i<=n;i++){
		now-=d[i];
		if(now<L[i]) return 0;}
	return 1;
}
void work(){
	ll l=0,r=a[pos],mid;
	while(l<r){
		mid=l+r>>1ll;
//	mid=0;
		//	枚举 pos 被逆区间集包含数
		if(check(a[pos]-mid,mid)) r=mid;
		else if(check(a[pos]-mid+1,mid)) r=mid;
		else l=mid+1;
	}
	printf("%lld\n",r);
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld%lld",&p1[i],&p2[i],&w[i]);
		if(p1[i]==p2[i]){p1[i]=p2[i]=-1;continue;}
		if(p1[i]>p2[i]) swap(p1[i],p2[i]); p2[i]--;
		a[p1[i]]+=w[i],a[p2[i]+1]-=w[i];}
	for(ll i=1;i<=n;i++) a[i]+=a[i-1];
//	for(ll i=1;i<=n;i++) printf("%lld ",a[i]); puts("");
	pos=1; for(ll i=1;i<=n;i++) if(a[i]>a[pos]) pos=i;
	for(ll i=1;i<=m;i++)
		if((p1[i]<=pos)&&(pos<=p2[i]))
			v[p1[i]].push_back((line){p2[i],w[i]});
	work();
	return 0;}