AT4353 [ARC101D] Robots and Exits

题面传送门
发现每个机器人只会最多有两个出口，这是好的。
又发现这个奇怪的方案数计数使得只有一个出口的机器人对于答案没有贡献，所以可以扔了。
然后这个问题被转化成了这样一个模型：有两维坐标系，你每次可以向两维分别走一步，定义\(m\)个二元组\((u_i,v_i)\)，对于任意两条路径，如果存在一个二元组使得\(x=u_i\)和\(y=v_i\)被走到的顺序不同那么不一样。
不妨对\(x\)这一维扫描线，维护\(dp_{i}\)表示当前\(x\)，\(y\)那一维走到\(i\)的，与所有\(1\)到\(i-1\)本质不同的方案数。
发现转移只对于所有二元组中\(u_i=x\)的位置，将\(v_i\)加上当前所有\(1\)到\(v_i-1\)的dp值的和。表示先走到了\(x\)。
容易用树状数组优化这个过程，时间复杂度\(O(n\log n)\)
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define ll long long
#define db double
#define lb long db
#define N (100000+5)
#define M (1000000+5)
#define K (20+5)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;vector S[N];
int n,m,k,x,y,z,La,R[N],A[N],B[N],Na[N],Nb[N],Ha,Hb;
namespace Tree{ll F[N];I void Ins(int x,ll b){while(x<=Hb+1) F[x]=(F[x]+b)%mod,x+=x&-x;}I ll Qry(int x){ll Ans=0;while(x) Ans+=F[x],x-=x&-x;return Ans%mod;}}
int main(){
	freopen("1.in","r",stdin);
	int i;scanf("%d%d",&n,&m);for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i<=m;i++) scanf("%d",&B[i]);sort(A+1,A+n+1);sort(B+1,B+m+1); 
	for(i=1;i<=n;i++){R[i]=R[i-1];while(R[i]B[R[i]+1]) R[i]++; R[i]&&R[i]^m&&(Na[++Ha]=A[i]-B[R[i]],Nb[++Hb]=B[R[i]+1]-A[i]);}
	sort(Na+1,Na+Ha+1);sort(Nb+1,Nb+Hb+1);Ha=unique(Na+1,Na+Ha+1)-Na-1;Hb=unique(Nb+1,Nb+Hb+1)-Nb-1;
	for(i=1;i<=n;i++) R[i]&&R[i]^m&&(S[lower_bound(Na+1,Na+Ha+1,A[i]-B[R[i]])-Na].PB(lower_bound(Nb+1,Nb+Hb+1,B[R[i]+1]-A[i])-Nb),0);
	Tree::Ins(1,1);for(i=1;i<=Ha;i++) {La=0;sort(S[i].begin(),S[i].end());for(int j:S[i]) Tree::Ins(j+1,Tree::Qry(j)-Tree::Qry(La)),La=j;}printf("%lld\n",(Tree::Qry(Hb+1)+mod)%mod);
}