2019.1.9交流题，现在看还是不会，，，

如果只有一边，那么Hall定理即可。

两边？分别满足Hall定理，就是合法的！

证明（构造方案）：

左集合先任意形成一个合法匹配，单点增量加入右集合和与右集合有关的边进行调整

加入bj，枚举连接bj的边，连向ai

直接大力匈牙利匹配即可。由于Hall定理成立，所过之处一定能返回true

DP之后双指针即可。

注意，左、右是空集合也合法

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}template
           
            il int ad(const int a,const int b,const Args &...args) { return ad(ad(a,b),args...);}template
            
             il int mul(const int a,const int b,const Args &...args) { return mul(mul(a,b),args...);}}// using namespace Modulo;namespace Miracle{const int N=21;int sz[1<
             
              >j)&1) { to|=go[j]; s[i]+=val[j]; } } f[i]=(sz[to]>=sz[i]); if(f[i]){ for(reg j=0;j
              
               >j)&1) f[i]&=f[i^(1<
               
                >1]+(i&1); } le.dp();ri.dp(); // cout<
                
                 <<" "<
                 
                  <
                  
                   =lim) --ptr; // ptr=lower_bound(ri.ok+1,ri.ok+ri.cnt+1,lim-le.ok[i])-ri.ok-1; ans+=ri.cnt-ptr; } cout<