专栏文章

追忆

cchengyifan91
休闲·娱乐参与者 57已保存评论 67

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
67 条
当前快照
1 份
快照标识符
@mm0uqutc
此快照首次捕获于
2026/02/25 01:01
2 周前
此快照最后确认于
2026/02/27 01:01
2 周前
查看原文

前言

本文将介绍如何在 C++ 中只使用 :%()<> 这 66 种特殊字符完成 追忆，其中特殊字符的定义为不能作为变量名的字符，程序中非特殊字符不受限制。注释的 // 以及注释内容同样不受限制。该限制在下文简称为“六字符”。

背景

我常常追忆过去。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。

题目

给定一个 nn 个点 mm 条边的有向图 GG，结点由 11 至 nn 编号。第 ii (1≤i≤m1 \leq i \leq m) 条边从 uiu_i 指向 viv_i，保证 ui<viu_i < v_i。节点 jj (1≤j≤n1 \leq j \leq n) 有两个权值 aj,bja_j, b_j，保证 [a1,…,an][a_1, \ldots, a_n] 与 [b1,…,bn][b_1, \ldots, b_n] 均是 1∼n1 \sim n 的排列。
你需要进行 qq 次操作。操作有以下三种：
  • 1 x y1\ x\ y：交换 axa_x 和 aya_y；
  • 2 x y2\ x\ y：交换 bxb_x 和 byb_y；
  • 3 x l r3\ x\ l\ r：你需要输出满足以下两个条件的点 yy 中 byb_y 的最大值，若不存在满足条件的点则输出 00：
    1. l≤ay≤rl \leq a_y \leq r。
    2. 图 GG 中存在一条 xx 到 yy 的有向路径，即存在整数 k≥1k \geq 1 与 kk 个结点 p1,p2,…,pkp_1, p_2, \ldots, p_k，满足 p1=xp_1 = x，pk=yp_k = y，且对于所有 1≤i<k1 \leq i < k，图 GG 中存在从 pip_i 指向 pi+1p_{i+1} 的有向边。特别地，图 GG 中总是存在一条 xx 到 xx 的有向路径。
对于所有测试点，
  • 1≤T≤31 \leq T \leq 3，
  • 1≤n,q≤1051 \leq n, q \leq 10^5，1≤m≤2×1051 \leq m \leq 2 \times 10^5，
  • ∀1≤i≤m\forall 1 \leq i \leq m，1≤ui<vi≤n1 \leq u_i < v_i \leq n，
  • ∀1≤i≤n\forall 1 \leq i \leq n，1≤ai≤n1 \leq a_i \leq n，且 [a1,…,an][a_1, \ldots, a_n] 是 1∼n1 \sim n 的一个排列，
  • ∀1≤i≤n\forall 1 \leq i \leq n，1≤bi≤n1 \leq b_i \leq n，且 [b1,…,bn][b_1, \ldots, b_n] 是 1∼n1 \sim n 的一个排列，
  • ∀1≤i≤q\forall 1 \leq i \leq q，oi∈{1,2,3}o_i \in \{1, 2, 3\}，1≤xi,yi≤n1 \leq x_i, y_i \leq n，1≤li≤ri≤n1 \leq l_i \leq r_i \leq n。

题解

常规版本

考虑到后面还需要讲解六字符版本，因此代码实现部分会讲的比较详细。
给出一个 O(n(m+q)w+qn)O(\frac {n(m+q)}w+q\sqrt n) 复杂度的解法（该解法是从原题题解区学习的）。
首先，我们需要维护 nn 个集合 ok1⋯oknok_1\cdots ok_n，其中 okiok_i 表示 ii 可以到达的点集合，倒着枚举点即可维护。当然常规的二维数组维护复杂度是 O(nm)O(nm) 的，使用 bitset 可以将复杂度降为 O(nmw)O(\frac {nm}w)。
代码CPP
for (int i = n; i >= 1; i--) {
  for (auto v : G[i]) {
    ok[i] |= ok[v];
  }
}
对每一个查询，我们可以得到一个限制集合 okxok_x。
接下来，就是维护另一个限制集合 {x∣l≤ax≤r}\{x\mid l\le a_x\le r\} 了，将其拆成两个后缀的异或和，即 {x∣l≤ax}∖{x∣r+1≤ax}\{x\mid l\le a_x\}\setminus\{x\mid r+1\le a_x\}。考虑分块，fxf_x 维护 {i∣Lx≤ai}\{i\mid L_x\le a_i\}，这里的集合同样使用 bitset 维护，其中 LiL_i 是第 ii 个块的左端点。整块贡献就可以直接用 ff 查询，散块贡献暴力添加即可。
代码
初始化：
CPP
for (int i = 1; i <= n; i++) f[pos[a[i]]].set(i); // pos[i] 表示 i 所属的块
for (int i = len-1; i; i--) f[i] |= f[i+1]; // len 表示块数
查询后缀：
CPP
node get(int x) {
	node res = f[pos[x]+1];
	for (int i = x; i <= r[pos[x]]; i++) res.set(id1[i]); // l[i] 和 r[i] 表示第 $i$ 个块的左右端点，id1[i] 表示 i 在 a 中的位置。
	return res;
}
有一个小细节，就是查询 r+1r+1 后缀时可能查到 n+1n+1，因此在完整代码中的分块部分我们还需要将 pos[n+1] 初始化，保证它不越界且不和前面的 pos[i] 相等即可。
有了两个限制集合后，对它们取交（按位与）即可得到最终的限制集合 resres。那如何求出 max⁡i∈res(bi)\max\limits_{i\in res}(b_i) 呢？我们维护 gxg_x 表示 {i∣Lx≤bi}\{i\mid L_x\le b_i\}（代码和维护 ff 数组类似）。
暴力的想法就是从小到大枚举每一块，找到最后一个和 resres 有交的块，随后在块内找答案，复杂度是 O(nnw)O(\frac{n\sqrt n}w)。
考虑优化，我们对于 resres 这个 bitset 的前 ii 个 ull 维护 pp 表示最大的和前 ii 个 ull 有交的块，最后在 pp 这个块里扫即可。由于 ii 和 pp 都是递增的，复杂度为 O(nw+n)O(\frac nw+\sqrt n)。
代码CPP
// p 和 q 对应原题操作 3 的 l 和 r
node res = get(q+1);
res ^= get(p);
res &= ok[x]; 
int p = 0, ans = 0;
for (int i = 0; i < SZ && p < len; i++) {
  while (res.a[i] & g[p+1].a[i]) ++p;
}
for (int i = l[p]; i <= r[p]; i++) {
  if (res.get(id2[i])) ans = i; // id2[i] 表示 i 在 b 中的位置
}
cout << ans << '\n';
最后就是处理修改，这里仅考虑操作 11，操作 22 是类似的。假设 ax<aya_x<a_y，找出他们所属的块 p,qp,q：
  • 对于 i≤pi\le p，第 ii 块同时包含 x,yx,y 的贡献，因此 fif_i 不会有影响；
  • 对于 i>qi>q，第 ii 块同时不包含 x,yx,y 的贡献，也不会有影响；
  • 对于 p<i≤qp<i\le q，xx 从不存在变为存在，yy 从存在变为不存在，只需要对 x,yx,y 这两个位置翻转即可。
代码CPP
int l = pos[a[x]], r = pos[a[y]];
if (l > r) swap(l, r);
for (int i = l+1; i <= r; i++) f[i].set(x), f[i].set(y);
swap(a[x], a[y]);
swap(id1[a[x]], id1[a[y]]);
完整代码：
CPP
#include<bits/stdc++.h>
#define _ 0
#define main(x) MiAn();int mIaN();main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;if(strlen(#x))cin>>t>>t;while(t--)mIaN();}int mIaN()
using namespace std;

typedef unsigned long long ull;
int n, m, q;
const int N = 1e5 + 10;
const int B = 512;
const int SZ = 1570;
struct node {
	ull a[SZ];
	void clear() { memset(a, 0, sizeof(a)); } 
	void set(int x) { a[x>>6] ^= 1ull<<(x&63); }
	int get(int x) { return a[x>>6]>>(x&63)&1; }
	void operator &= (const node &x) { for (int i = 0; i < SZ; i++) a[i] &= x.a[i]; }
	void operator |= (const node &x) { for (int i = 0; i < SZ; i++) a[i] |= x.a[i]; }
	void operator ^= (const node &x) { for (int i = 0; i < SZ; i++) a[i] ^= x.a[i]; } 
} f[B], g[B], ok[N];
vector<int> G[N];
int a[N], b[N], id1[N], id2[N], pos[N], l[B], r[B];

node get(int x) {
	node res = f[pos[x]+1];
	for (int i = x; i <= r[pos[x]]; i++) res.set(id1[i]);
	return res;
}

int main(1) {
	cin >> n >> m >> q;
	for (int i = 1; i < B; i++) f[i].clear(), g[i].clear();
	for (int i = 1; i <= n; i++) ok[i].clear(), G[i].clear(), ok[i].set(i); 
	for (int i = 1, u, v; i <= m; i++) cin >> u >> v, G[u].push_back(v);
	for (int i = n; i >= 1; i--) for (auto v : G[i]) ok[i] |= ok[v];
	for (int i = 1; i <= n; i++) cin >> a[i], id1[a[i]] = i;
	for (int i = 1; i <= n; i++) cin >> b[i], id2[b[i]] = i;
	int len = n/B+!!(n%B);
	for (int i = 1; i <= len; i++) l[i] = r[i-1] + 1, r[i] = min(i*B, n);
	for (int i = 1, j = 0; i <= n+1; i++) pos[i] = r[j] < i ? ++j : j; 
	for (int i = 1; i <= n; i++) f[pos[a[i]]].set(i), g[pos[b[i]]].set(i);
	for (int i = len-1; i; i--) f[i] |= f[i+1], g[i] |= g[i+1];
	while (q--) {
		int op, x, y, p, q;
		cin >> op >> x;
		if (op == 1) {
			cin >> y;
			int l = pos[a[x]], r = pos[a[y]];
			if (l > r) swap(l, r);
			for (int i = l+1; i <= r; i++) f[i].set(x), f[i].set(y);
			swap(a[x], a[y]);
			swap(id1[a[x]], id1[a[y]]);
		} else if (op == 2) {
			cin >> y;
			int l = pos[b[x]], r = pos[b[y]];
			if (l > r) swap(l, r);
			for (int i = l+1; i <= r; i++) g[i].set(x), g[i].set(y);
			swap(b[x], b[y]);
			swap(id2[b[x]], id2[b[y]]);
		} else {
			cin >> p >> q;
			node res = get(q+1);
			res ^= get(p);
			res &= ok[x]; 
			int p = 0, ans = 0;
			for (int i = 0; i < SZ && p < len; i++) while (res.a[i] & g[p+1].a[i]) ++p;
			for (int i = l[p]; i <= r[p]; i++) if (res.get(id2[i])) ans = i;
			cout << ans << '\n';
		}
	}
	return ~~(0^_^0);
}

六字符版本

前置知识

  1. 在 C++ 中，<: :> 可以用来替代 [ ]，<% %> 可以用来替代 { }，%: 可以用来替代 #。
  2. 在 C++ 中，and or not 可以用来替代 && || !，bitand bitor xor compl 可以用来替代 & | ^ ~，and_eq or_eq xor_eq 可以用来替代 &= |= ^=。注意，= += -= *= /= %= != == <= >= 无法被替代。
  3. C++20 起，ranges 头文件中提供了许多范围适配器，在代码中只会有两种用法：
    1. std::views::iota(x) bitor std::views::take(y) 一个 xx 开始，长度为 yy 的连续正整数序列（从小到大）。
    2. std::views::iota(x) bitor std::views::take(y) bitor std::views::reverse 一个 xx 结束，长度为 yy 的连续正整数序列（从大到小）。
    这两坨东西都可以使用 for 循环遍历，例如
    CPP
    for (int i : std::views::iota(1) bitor std::views::take(5)) {
  cout << i << char(32);
}
    会输出
    CPP
    1 2 3 4 5
  4. 不能使用任何 .h 结尾的头文件，因此程序中只会包含 iostream ranges（包含 vector）type_traits 这三个头文件。
  5. 为了避免使用 == 和 !=，a != b 可以看作 a xor b，a == b 可以看作 not(a xor b)。
  6. 开启 O2 优化的情况下，(size_t)&((char*)a)[b] 会被直接优化成 a+b。std::addressof(x) 可以用来替代 &x（需要 memory 头文件，但是 ranges 已经包含），std::add_pointer_t<char> 可以用来替代 char*（需要 type_traits 头文件，同样 ranges 已经包含）。
  7. 开启 O2 优化的情况下，sizeof(char[a][b]) 会被直接优化成 a*b。
  8. std::negate<int>{}(x) 可以用来替代 -x。
  9. 常规的声明变量需要 ;，因此我们可以使用 for (int x : {0}) 来声明。{0} 是一个只有一个元素的初始化列表，这个 for 循环的意思就是声明一个 int 变量 x，初值为 0。其他类型也是同理，设置一个合理的初值即可。
  10. 声明数组和声明常规变量有所不同，可以用 for (auto arr : {(int[N]){}}) 来声明。他的作用是在循环之前创建一个临时数组 (int[N]){}，arr 是指向这个临时数组的指针，离开循环后这个数组会被销毁。其他类型的数组或多维数组的声明同理，只需要将 int[N] 换成其他数组类型即可，比如 char[10][30]，unsigned long long[10]。
  11. 常规的语句需要分号（例如 a xor_eq b;），但是对于有返回值的语句（且可以转为 bool），我们可以将它放进 if 的条件里，例如 if (a xor_eq b) {}。cin 可以转换为 bool，表示是否读入成功（例如读到 EOF 就会返回 00）
符合挑战限制的代码肯定是需要 <: :> <% %> %: 的，但是这非常影响可读性，因此下文的示例代码中不会使用。
首先是一堆头文件和宏定义：
CPP
// 头文件
#include<iostream>
#include<ranges>
#define ull unsigned long long
// 0 ~ x-1
#define rg0(x) std::views::iota(0) bitor std::views::take(x)
// 1 ~ x
#define rg1(x) std::views::iota(1) bitor std::views::take(x)
// ad1(a) ad2(b) 可以得到 a + b，之所以这么写是因为多参数宏要用逗号
#define ad1(x) size_t(std::addressof((std::add_pointer_t<char>(x))
#define ad2(x) [x]))
// 相反数
#define neg(x) std::negate<int>{}(x)
// mu1(a) mu2(b) 可以得到 a * b
#define mu1(x) sizeof(char[x]
#define mu2(x) [x])
// a set(x) 相当于翻转 a 这个 bitset 的第 x 位
#define set(x) [(x)>>6] xor_eq 1ull << ((x) bitand 63)
// a get(x) 相当于获取 a 这个 bitset 的第 x 位
#define get(x) [(x)>>6]>>((x) bitand 63) bitand 1 
// 一堆常量
#define N 100010
#define B 512
#define SZ 100
然后是变量和数组的声明：
CPP
for (int c : {0})
for (int t : {0})
for (int n : {0})
for (int m : {0})
for (int q : {0})
for (int len : {0})
for (auto a : {(int[N]){}})
for (auto b : {(int[N]){}})
for (auto id1 : {(int[N]){}})
for (auto id2 : {(int[N]){}})
for (auto pos : {(int[N]){}})
// 需要写链式前向星，因为 vector 的 push_back 需要点
for (auto head : {(int[N]){}})
for (auto to : {(int[N<<1]){}})
for (auto nxt : {(int[N<<1]){}})
for (auto l : {(int[B]){}})   
for (auto r : {(int[B]){}})
for (auto f : {(ull[B][SZ]){}})
for (auto g : {(ull[B][SZ]){}})
for (auto ok : {(ull[N][SZ]){}})
for (auto res : {(ull[SZ]){}})
初始化一堆数组：
CPP
if (std::cin >> n >> m >> q) {}
for (int i : rg0(B)) for (int j : rg0(SZ)) if ((f[i][j] and_eq 0) or (g[i][j] and_eq 0)) {}
for (int i : rg0(N)) for (int j : rg0(SZ)) if (ok[i][j] and_eq 0) {}
for (int i : rg1(n)) if ((head[i] and_eq 0) or (ok[i] set(i))) {} 
for (int u : {0}) for (int v : {0}) for (int i : rg1(m)) {
    if (std::cin >> u >> v) {}
    if (to[i] xor_eq to[i] xor v) {} // a xor_eq a xor b 相当于 a = b
    if (nxt[i] xor_eq nxt[i] xor head[u]) {}
    if (head[u] xor_eq head[u] xor i) {}
}
for (int i : rg1(n) bitor std::views::reverse) {
    for (int p : {head[i]}) {
        while (p) for (int v : {to[p]}) {
            for (int j : rg0(SZ)) if (ok[i][j] or_eq ok[v][j]) {}
            if (p xor_eq p xor nxt[p]) {}
        }
    }
}
分块部分和原代码有所不同，由于 n/B 不太好求，我们需要先用特殊方法求出 len，然后才能维护块的信息。
CPP
if (len and_eq 0) {}
for (int i : {1}) {
    while (ad1(mu1(ad1(i) ad2(neg(1))) mu2(B)) ad2(1) < ad1(n) ad2(1)) if (i xor_eq i xor (ad1(i) ad2(1))) {} // 这一坨丑陋的式子实际上是 (i-1)*B+1 < n+1
    if (i xor_eq i xor (ad1(i) ad2(neg(1)))) {}
    if (len xor_eq len xor i) {}
}
for (int i : rg1(len)) {
    if (l[i] xor_eq l[i] xor (ad1(r[ad1(i) ad2(neg(1))]) ad2(1))) {} // l[i] = r[i-1] + 1
    if (r[i] xor_eq r[i] xor (mu1(i) mu2(B))) {}
    if (n < r[i]) if (r[i] xor_eq r[i] xor n) {}
    for (int j : std::views::iota(l[i]) bitor std::views::take(B)) if (j < n or not (j xor n)) if (pos[j] xor_eq pos[j] xor i) {}
}
if (pos[ad1(n) ad2(1)] or_eq 511) {} // 设置为极大值
for (int i : rg1(n)) if ((f[pos[a[i]]] set(i)) and (g[pos[b[i]]] set(i))) {}
for (int i : rg1(len) bitor std::views::reverse) if (i < len) for (int j : rg0(SZ)) if ((f[i][j] or_eq f[ad1(i) ad2(1)][j]) xor (g[i][j] or_eq g[ad1(i) ad2(1)][j])) {}
最后就是三个操作的部分了：
  • 操作 11 和操作 22 中需要注意的是 swap 不能用，但是 a ^= b ^= a ^= b 相当于 swap(a, b)。
    证明
    ^= 从右向左结合，上面的代码其实就是：
    CPP
    // 令最初的 a, b 为 A, B
a ^= b // a = A^B, b = B
b ^= a // a = A^B, b = A
a ^= b // a = B, b = A
    bitset 的操作用 get 和 set 宏即可。从 l+1 枚举到 r 有些困难，我们可以枚举 len 个，然后只有 i < r or i == r 时才执行循环体内的内容。
    CPP
    if (op < 2) {
    if (std::cin >> x >> y) {}
    for (int l : {pos[a[x]]})
    for (int r : {pos[a[y]]}) {
        if (l > r) if (l xor_eq r xor_eq l xor_eq r) {}
        for (int i : std::views::iota(ad1(l) ad2(1)) bitor std::views::take(len)) if (i < r or not (i xor r)) if ((f[i] set(x)) xor (f[i] set(y))) {}
        if (a[x] xor_eq a[y] xor_eq a[x] xor_eq a[y]) {}
        if (id1[a[x]] xor_eq id1[a[y]] xor_eq id1[a[x]] xor_eq id1[a[y]]) {}
    }
} else if (op < 3) {
    if (std::cin >> x >> y) {}
    for (int l : {pos[b[x]]})
    for (int r : {pos[b[y]]}) {
        if (l > r) if (l xor_eq r xor_eq l xor_eq r) {}
        for (int i : std::views::iota(ad1(l) ad2(1)) bitor std::views::take(len)) if (i < r or not (i xor r)) if ((g[i] set(x)) xor (g[i] set(y))) {}
        if (b[x] xor_eq b[y] xor_eq b[x] xor_eq b[y]) {}
        if (id2[b[x]] xor_eq id2[b[y]] xor_eq id2[b[x]] xor_eq id2[b[y]]) {}
    }
}
  • 操作 33 和原代码也有所不同，get(x) 函数被替换为了 solve(x) 函数（实际上是一个宏），表示让 res 异或上 x 后缀。对于块内的枚举，类似上面的从 l+1 枚举到 r，只不过变成了枚举 B 个。
    CPP
    if (std::cin >> x >> p >> q) {}
for (int i : rg0(SZ)) if (res[i] and_eq 0) {}
#define solve(x) for (int i : rg0(SZ)) if (res[i] xor_eq f[ad1(pos[x]) ad2(1)][i]) {} for (int i : std::views::iota(x) bitor std::views::take(B)) if (i < ad1(r[pos[x]]) ad2(1)) if (res set(id1[i])) {}
if (q xor_eq q xor ad1(q) ad2(1)) {} // ++q
solve(p) solve(q) // res ^= get(p), res ^= get(q)
for (int i : rg0(SZ)) if (res[i] and_eq ok[x][i]) {} // res &= ok[x]
for (int p : {0})
for (int ans : {0}) {
    // 该部分逻辑和原代码没有太大区别，只不过实现方式有区别
    for (int i : rg0(SZ)) if (p < len) while (res[i] bitand g[ad1(p) ad2(1)][i]) if (p xor_eq p xor ad1(p) ad2(1)) {}
    for (int i : std::views::iota(l[p]) bitor std::views::take(B)) if (i < r[p] or not (i xor r[p])) if (res get(id2[i])) if (ans xor_eq ans xor i) {}
    if (std::cout << ans << char(10)) {} // char(10) 是换行
}
完整代码
没有替代 #[]{} 的版本CPP
#include<iostream>
#include<ranges>
#define ull unsigned long long
#define rg0(x) std::views::iota(0) bitor std::views::take(x)
#define rg1(x) std::views::iota(1) bitor std::views::take(x)
#define ad1(x) size_t(std::addressof((std::add_pointer_t<char>(x))
#define ad2(x) [x]))
#define neg(x) std::negate<int>{}(x)
#define mu1(x) sizeof(char[x]
#define mu2(x) [x])
#define set(x) [(x)>>6] xor_eq 1ull << ((x) bitand 63)
#define get(x) [(x)>>6]>>((x) bitand 63) bitand 1
#define N 100010
#define B 512
#define SZ 1570

int main() {
    for (int c : {0})
    for (int t : {0})
    for (int n : {0})
    for (int m : {0})
    for (int q : {0})
    for (int len : {0})
    for (auto a : {(int[N]){}})
    for (auto b : {(int[N]){}})
    for (auto id1 : {(int[N]){}})
    for (auto id2 : {(int[N]){}})
    for (auto pos : {(int[N]){}})
    for (auto head : {(int[N]){}})
    for (auto to : {(int[N<<1]){}})
    for (auto nxt : {(int[N<<1]){}})
    for (auto l : {(int[B]){}})   
    for (auto r : {(int[B]){}})
    for (auto f : {(ull[B][SZ]){}})
    for (auto g : {(ull[B][SZ]){}})
    for (auto ok : {(ull[N][SZ]){}})
    for (auto res : {(ull[SZ]){}}) {
        if (std::cin >> c >> t) {}
        for (int _ : rg0(t)) {
            if (std::cin >> n >> m >> q) {}
            for (int i : rg0(B)) for (int j : rg0(SZ)) if ((f[i][j] and_eq 0) or (g[i][j] and_eq 0)) {}
            for (int i : rg0(N)) for (int j : rg0(SZ)) if (ok[i][j] and_eq 0) {}
            for (int i : rg1(n)) if ((head[i] and_eq 0) or (ok[i] set(i))) {} 
            for (int u : {0}) for (int v : {0}) for (int i : rg1(m)) {
                if (std::cin >> u >> v) {}
                if (to[i] xor_eq to[i] xor v) {}
                if (nxt[i] xor_eq nxt[i] xor head[u]) {}
                if (head[u] xor_eq head[u] xor i) {}
            }
            for (int i : rg1(n) bitor std::views::reverse) {
                for (int p : {head[i]}) {
                    while (p) for (int v : {to[p]}) {
                        for (int j : rg0(SZ)) if (ok[i][j] or_eq ok[v][j]) {}
                        if (p xor_eq p xor nxt[p]) {}
                    }
                }
            }
            for (int i : rg1(n)) if ((std::cin >> a[i]) and (id1[a[i]] xor_eq id1[a[i]] xor i)) {}
            for (int i : rg1(n)) if ((std::cin >> b[i]) and (id2[b[i]] xor_eq id2[b[i]] xor i)) {}
            if (len and_eq 0) {}
            for (int i : {1}) {
                while (ad1(mu1(ad1(i) ad2(neg(1))) mu2(B)) ad2(1) < ad1(n) ad2(1)) if (i xor_eq i xor (ad1(i) ad2(1))) {}
                if (i xor_eq i xor (ad1(i) ad2(neg(1)))) {}
                if (len xor_eq len xor i) {}
            }
            for (int i : rg1(len)) {
                if (l[i] xor_eq l[i] xor (ad1(r[ad1(i) ad2(neg(1))]) ad2(1))) {}
                if (r[i] xor_eq r[i] xor (mu1(i) mu2(B))) {}
                if (n < r[i]) if (r[i] xor_eq r[i] xor n) {}
                for (int j : std::views::iota(l[i]) bitor std::views::take(B)) if (j < n or not (j xor n)) if (pos[j] xor_eq pos[j] xor i) {}
            }
            if (pos[ad1(n) ad2(1)] or_eq 511) {}
            for (int i : rg1(n)) if ((f[pos[a[i]]] set(i)) and (g[pos[b[i]]] set(i))) {}
            for (int i : rg1(len) bitor std::views::reverse) if (i < len) for (int j : rg0(SZ)) if ((f[i][j] or_eq f[ad1(i) ad2(1)][j]) xor (g[i][j] or_eq g[ad1(i) ad2(1)][j])) {}
            for (int _ : rg0(q))
            for (int op : {0})
            for (int x : {0})
            for (int y : {0})
            for (int p : {0})
            for (int q : {0}) {
                if (std::cin >> op) {}
                if (op < 2) {
                    if (std::cin >> x >> y) {}
                    for (int l : {pos[a[x]]})
                    for (int r : {pos[a[y]]}) {
                        if (l > r) if (l xor_eq r xor_eq l xor_eq r) {}
                        for (int i : std::views::iota(ad1(l) ad2(1)) bitor std::views::take(len)) if (i < r or not (i xor r)) if ((f[i] set(x)) xor (f[i] set(y))) {}
                        if (a[x] xor_eq a[y] xor_eq a[x] xor_eq a[y]) {}
                        if (id1[a[x]] xor_eq id1[a[y]] xor_eq id1[a[x]] xor_eq id1[a[y]]) {}
                    }
                } else if (op < 3) {
                    if (std::cin >> x >> y) {}
                    for (int l : {pos[b[x]]})
                    for (int r : {pos[b[y]]}) {
                        if (l > r) if (l xor_eq r xor_eq l xor_eq r) {}
                        for (int i : std::views::iota(ad1(l) ad2(1)) bitor std::views::take(len)) if (i < r or not (i xor r)) if ((g[i] set(x)) xor (g[i] set(y))) {}
                        if (b[x] xor_eq b[y] xor_eq b[x] xor_eq b[y]) {}
                        if (id2[b[x]] xor_eq id2[b[y]] xor_eq id2[b[x]] xor_eq id2[b[y]]) {}
                    }
                } else {
                    if (std::cin >> x >> p >> q) {}
                    for (int i : rg0(SZ)) if (res[i] and_eq 0) {}
                    #define solve(x) for (int i : rg0(SZ)) if (res[i] xor_eq f[ad1(pos[x]) ad2(1)][i]) {} for (int i : std::views::iota(x) bitor std::views::take(B)) if (i < ad1(r[pos[x]]) ad2(1)) if (res set(id1[i])) {}
                    if (q xor_eq q xor ad1(q) ad2(1)) {}
                    solve(p) solve(q)
                    for (int i : rg0(SZ)) if (res[i] and_eq ok[x][i]) {} 
                    for (int p : {0})
                    for (int ans : {0}) {
                        for (int i : rg0(SZ)) if (p < len) while (res[i] bitand g[ad1(p) ad2(1)][i]) if (p xor_eq p xor ad1(p) ad2(1)) {}
                        for (int i : std::views::iota(l[p]) bitor std::views::take(B)) if (i < r[p] or not (i xor r[p])) if (res get(id2[i])) if (ans xor_eq ans xor i) {}
                        if (std::cout << ans << char(10)) {}
                    }
                }
            }
        }
    }
}
CPP
%:include<iostream>
%:include<ranges>
%:define ull unsigned long long
%:define rg0(x) std::views::iota(0) bitor std::views::take(x)
%:define rg1(x) std::views::iota(1) bitor std::views::take(x)
%:define ad1(x) size_t(std::addressof((std::add_pointer_t<char>(x))
%:define ad2(x) <:x:>))
%:define neg(x) std::negate<int><%%>(x)
%:define mu1(x) sizeof(char<:x:>
%:define mu2(x) <:x:>)
%:define set(x) <:(x)>>6:> xor_eq 1ull << ((x) bitand 63)
%:define get(x) <:(x)>>6:>>>((x) bitand 63) bitand 1
%:define N 100010
%:define B 512
%:define SZ 1570

int main() <%
    for (int c : <%0%>)
    for (int t : <%0%>)
    for (int n : <%0%>)
    for (int m : <%0%>)
    for (int q : <%0%>)
    for (int len : <%0%>)
    for (auto a : <%(int<:N:>)<%%>%>)
    for (auto b : <%(int<:N:>)<%%>%>)
    for (auto id1 : <%(int<:N:>)<%%>%>)
    for (auto id2 : <%(int<:N:>)<%%>%>)
    for (auto pos : <%(int<:N:>)<%%>%>)
    for (auto head : <%(int<:N:>)<%%>%>)
    for (auto to : <%(int<:N<<1:>)<%%>%>)
    for (auto nxt : <%(int<:N<<1:>)<%%>%>)
    for (auto l : <%(int<:B:>)<%%>%>)   
    for (auto r : <%(int<:B:>)<%%>%>)
    for (auto f : <%(ull<:B:><:SZ:>)<%%>%>)
    for (auto g : <%(ull<:B:><:SZ:>)<%%>%>)
    for (auto ok : <%(ull<:N:><:SZ:>)<%%>%>)
    for (auto res : <%(ull<:SZ:>)<%%>%>) <%
        if (std::cin >> c >> t) <%%>
        for (int _ : rg0(t)) <%
            if (std::cin >> n >> m >> q) <%%>
            for (int i : rg0(B)) for (int j : rg0(SZ)) if ((f<:i:><:j:> and_eq 0) or (g<:i:><:j:> and_eq 0)) <%%>
            for (int i : rg0(N)) for (int j : rg0(SZ)) if (ok<:i:><:j:> and_eq 0) <%%>
            for (int i : rg1(n)) if ((head<:i:> and_eq 0) or (ok<:i:> set(i))) <%%> 
            for (int u : <%0%>) for (int v : <%0%>) for (int i : rg1(m)) <%
                if (std::cin >> u >> v) <%%>
                if (to<:i:> xor_eq to<:i:> xor v) <%%>
                if (nxt<:i:> xor_eq nxt<:i:> xor head<:u:>) <%%>
                if (head<:u:> xor_eq head<:u:> xor i) <%%>
            %>
            for (int i : rg1(n) bitor std::views::reverse) <%
                for (int p : <%head<:i:>%>) <%
                    while (p) for (int v : <%to<:p:>%>) <%
                        for (int j : rg0(SZ)) if (ok<:i:><:j:> or_eq ok<:v:><:j:>) <%%>
                        if (p xor_eq p xor nxt<:p:>) <%%>
                    %>
                %>
            %>
            for (int i : rg1(n)) if ((std::cin >> a<:i:>) and (id1<:a<:i:>:> xor_eq id1<:a<:i:>:> xor i)) <%%>
            for (int i : rg1(n)) if ((std::cin >> b<:i:>) and (id2<:b<:i:>:> xor_eq id2<:b<:i:>:> xor i)) <%%>
            if (len and_eq 0) <%%>
            for (int i : <%1%>) <%
                while (ad1(mu1(ad1(i) ad2(neg(1))) mu2(B)) ad2(1) < ad1(n) ad2(1)) if (i xor_eq i xor (ad1(i) ad2(1))) <%%>
                if (i xor_eq i xor (ad1(i) ad2(neg(1)))) <%%>
                if (len xor_eq len xor i) <%%>
            %>
            for (int i : rg1(len)) <%
                if (l<:i:> xor_eq l<:i:> xor (ad1(r<:ad1(i) ad2(neg(1)):>) ad2(1))) <%%>
                if (r<:i:> xor_eq r<:i:> xor (mu1(i) mu2(B))) <%%>
                if (n < r<:i:>) if (r<:i:> xor_eq r<:i:> xor n) <%%>
                for (int j : std::views::iota(l<:i:>) bitor std::views::take(B)) if (j < n or not (j xor n)) if (pos<:j:> xor_eq pos<:j:> xor i) <%%>
            %>
            if (pos<:ad1(n) ad2(1):> or_eq 511) <%%>
            for (int i : rg1(n)) if ((f<:pos<:a<:i:>:>:> set(i)) and (g<:pos<:b<:i:>:>:> set(i))) <%%>
            for (int i : rg1(len) bitor std::views::reverse) if (i < len) for (int j : rg0(SZ)) if ((f<:i:><:j:> or_eq f<:ad1(i) ad2(1):><:j:>) xor (g<:i:><:j:> or_eq g<:ad1(i) ad2(1):><:j:>)) <%%>
            for (int _ : rg0(q))
            for (int op : <%0%>)
            for (int x : <%0%>)
            for (int y : <%0%>)
            for (int p : <%0%>)
            for (int q : <%0%>) <%
                if (std::cin >> op) <%%>
                if (op < 2) <%
                    if (std::cin >> x >> y) <%%>
                    for (int l : <%pos<:a<:x:>:>%>)
                    for (int r : <%pos<:a<:y:>:>%>) <%
                        if (l > r) if (l xor_eq r xor_eq l xor_eq r) <%%>
                        for (int i : std::views::iota(ad1(l) ad2(1)) bitor std::views::take(len)) if (i < r or not (i xor r)) if ((f<:i:> set(x)) xor (f<:i:> set(y))) <%%>
                        if (a<:x:> xor_eq a<:y:> xor_eq a<:x:> xor_eq a<:y:>) <%%>
                        if (id1<:a<:x:>:> xor_eq id1<:a<:y:>:> xor_eq id1<:a<:x:>:> xor_eq id1<:a<:y:>:>) <%%>
                    %>
                %> else if (op < 3) <%
                    if (std::cin >> x >> y) <%%>
                    for (int l : <%pos<:b<:x:>:>%>)
                    for (int r : <%pos<:b<:y:>:>%>) <%
                        if (l > r) if (l xor_eq r xor_eq l xor_eq r) <%%>
                        for (int i : std::views::iota(ad1(l) ad2(1)) bitor std::views::take(len)) if (i < r or not (i xor r)) if ((g<:i:> set(x)) xor (g<:i:> set(y))) <%%>
                        if (b<:x:> xor_eq b<:y:> xor_eq b<:x:> xor_eq b<:y:>) <%%>
                        if (id2<:b<:x:>:> xor_eq id2<:b<:y:>:> xor_eq id2<:b<:x:>:> xor_eq id2<:b<:y:>:>) <%%>
                    %>
                %> else <%
                    if (std::cin >> x >> p >> q) <%%>
                    for (int i : rg0(SZ)) if (res<:i:> and_eq 0) <%%>
                    %:define solve(x) for (int i : rg0(SZ)) if (res<:i:> xor_eq f<:ad1(pos<:x:>) ad2(1):><:i:>) <%%> for (int i : std::views::iota(x) bitor std::views::take(B)) if (i < ad1(r<:pos<:x:>:>) ad2(1)) if (res set(id1<:i:>)) <%%>
                    if (q xor_eq q xor ad1(q) ad2(1)) <%%>
                    solve(p) solve(q)
                    for (int i : rg0(SZ)) if (res<:i:> and_eq ok<:x:><:i:>) <%%> 
                    for (int p : <%0%>)
                    for (int ans : <%0%>) <%
                        for (int i : rg0(SZ)) if (p < len) while (res<:i:> bitand g<:ad1(p) ad2(1):><:i:>) if (p xor_eq p xor ad1(p) ad2(1)) <%%>
                        for (int i : std::views::iota(l<:p:>) bitor std::views::take(B)) if (i < r<:p:> or not (i xor r<:p:>)) if (res get(id2<:i:>)) if (ans xor_eq ans xor i) <%%>
                        if (std::cout << ans << char(10)) <%%>
                    %>
                %>
            %>
        %>
    %>
%>

结语

我不会写结语啊，如果你会写抓紧联系我！奖励 0,000,000.00 元。

评论

共 67 条评论，欢迎与作者交流。

正在加载评论...