1 条题解
-
1
首先,对于圆环问题,我们肯定要复制加倍转成区间。
然后根据 Hall 定理可得:,即 。
考虑线段树维护 ,我们按右端点排序,离散化,然后依次查询。
对于修改,只有包含询问的才有 的贡献,所以 修改。
对于查询,只有询问的 右边一直到 的 才会有贡献,维护最大值。
//bzoj#3693. 圆桌会议 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; /***********Basic Defination***********/ #define int long long const int MAXN=200005; struct Attendee { int l,r,a; }s[MAXN]; int b[MAXN<<1],cnt,n,m; bool operator <(Attendee x,Attendee y) { return x.r<y.r; } /***********Segment Tree***********/ struct Segt { int val,lazy; }tr[MAXN*6]; void pushup(int p) { tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val); return; } void build(int p,int l,int r) { int mid; tr[p].val=tr[p].lazy=0; if(l==r) { tr[p].val=b[l]-1; return; } mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); pushup(p); return; } void pushdown(int p) { if(tr[p].lazy) { tr[p<<1].val+=tr[p].lazy; tr[p<<1|1].val+=tr[p].lazy; tr[p<<1].lazy+=tr[p].lazy; tr[p<<1|1].lazy+=tr[p].lazy; tr[p].lazy=0; } return; } void update(int p,int l,int r,const int L,const int R,int c) { int mid; if(L>r||R<l) { return; } if(L<=l&&r<=R) { tr[p].val+=c; tr[p].lazy+=c; return; } pushdown(p); mid=(l+r)>>1; update(p<<1,l,mid,L,R,c); update(p<<1|1,mid+1,r,L,R,c); pushup(p); return; } int query(int p,int l,int r,const int L,const int R) { int mid,res; if(L<=l&&r<=R) { return tr[p].val; } pushdown(p); mid=(l+r)>>1; if(R<=mid) { res=query(p<<1,l,mid,L,R); } else if(L>mid) { res=query(p<<1|1,mid+1,r,L,R); } else { res=max(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R)); } pushup(p); return res; } signed main() { int t,sum,temp; bool flag; scanf("%lld",&t); while(t--) { sum=0; scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld%lld%lld",&s[i].l,&s[i].r,&s[i].a); s[i].l++; s[i].r++; sum+=s[i].a; if(s[i].r<s[i].l)//把环变成链 { s[i].r+=m; } } temp=n; for(int i=1;i<=temp;i++) { if(s[i].r>m) { continue; } s[++n]=s[i]; s[n].l+=m; s[n].r+=m; } if(sum>m) { printf("No\n"); continue; } cnt=0; for(int i=1;i<=n;i++)//离散化 { b[++cnt]=s[i].l; b[++cnt]=s[i].r; } sort(b+1,b+cnt+1); sort(s+1,s+n+1); temp=cnt; for(int i=1;i<=n;i++) { s[i].l=lower_bound(b+1,b+temp+1,s[i].l)-b; s[i].r=lower_bound(b+1,b+temp+1,s[i].r)-b; } build(1,1,n<<1); flag=true; for(int i=1;i<=n;i++) { update(1,1,n<<1,1,s[i].l,s[i].a); if(query(1ll,1,n<<1,max(1ll,s[i].r-m+1),s[i].r)>b[s[i].r]) { flag=false; break; } } printf(flag?"Yes\n":"No\n"); } return 0; } /* * HydroOJ-BZOJ * https://hydro.ac/d/bzoj/p/3693 * C++17 -O0 * 2022.10.11 */
- 1
信息
- ID
- 3693
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 28
- 已通过
- 8
- 上传者