先考虑另一个问题：在上下界限制下判断是否存在 (x,y) 满足 (x or y=v_1,x and y=v_2)，设 (f(p,a,b,c,d)) 表示考虑到第 (p) 位和上下界限制是否合法。回到原问题，考虑 (DP) 套 (DP)，设 (g(p,S)) 表示考虑到第 (p) 位，(DP) 状态为 (S) 的 (v_2) 个数，其中 (S) 是将上一个 (DP) 后四维中 (2^4) 种情况压起来，枚举 (v_2) 当前位的值即可转移。复杂度为 (O(2^{16}log T))。
也可以直接数位 (DP)，注意当前位与为 (0) 时有三种情况：(0 0,0 1,1 0)，都加起来会算重，发现方案数小的情况一定是方案数大的情况的子集，于是取 (max) 转移即可。复杂度为 (O(2^4log T))。
(DP) 套 (DP)：
#include<bits/stdc++.h>
#define maxn 62
#define maxm 65546
#define all 65535
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
ll ans;
int w[maxn],Lx[maxn],Rx[maxn],Ly[maxn],Ry[maxn];
ll f[maxn][maxm];
int sta(int a,int b,int c,int d)
{
return (a<<3)|(b<<2)|(c<<1)|d;
}
void work(int *a)
{
ll v;
int cnt=-1;
read(v);
while(v) a[++cnt]=v%2,v/=2;
}
int main()
{
work(w),work(Lx),work(Rx),work(Ly),work(Ry),f[60][1<<sta(1,1,1,1)]=1;
for(int p=59;p>=0;--p)
{
for(int s=0;s<=all;++s)
{
if(!f[p+1][s]) continue;
for(int v=0;v<=1;++v)
{
int t=0;
for(int a=0;a<=1;++a)
{
for(int b=0;b<=1;++b)
{
for(int c=0;c<=1;++c)
{
for(int d=0;d<=1;++d)
{
if(!((s>>sta(a,b,c,d))&1)) continue;
for(int x=0;x<=1;++x)
{
for(int y=0;y<=1;++y)
{
if((x|y)!=w[p]||(x&y)!=v) continue;
if(a&&x<Lx[p]) continue;
if(b&&x>Rx[p]) continue;
if(c&&y<Ly[p]) continue;
if(d&&y>Ry[p]) continue;
t|=1<<sta(a&(x==Lx[p]),b&(x==Rx[p]),c&(y==Ly[p]),d&(y==Ry[p]));
}
}
}
}
}
}
f[p][t]+=f[p+1][s];
}
}
}
for(int i=1;i<=all;++i) ans+=f[0][i];
printf("%lld",ans);
return 0;
}
数位 (DP)：
#include<bits/stdc++.h>
#define maxn 62
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n;
int t[maxn],Lx[maxn],Rx[maxn],Ly[maxn],Ry[maxn];
ll f[maxn][2][2][2][2];
ll dp(int p,bool lx,bool rx,bool ly,bool ry)
{
if(p==-1) return 1;
if(f[p][lx][rx][ly][ry]!=-1) return f[p][lx][rx][ly][ry];
ll v=0,mx=0;
for(int i=0;i<4;++i)
{
int x=i&1,y=i>>1;
if((x|y)!=t[p]) continue;
if(lx&&x<Lx[p]) continue;
if(rx&&x>Rx[p]) continue;
if(ly&&y<Ly[p]) continue;
if(ry&&y>Ry[p]) continue;
bool t1=lx&(x==Lx[p]),t2=rx&(x==Rx[p]),t3=ly&(y==Ly[p]),t4=ry&(y==Ry[p]);
if(x&y) v+=dp(p-1,t1,t2,t3,t4);
else mx=max(mx,dp(p-1,t1,t2,t3,t4));
}
return f[p][lx][rx][ly][ry]=v+mx;
}
void work(int *a)
{
ll v;
int cnt=-1;
read(v);
while(v) a[++cnt]=v%2,v/=2;
n=max(n,cnt);
}
int main()
{
work(t),work(Lx),work(Rx),work(Ly),work(Ry);
memset(f,-1,sizeof(f)),printf("%lld",dp(n,1,1,1,1));
return 0;
}