题目
给定长为n(n<=2e5)的两个序列a和b，
a为n的一个排列，
b也为n的一个排列，但有一些位置被-1替换了，保证没被替换的位置在[1,n]之间且两两不同
你有一个距离最大限制s，你可以执行n次操作，
第i次操作时(1<=i<=n)，
你可以选择满足i<=x<=y<=min(i+s,n)的两个值(x,y)，
交换这两个值在a序列里的位置，
你可以选择x=y，也就是意味着可以不操作
现在你可以将b中的每个-1的位置替换上对应的[1,n]内的值，使得b是一个排列，
如果替换成排列之后的序列b，可以由a序列在n次交换后得到，则称b序列是合法的，
问所有合法的b序列的方案数，答案对998244353取模
实际为t(t<=1e3)组样例，保证sumn不超过2e5
思路来源
洛谷题解
CF1698E PermutationForces II Solution - 思考人生中 的博客 - 洛谷博客
题解
首先考虑无解的情况，由于第i次只能交换[i,i+s]内的两个值，
不妨第i次交换，就是使i这个值在b序列中归位
若b[i]需要被归位，且当前占住i位置的值a[i]>b[i]+s，
说明增序考虑到i时，a[i]是被换不走的，此时无解
所以，合法的条件是，对于b[i]不为-1的位置，要求a[i]的值不能超过b[i]+s
即
有解之后，考虑怎么操作，首先考虑给转换成位置序列
即，若a[i]=j，则令posa[j]=i；若b[i]=j，则令posb[j]=i
举一个例子，即第五个样例
原序列：
n=7，s=4
a: 1 3 6 2 7 4 5
b: 2 5 1 -1 -1 4 -1
转化序列：
posa: 1 4 2 6 7 3 5
posb: -1 1 -1 6 2 -1 -1
对于posb的每一个为-1的位置i，
只有posa序列[1,min(i+s,n)]中，那些值没有在posb中出现过的位置是可取的，
记这个值的个数为cnt，则对于每个posb的-1位置，
有cnt个值是可取的，每取走一个，即令ans*=cnt,cnt-=1
比如，在为posb[1]=-1这个未确定的位置赋值的时候，posb[1]的值，
可以在[1 4 2 6 7]，也就是[1,1+s]这个区间里取，但是只能用[4 7]这两个值，
因为1 2 6在posb中出现过，只能换到一一对应的位置去
也就是说，4个-1位置可以用到的值是4 7 3 5，
其中，
posb[1]只能用到[1,5]里的可用位置，即[1 4 2 6 7]里的[4 7]，ans*=2
posb[3]可以用到[1,7]里的可用位置，即[1 4 2 6 7 3 5]里的[4 7 3 5]，
而其中[4 7]有一个被posb[1]用过，所以ans*=3
类似地，posb[6]和posb[7]都可以用到[1,7]里的可用位置，分别对应ans*=2和ans*=1
所以，ans=2*3*2*1=12
每个前面的不确定位置只能用一个值，前面没有用到的值可以被换下来换到后面，
所以posb[i]=-1的位置，可以用到[1,min(i+s,n)]的所有可用位置
双指针模拟这个过程即可，复杂度
代码
#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,mod=998244353;
int t,n,s,a[N],b[N],posa[N],posb[N];
bool vis[N];
/*
原序列
n=7 s=4
a: 1 3 6 2 7 4 5
b: 2 5 1 -1 -1 4 -1
转化序列
posa: 1 4 2 6 7 3 5
posb: -1 1 -1 6 2 -1 -1
其中4 7 3 5是可用的-1位置，第一个位置只能用到[1 4 2 6 7]里的可用位置
对于posb的每一个为-1的位置i，只有posa中[1,min(i+s,n)]中，那些值没有在posb中出现过的位置是可取的，记这个值的个数为cnt，则对于每个posb的-1位置，ans*=cnt,cnt-=1
*/
int sol(){
sci(n),sci(s);
rep(i,1,n){
sci(a[i]);
posa[a[i]]=i;
posb[i]=-1;
vis[i]=0;
}
rep(i,1,n){
sci(b[i]);
if(b[i]==-1)continue;
posb[b[i]]=i;
vis[i]=1;
}
rep(i,1,n){
if(b[i]==-1)continue;
//printf("i:%d a:%d b:%d\n",i,a[i],b[i]);
if(a[i]-b[i]>s)return 0; //若b[i]需要被归位，且当前占住i位置的值a[i]>b[i]+s，说明增序考虑到i时，a[i]是挪不走的，无解
}
int cur=0,ans=1,cnt=0;
rep(i,1,n){
while(cur+1<=min(n,i+s)){
cur++;
cnt+=(!vis[posa[cur]]);
}
//printf("i:%d cur:%d cnt:%d\n",i,cur,cnt);
if(posb[i]==-1){
ans=1ll*ans*cnt%mod;
cnt--;
}
}
return ans;
}
int main(){
sci(t);
while(t--){
pte(sol());
}
return 0;
}
