传送门
对于圆环问题,先复制一遍转区间。
对于一个区间,这个区间包含的所有a的和,肯定要小于等于座位数和。这是hall定理(当然生活常识也知道凳子至少要比人多)
对于任意一个区间都要如此。
因为是包含,所以我们只需要管端点是问题的l,r端点就可以。
也就是说对于任何
转换一下就是
这样就是一个可以按顺序维护的东西了。线段树维护sum+L-1,我们按右端点sort,然后依次查询。
对于查询,很明显只有在本询问的l右边一直到r的key才会有贡献。查询最大值。
对于修改,很明显对于包含本询问的才有a_i的贡献,所以1~l_i修改。
区间修改,区间最大值。
记得离散化
#include<bits/stdc++.h> using namespace std; #define in read() #define int long long int in{ int cnt=0,f=1;char ch=0; while(!isdigit(ch)){ ch=getchar();if(ch=='-')f=-1; } while(isdigit(ch)){ cnt=cnt*10+ch-48; ch=getchar(); }return cnt*f; } struct node{ int l,r,key,tag; }t[1200003]; int T,n,m; struct bili{ int l,r,key; }que[200003]; bool cm(bili a,bili b){ return a.r<b.r; } void pushup(int u){ t[u].key=max(t[u*2].key,t[u*2+1].key); }int b[800003],bcnt; void pushdown(int u){ if(t[u].tag){ int x=t[u].tag;t[u].tag=0;t[u*2].key+=x;t[u*2+1].key+=x; t[u*2].tag+=x;t[u*2+1].tag+=x; } } void build(int u,int l,int r){ t[u].l=l;t[u].r=r;t[u].tag=t[u].key=0; if(l==r)return (void)(t[u].key=b[l]-1);int mid=(l+r)>>1; build(u*2,l,mid);build(u*2+1,mid+1,r);pushup(u); } int query(int u,int ql,int qr){ //if(t[u].l>qr||t[u].r<ql)return -0x3f3f3f3f; if(ql<=t[u].l&&t[u].r<=qr)return t[u].key; pushdown(u);int mid=(t[u].l+t[u].r)>>1;int ans; if(qr<=mid)ans=query(u*2,ql,qr); else if(ql>mid)ans=query(u*2+1,ql,qr); else ans=max(query(u*2,ql,qr),query(u*2+1,ql,qr)); pushup(u);return ans; } void modify(int u,int ql,int qr,int key){ if(t[u].r<ql||t[u].l>qr)return; if(ql<=t[u].l&&t[u].r<=qr){ t[u].key+=key;t[u].tag+=key;return; }pushdown(u); modify(u*2,ql,qr,key);modify(u*2+1,ql,qr,key); pushup(u); } signed main(){ T=in; while(T--){ //memset(t,0,sizeof(t)); int sum=0;n=in;m=in;for(int i=1;i<=n;i++){ que[i].l=in+1;que[i].r=in+1;sum+=que[i].key=in;if(que[i].r<que[i].l)que[i].r+=m; }int cnt=n; for(int i=1;i<=cnt;i++){ if(que[i].r>m)continue; que[++n]=que[i];que[n].l+=m;que[n].r+=m; } if(sum>m){ cout<<"No"<<'\n';continue; }bcnt=0; for(int i=1;i<=n;i++){ b[++bcnt]=que[i].l;b[++bcnt]=que[i].r; } sort(b+1,b+bcnt+1);int len=bcnt; sort(que+1,que+n+1,cm); for(int i=1;i<=n;i++){ que[i].l=lower_bound(b+1,b+len+1,que[i].l)-b; que[i].r=lower_bound(b+1,b+len+1,que[i].r)-b; } //cout<<"##"<<endl;for(int i=1;i<=n;i++)cout<<que[i].l<<" "<<que[i].r<<endl;cout<<"##"<<endl; build(1,1,n<<1);int flag=0; for(int i=1;i<=n;i++){ modify(1,1,que[i].l,que[i].key); int gu=query(1ll,max(1ll,que[i].r-m+1),que[i].r); //cout<<gu<<"#gu "<<endl; if(gu>b[que[i].r]){ flag=1;break; } } if(flag)cout<<"No"<<'\n';else cout<<"Yes"<<'\n'; } return 0; }