2022 NOIP 题解

这道题之前做过一次,我们来转换一下这道题的题意，题中给到了边、点我们可以想到强连通分量，进而想到tarjan算法。通过所给样例及题意，我们可以将原题目转化为以下内容：

给定一张图，选择一些点和边，使得割断任意没有选的边，被选中的点仍联通，最终答案对$10^9+7$取模。

想做这道题，我们得先知道什么是割点、割边（桥）、缩边、双连通分量

看到图和连通，想到tarjan。割断一条没有选的边，选中的点仍连通，割非割边，整张图仍然连通。

把割边删掉，则整张图分成若干连通子图。可以把一张子图看成一个点，这样形成的新图上没有环，因为在环上的边都不是割边，那它就是一棵树。使用vector邻接表建图，dfs一遍，使用$f$数组记录答案，最终将答案转移到$ans$上。

上一次做这道题代码愣是写了120行，昨天换了个思路，尝试着把dfs压缩了一下，代码就短多了。

code

//本质使得割掉一些边之后,剩下的点仍然联通
//看到连通块就想到tarjan算法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 500005;
const int mod = 1e9 + 7;
ll n, m;//城市个数,双向道路数量
ll ans;//方案数
//tarjan算法的常用数组
ll st[N], dfn[N], low[N],bl[N];
ll f[N];
vector<int>e[N], g[N];//使用vector为了方便
void tarjan(int x, int fa) {st[++st[0]] = x;dfn[x] = low[x] = ++dfn[0];for (int y : e[x]){//从数组e中依次取出元素赋值给yif (y != fa) {if (!dfn[y]){tarjan(y, x);}low[x] = min(low[x], low[y]);}}if (dfn[x] == low[x]) {m++;while (st[st[0]] != x)bl[st[st[0]--]] = m;bl[st[st[0]--]] = m;}
}
void dfs(int k, int fa) {ans = (ans + f[k]) % mod;for (int i : g[k]){if (i != fa) {dfs(i, k);f[i] = f[i] * (mod + 1) / 2 % mod;ans = (ans + f[k] * f[i]) % mod;f[k] = (f[k] + f[i] + f[k] * f[i]) % mod;}}
}
int main() {cin >> n >> m;//输入边+建图for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;//临接表建图e[x].push_back(y);e[y].push_back(x);}m = 0;tarjan(1, 0);for (int i = 1; i <= m; i++){f[i]++;}for (int i = 1; i <= n; i++){f[bl[i]] = f[bl[i]] * 2 % mod;}for (int i = 1; i <= m; i++){f[i]--;}for (int i = 1; i <= n; i++){for (int j : e[i]){if (bl[i] != bl[j]){g[bl[i]].push_back(bl[j]);}}}dfs(1, 0);for (int i = 1; i <= n; i++){for (int j : e[i]){if (i < j){ans = ans * 2 % mod;}}}cout << ans;return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int M = 4e6;
const int mod = 1e9 + 7;
int add(int x, int y) {return ((x += y) >= mod) ? x - mod : x;
}
void addn(int &x, int y) {if ((x += y) >= mod) x -= mod;
}
int mins(int x, int y) {return ((x -= y) < 0) ? x + mod : x;
}
struct G {struct edge {int to, nxt, w;} e[M << 1];int head[M], cnt1 = 1;void link(int u, int v) {e[++cnt1] = {v, head[u], 1};head[u] = cnt1;}
} g1, g2;
int fa[M];
int dfn[M], low[M], cnt;
bool cut[M];
void tarjan(int u, int f) {low[u] = dfn[u] = ++cnt;for (int i = g1.head[u]; i; i = g1.e[i].nxt) {int v = g1.e[i].to;if (v == f) continue;if (!dfn[v]) {tarjan(v, u);low[u] = min(low[u], low[v]);if (low[v] > dfn[u]) g1.e[i].w = g1.e[i ^ 1].w = 0; // 0 标记为割边，i^1 用了成对变换的技巧，把反边一起标记} else low[u] = min(low[u], dfn[v]);}
}
int siz1[M], siz2[M];
bool vis[M];
int bl[M];
int n, m;//n城市个数,m双向道路数量
int cnt2;
// 用于划分连通块，siz1 对应行文中的 cntp，点数；siz2 对应行文中的 cnte，边数
void dfs2(int u, int f, int t) {bl[u] = t;vis[u] = 1;++siz1[t];for (int i = g1.head[u]; i; i = g1.e[i].nxt) {if (g1.e[i].w) ++siz2[t];int v = g1.e[i].to;if (g1.e[i].w == 0 || v == f) continue;if (!vis[v]) dfs2(v, u, t);}
}
int sm[M];
// 用于计算文中的 sum 数组，子树中边数和，包括被缩掉者
void dfs4(int u, int fa) {sm[u] = siz2[u];for (int i = g2.head[u]; i; i = g2.e[i].nxt) {int v = g2.e[i].to;if (v == fa) continue;dfs4(v, u);sm[u] += sm[v] + 1;}
}
int dp[M][2], pw[M], ans;
// 统计答案的 dfs，dp 意义如上文所叙
// dp_{u,0} 强制 u 及其子树不选任意一个点（空）
// dp_{u,1} 强制 u 及其子树选至少一个点，且所有被选的点与 u 连通（不空）。
void dfs3(int u, int fa) {dp[u][0] = pw[siz2[u]];dp[u][1] = 1ll * pw[siz2[u]] * (pw[siz1[u]] - 1) % mod;int tot = 0;for (int i = g2.head[u]; i; i = g2.e[i].nxt) {int v = g2.e[i].to;if (v == fa) continue;dfs3(v, u);dp[u][1] = add(1ll * dp[u][1] * add(1ll * dp[v][0] * 2 % mod, dp[v][1]) % mod, 1ll * dp[u][0] * dp[v][1] % mod);dp[u][0] = 1ll * dp[u][0] * 2 % mod * dp[v][0] % mod;addn(tot, dp[v][1]);}if (u != n + 1) addn(ans, 1ll * dp[u][1] * pw[sm[n + 1] - sm[u] - 1] % mod);else addn(ans, 1ll * dp[u][1] % mod);
}
int find(int u) {return u == fa[u] ? u : fa[u] = find(fa[u]);
}
void merge(int u, int v) {if ((u = find(u)) != (v = find(v))) fa[u] = v;
}
int main() {scanf("%d %d", &n, &m);pw[0] = 1;for (int i = 1; i <= 2 * n + m; i++) pw[i] = 1ll * pw[i - 1] * 2 % mod;for (int i = 1; i <= m; i++) {int u, v;scanf("%d %d", &u, &v);g1.link(u, v);g1.link(v, u);}tarjan(1, 0);cnt2 = n;for (int i = 1; i <= n; i++) if (!vis[i]) dfs2(i, 0, ++cnt2);for (int i = n + 1; i <= 2 * n; i++) {siz2[i] /= 2;}// 缩边for (int i = 1; i <= 2 * n; i++) fa[i] = i;for (int u = 1; u <= n; u++) {for (int i = g1.head[u]; i; i = g1.e[i].nxt) {int v = g1.e[i].to;if (find(bl[u]) != find(bl[v])) g2.link(bl[u], bl[v]), g2.link(bl[v], bl[u]), merge(bl[u], bl[v]);}}// n+1 是缩完边后树的根dfs4(n + 1, 0);dfs3(n + 1, 0);printf("%d\n", ans);
}

这道题其实是道计数4+模拟的题，非常简单的想法，用两个函数把我们所需要求的写成两个函数，按照题目中的要求实现就行，但是好像会T。
$80pts$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e3 + 10;
const int md = 998244353;
int t, id;
int n, m, c, f;
bool mapp[maxn][maxn];
ll ac, af;
string s;
//快速幂模板
ll qmul(ll a, ll b) {ll res = 0;while (b) {if (b & 1)res += a;a *= 2;b >>= 1;}return res;
}
void cc() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (!mapp[i][j]) {int x = 0, xx = 0, y = 0;while (!mapp[i][j + x] && j + x <= m)x++;if (!(x - 1))continue;while (!mapp[i + y][j] && i + y <= n)y++;if (!(y - 2))continue;for (int k = 2; k <= y - 1; k++) {xx = 0;while (!mapp[i + k][j + xx] && j + xx <= m)xx++;if (!xx)continue;ac += qmul(x - 1, xx - 1);ac = ac % md;}}}}
}
void ff() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (!mapp[i][j]) {int x = 0, xx = 0, y = 0;while (!mapp[i][j + x] && j + x <= m)x++;if (!(x - 1))continue;while (!mapp[i + y][j] && i + y <= n)y++;if (!(y - 3))continue;for (int k = 2; k <= y - 2; k++) {xx = 0;while (!mapp[i + k][j + xx] && j + xx <= m)xx++;if (!xx)continue;af += qmul(qmul(x - 1, xx - 1), (y - 1 - k));af = af % md;}}}}
}
int main() {cin >> t >> id;while (t--) {memset(mapp, 0, sizeof(mapp));cin >> n >> m >> c >> f;ac = 0, af = 0;for (int i = 1; i <= n; i++) {cin >> s;for (int j = 1; j <= m; j++)mapp[i][j] = s[j - 1] == '0' ? 0 : 1;}if (c)cc();if (f)ff();cout << ac << ' ' << af << '\n';}return 0;
}

先考虑$C$形，

我们可以确定$C$形的左上角 $O(nm)$

然后，我们的目标是：

1. 求出$C$第一行长度的可能结果数
2. 求出$C$ 第一列的可取长度的范围1
3. 求出$C$每一列长度对应的行的可能结果数
4. 目标$1$和目标$3$相乘累加到答案中

以上的步骤全部需要$O(1)$ 完成，所以我们考虑预处理

对于 目标$1$，我们可以预处理出 位置 ( i , j ) (i,j)(i,j) 离右手边最近的障碍的距离。

对于 目标$3$，一个个算肯定是 武则天丧夫 没理智的，但是我们求的是一个区间结果，这个时候就该考虑前缀和

我们用新的数组存储(我们预处理的右手边最近障碍距离)的前缀和，在执行目标$3$时用前缀和作差求出结果。

我们可以再预处理 位置 $(i,j)$ 离正下方最近障碍的距离。那么我们询问的区间就是 $(x+2,j)\sim (x+dis(x),j)$

自此 $c$ 形就解决了！

再考虑$F$形:

如果我们已经确定了 $F$ 形的第二 横，那么可以得到累加多少结果呢？

很显然是 小尾巴 的长度。那么我们对于每一个可能的横都可以预处理出带上小尾巴的结果数，

然后还是熟悉的区间结果查询，我们依旧对上述结果做前缀和。

$code$

#include<bits/stdc++.h>
using namespace std;
#define int long long		
int rd() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;
}void wt(int x) {static int sta[35];int f = 1;if(x < 0) f = -1,x *= f;int top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);if(f == -1) putchar('-');while (top) putchar(sta[--top] + 48);
}
int T,id;
const int N = 1005,mod = 998244353;
int n,m,c,f;
char d[N];
int s[N][N],h[N][N];
int ss[N][N],_s[N][N];void init() {memset(s,0,sizeof(s));memset(ss,0,sizeof(ss));memset(h,0,sizeof(h));memset(_s,0,sizeof(_s));
}void solve() {init();n = rd(),m = rd(),c = rd(),f = rd();for(int i = 1;i<=n;i++) {scanf("%s",d + 1);for(int j = 1;j<=m;j++)s[i][j] = d[j] - '0';}for(int j = 1;j<=m;j++)for(int i = n,k = n + 1;i>=1;i--)if(s[i][j]) k = i,h[i][j] = k - i - 1;else h[i][j] = k - i - 1;for(int i = 1;i<=n;i++)for(int j = m,k = m + 1;j >= 1;j--)if(s[i][j]) k = j,s[i][j] = k - j - 1;else s[i][j] = k - j - 1;for(int j = 1;j<=m;j++) {for(int i = n;i>=1;i--){ss[i][j] = ss[i + 1][j] + s[i][j];_s[i][j] = s[i][j] * h[i][j];_s[i][j] = _s[i + 1][j] + _s[i][j];}}int C = 0,F = 0;for(int j = 1;j<=m;j++) {int k = 1,re = 0;while(k + 2 <= n) {while((s[k][j] == -1 || s[k + 1][j] == -1 || s[k + 2][j] == -1) && k <= n) k++;if(k >= n - 1) break;re = s[k][j];(C += re * (ss[k + 2][j] - ss[k + h[k][j] + 1][j])) %= mod;if(k + 3 <= n && ~s[k + 3][j]) 	(F += re * (_s[k + 2][j] - _s[k + h[k][j] + 1][j])) %= mod;k++;}}wt(c * C),putchar(' '),wt(f * F);putchar('\n');
}		
signed main() {T = rd(),rd();while(T--) solve();return 0;
}

想了想，对于题中的所有询问，我们先从$r$开始，从小到大一个挨着一个的开始遍历。如果当前考虑到$r$，记$x_i={\max }_{j=i}^r{a}_j,y_i={\max }_{j=i}^r{b}_j,f_i={\sum }_{j=i}^r{x}_j{y}_j,$那么对于我们所询问的区间$(l,r)，$我们所要求的答案就是${\sum }_{i=l}^r{f}_i。$
$20pts$

//暴力做法
//20pts
#include<bits/stdc++.h>
using namespace std;
#define LL  long long//数据较大，要开long long
const int N = 3e5;
struct Node {int l, id;
};
LL read(){LL x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
vector<Node> d[N];//将询问存在vector里
LL a[N], b[N];
LL f[N];
LL x[N], y[N];
LL ans[N];//记录答案
int main() {int t;int n, q;t=read();n=read();//小n队for (int i = 1; i <= n; i++) {a[i]=read();}//小o队for (int i = 1; i <= n; i++) {b[i]=read();}//比赛场数q=read();for (int i = 1; i <= q; i++) {int l, r;//比赛参数l=read(),r=read();d[r].push_back({l, i});}//将所有询问按照右端点排序
//	对所有访问按照r从小到大来for (int r = 1; r <= n; r++) {for (int i = 1; i <= r; i++) {
//			考虑到r
//			两个数组的最大值x[i] = max(x[i], a[r]);y[i] = max(y[i], b[r]);//f[i]对于每个r,x[i]*y[i]的累加和,相当于固定左端点是i,右端点是[i,r]任意数的贡献和f[i] += x[i] * y[i];}
//		答案为\sum _{i=l}^{r}f_i
//		转换为将p固定住，将q移动for (auto [l, id] : d[r]) {for (int i = l; i <= r; i++)ans[id] += f[i];}}for (int i = 1; i <= q; i++) {printf("%lld\n", ans[i]);}
//	时间复杂度O(n^2+nq)return 0;
}

正解
考虑优化，用线段树来维护$f_i$这样$O(logn)$的时间能求出${\sum }_{i=l}^r{f}_i$。
用单调栈或者 DP 预处理出$a,b$ 数组每个元素作为最大值往左能控制到的最远位置，这样每个​$a_r$只会更新一段后缀的$x_i,b_r$也同理，都利用线段树来做区间覆盖。也就说，每到一个新的$r$在回答询问前进行下面$3$个步骤:

1. 区间更新一段后缀的$x_i$为$a_r$。
2. 区间更新一段后缀的$y_i$为$b_r$。
3. 在$[l,r]$区间每个$f_i$上加上$x_i\ast y_i$。

线段树记录四个信息$s$表示$f_i$的区间和，$xy$表示区间内$\sum x_i{y}_i,x$表示区间内$\sum x_i,y$表示区间内$\sum{y_i}。

定义6个延迟标记，$c_x,c_y$是覆盖标记，后面四个标记$ad{d}_{xy},ad{d}_x,ad{d}_y,ad{d}_c$分别为$\sum x_i{y}_i,\sum x_i,\sum y_i,\sum 1$(相当于于区间长度)的增量，也就是各自增加的倍数。

规定延迟标记的优先级为，加标记应用在覆盖标记之前，这样在下传的时候，下传的加标记会作用在原先的信息上。也就是说，如果原先存在覆盖标记，下传的加标记会退化 。

对于区间信息的更新，首先$s$应该加上$ad{d}_{xy}\ast \sum x_i{y}_i+ad{d}_x\ast \sum x_i+ad{d}_y\ast \sum y_i+ad{d}_c\ast \sum 1$,然后根据是否有覆盖标记来更新$\sum x_i{y}_i,\sum x_i,\sum y_i,$时间复杂度为$O((n+q)logn)。
$code$

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 250005;struct Qode {int l, id;
};
vector<Qode> d[N];
ULL a[N], b[N];
ULL ans[N];
int la[N], lb[N];
struct Node {ULL s, xy, x, y;
} tr[N << 2];
struct Tag {// 先应用加标记，再应用覆盖标记ULL cx, cy;  //覆盖标记,0 表示无覆盖ULL add_xy, add_x, add_y, add_c;
} lazy[N << 2];void push_up(int u) {tr[u] = {tr[u << 1].s + tr[u << 1 | 1].s,tr[u << 1].xy + tr[u << 1 | 1].xy,tr[u << 1].x + tr[u << 1 | 1].x,tr[u << 1].y + tr[u << 1 | 1].y};
}void gx(int u, int len, Tag t) {// 标记更新标记auto &[cx, cy, add_xy, add_x, add_y, add_c] = lazy[u];if (cx && cy) {add_c += t.add_xy * cx * cy + t.add_x * cx + t.add_y * cy + t.add_c;} else if (cx) {add_c += t.add_x * cx + t.add_c;add_y += t.add_xy * cx + t.add_y;} else if (cy) {add_c += t.add_y * cy + t.add_c;add_x += t.add_xy * cy + t.add_x;} else {add_xy += t.add_xy;add_x += t.add_x;add_y += t.add_y;add_c += t.add_c;}if (t.cx) cx = t.cx;if (t.cy) cy = t.cy;// 标记更新信息auto &[s, xy, x, y] = tr[u];s += t.add_xy * xy + t.add_x * x + t.add_y * y + t.add_c * len;if (t.cx && t.cy) {xy = t.cx * t.cy * len;x = t.cx * len;y = t.cy * len;} else if (t.cx) {xy = t.cx * y;x = t.cx * len;} else if (t.cy) {xy = t.cy * x;y = t.cy * len;}
}
void push_down(int u, int len1, int len2) {if (lazy[u].cx || lazy[u].cy || lazy[u].add_xy || lazy[u].add_x || lazy[u].add_y || lazy[u].add_c) {gx(u << 1, len1, lazy[u]);gx(u << 1 | 1, len2, lazy[u]);lazy[u] = {0, 0, 0, 0, 0, 0};}
}void update(int u, int l, int r, int x, int y, Tag t) {if (x <= l && r <= y) {gx(u, r - l + 1, t);return;}int mid = l + r >> 1;push_down(u, mid - l + 1, r - mid);if (x <= mid) update(u << 1, l, mid, x, y, t);if (y > mid) update(u << 1 | 1, mid + 1, r, x, y, t);push_up(u);
}ULL query(int u, int l, int r, int x, int y) {if (x <= l && r <= y) return tr[u].s;int mid = l + r >> 1;push_down(u, mid - l + 1, r - mid);ULL res = 0;if (x <= mid) res += query(u << 1, l, mid, x, y);if (y > mid) res += query(u << 1 | 1, mid + 1, r, x, y);return res;
}int main() {int n, q;scanf("%*d%d", &n);a[0] = b[0] = 1e9;for (int i = 1; i <= n; i++) {scanf("%llu", &a[i]);la[i] = i;while (a[i] > a[la[i] - 1]) la[i] = la[la[i] - 1];}for (int i = 1; i <= n; i++) {scanf("%llu", &b[i]);lb[i] = i;while (b[i] > b[lb[i] - 1]) lb[i] = lb[lb[i] - 1];}scanf("%d", &q);for (int i = 1; i <= q; i++) {int l, r;scanf("%d%d", &l, &r);d[r].push_back({l, i});}for (int r = 1; r <= n; r++) {update(1, 1, n, la[r], r, (Tag){a[r], 0, 0, 0, 0, 0});update(1, 1, n, lb[r], r, (Tag){0, b[r], 0, 0, 0, 0});update(1, 1, n, 1, r, (Tag){0, 0, 1, 0, 0, 0});for (auto [l, id] : d[r]) {ans[id] = query(1, 1, n, l, r);}}for (int i = 1; i <= q; i++) printf("%llu\n", ans[i]);return 0;
}

看到这个题我真想$mlgb$道题怎么说呢，很考思维，上次去潍坊培训，老师也说这道题糖丸了，所以昨天这道题我压根都没看，看了题解还一知半解，所以写个部分分出来。

当 $k=2(n-1)$ 时，这个时候就可以在每个栈中放入两个元素，然后留出来一个特殊栈，特殊栈就是要消元素用的。

这样对于某个栈, 来一个属于该栈的卡牌时, 若和底部卡牌相同就利用特殊栈进行 2 操作, 否则就直接放上去。这样可以保证每时每刻, 前$n-1$ 个栈的卡牌个数不超过 2 。

当$k=2n-1$ 时, 此时会出现一种情况: $n-1$ 个栈都包含 $2$个卡牌了, 此时又来最后一种卡牌。

设该卡牌为 $w$, 找到 $n − 1 $ 个放满的栈中底部卡牌之后最先出现的栈$x,x$栈底设为 $u$, 栈顶设为 $v$ , 分下面三种情况讨论:

若 $w$ 的下一次出现时间早于 $u$ , 那么可以 $w$ 直接放到特殊栈（因为特殊栈的作用是消除底部, 在 $u$ 下次出现之前都不会用到特殊栈）
若 $u$下次出现时间早于 $v$ , 那么可以把$w$放到 $x$ 顶部（虽然此时栈内会有 3 个卡牌导致中间的$v$无法消除，但是 $u$ 会早于 $v$ 离开）
剩下的情况意味着下次出现的时间是 $v<u<w$ ，那么可以把 w 放到特殊栈，然后规定接下来的特殊栈改为 x （很明显在 x清空之前，都不会存在 2 操作，所以没影响）
优化成 O ( m ) 要注意几个点:

需要一个数组维护每个卡牌当前所在栈的编号
需要一个队列来分配每个新来的卡牌属于哪个普通栈的，初始每个普通栈能提供两个空位，卡牌出栈会归还空位
查找下一个最先出现底部元素的栈，可以暴力往后找，因为下一次再出现放满栈的局面一定在底部元素出栈后（若是第一种情况 w 先出，就循环到下个 w 结束）。这样所有暴力找的部分不会有交叉, 总循环次数不超过 $m$。

#include <bits/stdc++.h>
using namespace std;
struct Node {int op, x, y;
};
int main() {int _;scanf("%d", &_);while (_--) {int n, m, k;scanf("%d%d%d", &n, &m, &k);vector<int> a(m + 1);vector<Node> ans;vector<int> home(k + 1);                           //每个卡片所属的栈编号vector<deque<int>> s(n + 1);                       //栈queue<int> q;                                      //可以分配的栈的编号int kong = n;                                      //特殊栈编号for (int i = 1; i < n; i++) q.push(i), q.push(i);  //除了特殊栈 每个栈可以提供两个空位for (int i = 1; i <= m; i++) {scanf("%d", &a[i]);}auto cz1 = [&](int x, int t) {ans.push_back({1, x, 0});if (s[x].size() > 0 && s[x].back() == t) {s[x].pop_back();if (x != kong && s[x].size() < 2) q.push(x);home[t] = 0;} else {s[x].push_back(t);home[t] = x;}};auto cz2 = [&](int x, int y) {ans.push_back({2, x, y});home[s[x][0]] = 0;s[x].pop_front();s[y].pop_front();if (s[x].size() < 2) q.push(x);};for (int i = 1; i <= m; i++) {int x = home[a[i]];if (x) {if (s[x].size() == 1)cz1(x, a[i]);else if (s[x].back() == a[i])cz1(x, a[i]);else {cz1(kong, a[i]);cz2(x, kong);}continue;}if (q.size() > 0) {x = q.front();q.pop();cz1(x, a[i]);continue;}// 此时除特殊栈外，其他栈都有两个元素// 找到底部最早出来的栈x  暴力找不会有交叉 保证复杂度O(m)for (int j = i + 1;; j++) {if (a[j] == a[i]) {break;}if (s[home[a[j]]][0] == a[j]) {x = home[a[j]];break;}}if (x == 0) {  //把a[i]放入特殊栈不影响cz1(kong, a[i]);} else {int u = s[x].front(), v = s[x].back();for (int j = i + 1;; j++) {if (a[j] == u) {cz1(x, a[i]);  //底部先出，放到x此时会有3个元素break;}if (a[j] == v) {// 顶部先出，把x作为特殊栈cz1(kong, a[i]);q.push(kong);  //kong这个栈还能放一个元素kong = x;break;}}}}printf("%d\n", ans.size());for (auto [op, x, y] : ans) {if (op == 1)printf("1 %d\n", x);elseprintf("2 %d %d\n", x, y);}}return 0;
}

​