圆桌会议[bzoj3693]

发表于 分类于

题意

$n$ 组人，第 $i$ 组 $a_i$ 个人，需要安排在一个$m$ 个座位的，编号为 $0,1,\cdots,m-1$ 的圆桌上，每个位置只能最多做一个人。

其中第 $i$ 组的人能坐在 ${ l_i,(l_i+1)%m,(l_i+2)% m,\cdots,r_i}$的位置上。

问是否存在一种合法的安排。

$n\leq 10^5,m\leq 10^9$

题解

容易想到建一个二分图，然后变成判断是否存在完美匹配的问题。

我们发现，尽管现在是在环上，但Hall定理的结论1仍然成立。

就可以先考虑简单一点的，在一条链上而不是在一个环上的情况。考虑完链的情况以后破环成链就能解决。

根据Hall定理的结论，我们需要对所有的区间 $[L,R]$ 都查询一遍看是否符合。

但十分显然的，我们只需要考虑 $R=r_i$ 的区间就可以了。

我们需要区间 $[L,R]$ 满足：$\sum a_i\leq R-L+1$，即 $(\sum a_i)+L\leq R+1$

那么把区间按右端点排序，然后枚举区间。每次在 $[1,l_i]$ 中加 $a_i$，查询 $[1,r_i]$ 中 $(\sum a)+L$ 的最大值，看是否小于等于 $R+1$ 即可。

环的话破环成链就可以了。

注意判断 $r_i=l_i-1$ 的情况。

时间复杂度 $O(n\log n)$

程序

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
#define N 400010
struct node{
	int l,r,a;
	friend inline bool operator<(const node &A,const node &B){return A.r<B.r;}
}q[N>>1];
int n,m,a[N];

int ls[N<<1],rs[N<<1],mx[N<<1],tag[N<<1],cnt;
inline void pushtag(int u,int x)
{
	if(!u) return;
	mx[u]+=x; tag[u]+=x;
}
inline void pushdown(int u)
{
	if(!tag[u]) return;
	pushtag(ls[u],tag[u]);
	pushtag(rs[u],tag[u]);
	tag[u]=0;
}
int build(int l,int r)
{
	int u=++cnt;
	if(l==r) {mx[u]=a[l]; return u;}
	int mid=l+r>>1;
	ls[u]=build(l,mid);
	rs[u]=build(mid+1,r);
	mx[u]=max(mx[ls[u]],mx[rs[u]]);
	return u;
}
void add(int u,int l,int r,int L,int R,int x)
{
	if(L<=l&&r<=R) return pushtag(u,x);
	pushdown(u);
	int mid=l+r>>1;
	if(L<=mid) add(ls[u],l,mid,L,R,x);
	if(mid<R)  add(rs[u],mid+1,r,L,R,x);
	mx[u]=max(mx[ls[u]],mx[rs[u]]);
}
int ask(int u,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return mx[u];
	int mid=l+r>>1,mx=0;
	pushdown(u);
	if(L<=mid) mx=max(mx,ask(ls[u],l,mid,L,R));
	if(mid<R)  mx=max(mx,ask(rs[u],mid+1,r,L,R));
	return mx;
}
ll sum;
inline void init()
{
	sum=0;
	fo(u,1,cnt) ls[u]=rs[u]=tag[u]=mx[u]=0;
	cnt=0;
}
#define pos(x) lower_bound(a+1,a+tot+1,(x))-a
int main()
{
	for(int _=read(),tot,n_tot;_--;)
	{
		n_tot=n=read(); m=read();
		init();
		fo(i,1,n)
		{
			q[i].l=read()+1,q[i].r=read()+1;
			sum+=(q[i].a=read());
			if(q[i].r==q[i].l-1) q[i].l=1,q[i].r=m;//特判
			else if(q[i].l>q[i].r) q[i].r+=m;
			else q[++n_tot]=(node){q[i].l+m,q[i].r+m,q[i].a};
		}
		if(sum>m) {puts("No"); continue;}
		n=n_tot; tot=0;
		fo(i,1,n) a[++tot]=q[i].l,a[++tot]=q[i].r;
		sort(a+1,a+tot+1); tot=unique(a+1,a+tot+1)-a-1;
		sort(q+1,q+n+1);
		build(1,tot);
		int l,r;  bool flag=1;
		fo(i,1,n)
		{
			l=pos(q[i].l); r=pos(q[i].r);
			add(1,1,tot,1,l,q[i].a);
			int p=ask(1,1,tot,1,r);
			if(p>q[i].r+1) {flag=0; break;}
		}
		puts(flag?"Yes":"No");
	}
	return 0;
}