题目大意：维护两个栈，几个操作：
- $PUSH\;x\;num：$把$num$压入栈$x$
- $POP\;x：$弹出栈$x$栈顶元素
- $ADD\;x：$取出两个栈栈顶，把相加值压入栈$x$
- $SUB\;x：$取出两个栈栈顶，把相减的绝对值压入栈$x$
- $DEL\;x：$清空栈$x$
- $MOVE\;x\;y：$把$y$中的元素一个个弹出，依次压入栈$x$
- $SWAP：$交换两个栈
- $END：$结束
题解：可以平衡树搞，但是也可以用双向链表。两个双向链表，除了第$6$个，其他都是基本操作。第$6$个操作时，就把$y$的栈顶与$x$的栈顶接起来，把$x$的栈顶设为$y$的栈底就行了
卡点：莫名$RE$了很多次（包括后面$WA$的），开大数组后通过（我也不知道为什么，中间尝试查错，没有成功）
C++ Code：
#include#include #include #include #define maxn 7000010#define TANG_Yx 20040826struct node { long long w; int nxt[2]; inline int find(int pos = TANG_Yx) { if (pos == TANG_Yx) {for (int i = 0; i < 2; i++) if (nxt[i] != 0) return nxt[i];} else for (int i = 0; i < 2; i++) if (nxt[i] == pos) return nxt[i]; return TANG_Yx; } inline int find_pos(int pos = TANG_Yx) { if (pos == TANG_Yx) {for (int i = 0; i < 2; i++) if (nxt[i] != 0) return i;} else for (int i = 0; i < 2; i++) if (nxt[i] == pos) return i; return TANG_Yx; } inline void clear_nxt(int pos) { int __pos = find_pos(pos); if (__pos != TANG_Yx) nxt[__pos] = 0; }};node S[maxn << 1];struct Stack { int begin, end, idx, sz = 0; inline Stack(int __idx = 0) { begin = end = 0; idx = __idx; sz = 0; } inline bool empty() {return sz < 1;} inline void clear() { begin = end = 0; sz = 0; } inline long long top() { if (empty()) return TANG_Yx; return S[begin].w; } inline int pop() { if (empty()) return TANG_Yx; int __begin = S[begin].find(); sz--; if (sz) { S[__begin].clear_nxt(begin); begin = __begin; } else begin = 0; return sz; } inline void push(long long num) { int __begin = ++idx; S[__begin].w = num; S[__begin].nxt[0] = begin; S[__begin].nxt[1] = 0; int __nxt = S[begin].find_pos(0); S[begin].nxt[__nxt] = __begin; begin = __begin; if (!sz) end = __begin; sz++; }} sta[2];inline long long abs(long long a) {return a < 0 ? -a : a;}int opt = 0, result;int main() { sta[0] = Stack(); sta[1] = Stack(maxn); while (true) { char op[10]; int x; long long y; scanf("%s", op); if (strcmp(op, "PUSH") == 0) { scanf("%d%lld", &x, &y); sta[x ^ opt].push(y); } if (strcmp(op, "POP") == 0) { scanf("%d", &x); result = sta[x ^ opt].pop(); if (result == TANG_Yx) printf("UN"); } if (strcmp(op, "ADD") == 0) { scanf("%d", &x); long long l = sta[0].top(), r = sta[1].top(); if (l != TANG_Yx && r != TANG_Yx) { sta[0].pop(), sta[1].pop(); sta[x ^ opt].push(l + r); } else printf("UN"); } if (strcmp(op, "SUB") == 0) { scanf("%d", &x); long long l = sta[0].top(), r = sta[1].top(); if (l != TANG_Yx && r != TANG_Yx) { sta[0].pop(), sta[1].pop(); sta[x ^ opt].push(abs(l - r)); } else printf("UN"); } if (strcmp(op, "DEL") == 0) { scanf("%d", &x); sta[x ^ opt].clear(); } if (strcmp(op, "MOVE") == 0) { int l, r; scanf("%d%d", &l, &r); l ^= opt, r ^= opt; if (!sta[r].empty()) { if (sta[l].empty()) { sta[l].begin = sta[r].end; sta[l].end = sta[r].begin; sta[l].sz = sta[r].sz; } else { int tmp = S[sta[l].begin].find_pos(0); S[sta[l].begin].nxt[tmp] = sta[r].begin; tmp = S[sta[r].begin].find_pos(0); S[sta[r].begin].nxt[tmp] = sta[l].begin; sta[l].begin = sta[r].end; sta[l].sz += sta[r].sz; } sta[r].clear(); } } if (strcmp(op, "SWAP") == 0) { opt ^= 1; } puts("SUCCESS"); if (strcmp(op, "END") == 0) { break; } } bool flag = false; while (sta[opt].top() != TANG_Yx) { flag = true; printf("%lld ", sta[opt].top()); sta[opt].pop(); } if (!flag) printf("NONE"); puts(""); flag = false; while (sta[opt ^ 1].top() != TANG_Yx) { flag = true; printf("%lld ", sta[opt ^ 1].top()); sta[opt ^ 1].pop(); } if (!flag) printf("NONE"); puts(""); return 0;}