当前位置：网站首页>bzoj3693 圆桌会议 hall定理+线段树

bzoj3693 圆桌会议 hall定理+线段树

2022-08-08 14:58:00 【51CTO】

http://www.elijahqi.win/2018/03/06/bzoj3693/
Description
有n组人要一起开一个圆桌会议（编号为0~n-1），会议的圆桌上有m个位置（编号为0~m-1）。每个组有ai个人，他
们需要被安排在（li，(li+1)%m，(li+2)%m，…，ri）的座位范围内。每个座位只能安排一个人就坐，并且每个人
都需要被安排一个座位。现在你需要判断是否存在满足条件的座位安排。
Input
输入包含不超过10组数据。
第一行有一个数字T，表示数据组数。
接下来有T组数据，每组数据第一行包含两个数n，m，表示有多少组的人与圆桌的位置数。
每组数据接下来包含n行，每行包含3个数li，ri，ai。
Output
对于每组数据，输出”Yes”或”No”，表示是否存在符合条件的安排。
Sample Input
2

2 4

0 1 2

1 2 2

2 3

2 0 2

1 1 1

Sample Output
No

Yes

HINT

T≤10，其中有不超过3组的数据范围为n≤10^5，m≤10^9

可以考虑Hall定理即其中任意子集均满足条件针对每个询问针对区间内询问的ai求和可以满足一个关系 r-l+1>=s即满足条件设这个区间的和是s 那么s> r-l+1即s+l-1>r 那么我们只需要维护这个值支持快速的区间覆盖区间最大值即可线段树解决

按照右端点排序然后每次区间覆盖左端点然后查询也只查询到左端点即可 why因为右端点有序了不可能对左端点产生的影响我询问的时候还没处理好当我右端点单调后左端点的每个值就相当于左端的点到我当前右端点的这些区间包含多少a[i]

注意反例：来自leoly

m=5，两个条件：[1,3]，a1=2；[3,2]，a2=4，上述方法会判定为能满足。。

因为在查询[3,7]时，[1,3]和[6,8]均不包含于[3,7]，事实上是包含的([3,3]∪[6,7])。。

这种情况是把原区间从中间断开分到了两端。。

此时查询区间总长一定为m(两端能接成一个区间)，故事先特判总区间(所有ai之和<=m)即可。。好神啊

       
       #include<cstdio>
       
#include<algorithm>
       
#define N 220000
       
using namespace std;
       
inline char gc(){
       
    static char now[1<<16],*S,*T;
       
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
       
    return *S++;
       
}
       
inline int read(){
       
    int x=0,f=1;char ch=gc();
       
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
       
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
       
    return x*f;
       
}
       
struct node{
       
    int l,r,a;
       
}qr[N];
       
inline bool cmp(const node &a,const node &b){
       
    return a.r<b.r;
       
}
       
struct node1{
       
    int left,right,mx,add;
       
}tree[N<<2];
       
int num,nn,n,m,aa[N<<2],root;
       
inline void update(int x){
       
    int l=tree[x].left,r=tree[x].right;
       
    tree[x].mx=max(tree[l].mx,tree[r].mx);
       
}
       
inline void pushdown(int x){
       
    if (!tree[x].add) return;
       
    int l=tree[x].left,r=tree[x].right,ad=tree[x].add;
       
    if (l)tree[l].add+=ad,tree[l].mx+=ad;
       
    if (r)tree[r].add+=ad,tree[r].mx+=ad;tree[x].add=0;
       
}
       
inline void build(int &x,int l,int r){
       
    x=++num;tree[x].left=tree[x].right=tree[x].mx=tree[x].add=0;
       
    if (l==r) {tree[x].mx=aa[l]-1;return;}
       
    int mid=l+r>>1;build(tree[x].left,l,mid);
       
    build(tree[x].right,mid+1,r);update(x);
       
}
       
inline void insert1(int x,int l,int r,int l1,int r1,int v){
       
    if (l1<=l&&r1>=r) {tree[x].mx+=v;tree[x].add+=v;return;}
       
    int mid=l+r>>1;pushdown(x);
       
    if (l1<=mid) insert1(tree[x].left,l,mid,l1,r1,v);
       
    if (r1>mid) insert1(tree[x].right,mid+1,r,l1,r1,v);update(x);
       
}
       
inline int query(int x,int l,int r,int l1,int r1){
       
    if (l1<=l&&r1>=r) return tree[x].mx;pushdown(x);int mid=l+r>>1,tmp=0;
       
    if (l1<=mid) tmp=max(tmp,query(tree[x].left,l,mid,l1,r1));
       
    if (r1>mid) tmp=max(tmp,query(tree[x].right,mid+1,r,l1,r1));return tmp;
       
}
       
inline void print(int x){
       
    pushdown(x);
       
    if (tree[x].left) print(tree[x].left);
       
    printf("%d,tree[x].mx);
       
    if (tree[x].right) print(tree[x].right);
       
}
       
int main(){
       
    freopen("bzoj3693.in","r",stdin);
       
    int T=read();
       
    while(T--){
       
        n=read();m=read();int tot=n,sum=0;nn=0;
       
        for (int i=1;i<=n;++i){
       
            qr[i].l=read()+1;qr[i].r=read()+1;qr[i].a=read();sum+=qr[i].a;
       
            if (qr[i].l>qr[i].r) qr[i].r+=m;else qr[++tot].l=qr[i].l+m,qr[tot].r=qr[i].r+m,qr[tot].a=qr[i].a;
       
        }if (sum>m) {puts("No");continue;}num=0;
       
        for (int i=1;i<=tot;++i) aa[++nn]=qr[i].l,aa[++nn]=qr[i].r;
       
        sort(aa+1,aa+nn+1);nn=unique(aa+1,aa+nn+1)-aa-1;
       
        //for (int i=1;i<=nn;++i) printf("%d,aa[i]);puts("");
       
        sort(qr+1,qr+tot+1,cmp);build(root,1,nn);bool flag=0;
       
        //print(root);
       
        for (int i=1;i<=tot;++i){
       
            int l=lower_bound(aa+1,aa+nn+1,qr[i].l)-aa;
       
            int r=lower_bound(aa+1,aa+nn+1,qr[i].r)-aa;
       
            insert1(root,1,nn,1,l,qr[i].a);
       
            if (query(root,1,nn,1,l)>aa[r]) {flag=1;break;}
       
        }if (flag) puts("No");else puts("Yes");
       
    }
       
    return 0;
       
}
      
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.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5555925

当前位置：网站首页>bzoj3693 圆桌会议 hall定理+线段树

bzoj3693 圆桌会议 hall定理+线段树

边栏推荐

猜你喜欢

随机推荐