前言
boom
题目
讲解
暴力地，我们如果存能够开多少炮和CD，时空都直接上天。
我们把开炮数量和CD综合存储，可以用类似于能量条的东西来解释：走一步获得一点能量，如果能量达到 t 就可以开炮，每次换路时能量要对 t 取最小值。
但是 n 很大，不能直接做，考虑挖掘性质，我们发现如果要换路，那么肯定是越早越好，具体体现为会在某个障碍物之后的一个格子换路，这样的话就可以离散化处理了。
注意求开炮时间的时候由于是倒推，所以需要一些特别处理，详见代码attention处。
精细实现可以做到 \(O(m_1+m_2)\)，但是直接用sort排序，lower_bound预处理也能过。
代码
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 4000005;
int n,m1,m2,t,tot;
int b[2][MAXN],pos[MAXN],dp[2][MAXN],pa[MAXN],pb[MAXN],p1,p2;
bool tb[2][MAXN],dir[2][MAXN];
vector<int> ans[3];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
void update(int x,int y,int val,bool sg){if(dp[x][y] < val) dp[x][y] = val,dir[x][y] = sg;}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); m1 = Read(); m2 = Read(); t = Read();
for(int i = 1;i <= m1;++ i) pa[++p1] = b[0][i] = Read(),pa[p1+1] = pa[p1]+1,++p1;
for(int i = 1;i <= m2;++ i) pb[++p2] = b[1][i] = Read(),pb[p2+1] = pb[p2]+1,++p2;
pos[++tot] = 0;
int l1 = 1,l2 = 1;
while(l1 <= p1 && l2 <= p2)
if(pa[l1] == pos[tot]) ++l1;
else if(pb[l2] == pos[tot]) ++l2;
else if(pa[l1] < pb[l2]) pos[++tot] = pa[l1++];
else pos[++tot] = pb[l2++];
while(l1 <= p1) if(pa[l1] == pos[tot]) ++l1;else pos[++tot] = pa[l1++];
while(l2 <= p2) if(pb[l2] == pos[tot]) ++l2;else pos[++tot] = pb[l2++];
if(pos[tot]^(n+1)) pos[++tot] = n+1;
l1 = l2 = 1;
for(int i = 1;i <= m1;++ i) {while(pos[l1] < b[0][i]) ++l1;tb[0][l1] = 1;}
for(int i = 1;i <= m2;++ i) {while(pos[l2] < b[1][i]) ++l2;tb[1][l2] = 1;}
for(int i = 1;i <= tot;++ i) dp[0][i] = dp[1][i] = -1;
dp[0][1] = dp[1][1] = 0; dir[1][1] = 1;
for(int i = 1;i <= tot;++ i)
{
for(int j = 0;j < 2;++ j)//slide
if(dp[j][i] >= 0 && !tb[j^1][i])
update(j^1,i,Min(dp[j][i],t),1);
for(int j = 0;j < 2;++ j)//fire
if(dp[j][i] >= 0 && dp[j][i] + pos[i+1]-pos[i]-1 >= t*tb[j][i+1])
update(j,i+1,dp[j][i] + pos[i+1]-pos[i] - t*tb[j][i+1],0);
}
bool now = 0;
if(dp[0][tot] >= 0) now = 0;
else if(dp[1][tot] >= 0) now = 1;
else {printf("No\n");return 0;}
int lst = n+t;//attention
for(int i = tot;i >= 1;-- i)
{
if(dir[now][i]) ans[0].emplace_back(pos[i]),now ^= 1;
if(tb[now][i])
{
lst = Min(lst-t,pos[i]-1);
ans[1].emplace_back(lst);
ans[2].emplace_back(now);
}
}
printf("Yes\n");
Put(ans[0].size(),'\n');
for(int i = ans[0].size()-1;i >= 0;-- i) Put(ans[0][i],' '); putchar('\n');
Put(ans[1].size(),'\n');
for(int i = ans[1].size()-1;i >= 0;-- i) Put(ans[1][i],' '),Put(ans[2][i]+1,'\n');
return 0;
}