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

​​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])。。

#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;
}