本文共 4422 字，大约阅读时间需要 14 分钟。

题解

首先我们可以发现，对于加上的最后一张牌，它一定会出现在一只手中，也就是说只有一只手是未知的。

于是我们很快想到了$dp$，定义$L_{i,j}$表示左手是第$i$张牌，右手是新加入的第$j$张牌时是否可行，定义$R_{i,j}$表示表示右手是第$i$张牌，左手是新加入的第$j$张牌时是否可行。 容易得到$dp$转移方程式，假设现在加入的是第$j$张牌， $$L_{i,j}=\left[a_i\in [a{l}_j,b{l}_j]\wedge a_j\in [a{r}_j,b{r}_j]\right]\left\{\begin{array}{rc}{L}_{i,j-1}& (i\ne j-1)\\ {\sum }_{k=1}^{k=j-2}{R}_{k,j-1}& (i=j-1)\end{array}\right\}$$ 同理，有 $$R_{i,j}=\left[a_i\in [a{r}_j,b{r}_j]\wedge a_j\in [a{l}_j,b{l}_j]\right]\left\{\begin{array}{rc}{R}_{i,j-1}& (i\ne j-1)\\ {\sum }_{k=1}^{k=j-2}{L}_{k,j-1}& (i=j-1)\end{array}\right\}$$

但很明显，如果我们直接进行$dp$的话是一定会$T$掉的，考虑通过线段树对转移进行优化。

如果通过线段树的话我们需要从新对状态进行一下定义，改称$L_i$为左手上的数为$i$的情况是否存在，$R_i$同理。 每次维护$L$与$R$状态的两棵线段树，每个节点表示这段区间是否可行。 对于每次不为$a_{j-1}$的点，我们只需要判断一下它是否在范围内，将范围外的点整体赋零即可。 而对于$a_{i-1}$，我们先看看另外一棵树上是否存在可行解，如果有的话，我们就可以从那边转移过来，也就是对这棵树进行单点修改，当然需要判断一下是否合法。

最后判断是否可行看有没有解即可，但构造一组解又该怎么办了？

我们可以记录一下在那些位置发生了$a_{j-1}$的转换，它有更新到哪里去了，再从末状态往前更新即可，这样就可以还原出来一组答案序列。 再将其输出即可。

时间复杂度$O\left(nlogm\right)$。

源码

#include
   
    using namespace std;#define MAXN 200005#define lowbit(x) (x&-x)#define reg register#define mkpr make_pairtypedef long long LL;typedef unsigned long long uLL;const int INF=0x3f3f3f3f;const int mo=1e9+7;const int iv2=5e8+4;const int lim=1000000;const int jzm=2333;const int orG=3,invG=332748118;const double Pi=acos(-1.0);typedef pair
    
      pii;template
     
      _T Fabs(_T x){
   return x<0?-x:x;}template
      
       void read(_T &x){
   	_T f=1;x=0;char s=getchar();	while(s>'9'||s<'0'){
   if(s=='-')f=-1;s=getchar();}	while('0'<=s&&s<='9'){
   x=(x<<3)+(x<<1)+(s^48);s=getchar();}	x*=f;}template
       
        void print(_T x){
   if(x<0){
   x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}int gcd(int a,int b){
   return !b?a:gcd(b,a%b);}int add(int x,int y){
   return x+y
        
         ai||r
         
          r)return ;if(!rt)rt=++tot; if(l==r){ tr[rt]=1;tim[rt]=aw;return ;}int mid=l+r>>1;pushdown(rt); if(ai<=mid)insert(ch[rt][0],l,mid,ai,aw); if(ai>mid)insert(ch[rt][1],mid+1,r,ai,aw); pushup(rt); } void modify(int rt,int l,int r,int al,int ar){ if(l>r||l>ar||r
          
           ar||!rt)return ;int mid=l+r>>1; if(al<=l&&r<=ar){ tr[rt]=0;lzy[rt]=1;return ;}pushdown(rt); if(al<=mid)modify(ch[rt][0],l,mid,al,ar); if(ar>mid)modify(ch[rt][1],mid+1,r,al,ar); pushup(rt); } bool query(int rt){ return tr[rt];} int sakura(int rt,int l,int r){ if(l==r)return tim[rt];int mid=l+r>>1;pushdown(rt); if(tr[ch[rt][0]])return sakura(ch[rt][0],l,mid); return sakura(ch[rt][1],mid+1,r); }}TL,TR;signed main(){ read(n);read(m);TL.insert(TL.root,0,m,0,0);TR.insert(TR.root,0,m,0,0); for(int i=1;i<=n;i++){ read(s[i].k);read(s[i].al);read(s[i].bl);read(s[i].ar);read(s[i].br); bool Llive=TL.query(TL.root),Rlive=TR.query(TR.root); if(Llive)ansl[i]=TL.sakura(TL.root,0,m);else ansl[i]=-1; if(Rlive)ansr[i]=TR.sakura(TR.root,0,m);else ansr[i]=-1; if(s[i].ar<=s[i].k&&s[i].k<=s[i].br){ TL.modify(TL.root,0,m,0,s[i].al-1),TL.modify(TL.root,0,m,s[i].bl+1,m); if(i>1&&s[i].al<=s[i-1].k&&s[i-1].k<=s[i].bl&&Rlive) TL.insert(TL.root,0,m,s[i-1].k,i-1),choL[i]=1; } else TL.modify(TL.root,0,m,0,m); if(s[i].al<=s[i].k&&s[i].k<=s[i].bl){ TR.modify(TR.root,0,m,0,s[i].ar-1),TR.modify(TR.root,0,m,s[i].br+1,m); if(i>1&&s[i].ar<=s[i-1].k&&s[i-1].k<=s[i].br&&Llive) TR.insert(TR.root,0,m,s[i-1].k,i-1),choR[i]=1; } else TR.modify(TR.root,0,m,0,m); } if(TL.query(TL.root)||TR.query(TR.root)){ puts("Yes");int x=0,y=0;int tot=n,lim;bool f; if(TL.query(TL.root))lim=TL.sakura(TL.root,0,m),x=s[lim].k,y=s[n].k,f=0; else lim=TR.sakura(TR.root,0,m),x=s[n].k,y=s[lim].k,f=1; while(tot){ int tmpl=(y!=s[tot-1].k||!choR[tot])?s[tot-1].k:ansl[tot]; if(f){ ans[tot]=0;if(tot>lim+1)x=s[tot-1].k;else f^=1,x=s[lim=ansl[tot]].k;} else{ ans[tot]=1;if(tot>lim+1)y=s[tot-1].k;else f^=1,y=s[lim=ansr[tot]].k;} tot--; } for(int i=1;i<=n;i++)printf("%d ",ans[i]);puts(""); } else puts("No"); return 0;}
          
         
        
       
      
     
    
   

谢谢！！！

转载地址：http://xeyoi.baihongyu.com/