题目大意：
一开始给你一个空图。有4个操作
- 在图中给 u → v u\rightarrow v u→v加一条有向边
- 把 u u u节点涂成红色
- 把 v v v节点涂成黑色
- 询问：在上次询问之后，所有增加的红黑路径的异或和是多少
- 路径权值定义就是 点 的 编 号 × 点 所 在 路 径 的 位 置 求 和 点的编号\times 点所在路径的位置求和 点的编号×点所在路径的位置求和
-
数据范围：
解题思路：
- 对于这么多加加涂涂的图里面肯定在线求解肯定不行我们考虑离线：
- 就是我们先把最终的图给建出来，然后暴力求解所有的路径，在路径上面每个点和边都要记录一个时间：就是在哪次操作的时候加入的边，或者涂成红黑色的
- 然后把贡献 x o r xor xor到那个时间戳的位置去，本质上异或是有消去率的，相邻两个询问查询 x o r xor xor值，也相当于两个图所有路径的 x o r xor xor值
- 我们看一下就是合法路径条数是 5000000 5000000 5000000，我们直接对整个图搜索肯定是T的，因为图上可能有很多无效路径，对于一个有效路径我们知道开头肯定是 r e d red red，结尾肯定是 b l a c k black black,那么我们可以对这个图进行 d f s dfs dfs一遍把所以没用的点给删除，然后再跑就可以了！！
AC code
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = N;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
vector<int> red, q;// red是起点，q是询问的时间
ll ans[maxn];// 统计答案
int black[maxn], cred[maxn];// 记录红黑点被修改的时间
struct node {
int nxt, to, tim;
}edge[maxn];
int cnt = 0, head[maxn];
inline void add(int from, int to, int tim = 0) {
edge[cnt] = {head[from],to, tim};
head[from] = cnt ++;
}
struct Edge {
int u, v, i;
};
vector<Edge> e;
bool tag[maxn], vis[maxn];
inline void dfs(int u) {
vis[u] = 1;
if(black[u]) tag[u] = 1;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int to = edge[i].to;
if(vis[to]) {
tag[u] |= tag[to];
continue;
}
dfs(to);
tag[u] |= tag[to];
}
}
inline void rebuild() {// 重新建图
ms(head,-1);
cnt = 0;
for(auto it : e) {
if(tag[it.u] && tag[it.v])
add(it.u,it.v,it.i);
}
}
// maxv是路径上面最大的时间戳
inline void find_path(int u, int maxv, ll sum, int depth) {
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].to;
find_path(v,max(maxv,edge[i].tim),sum+1ll*depth*u,depth+1);
}
if(black[u]) {
ans[max(maxv,black[u])] ^= sum + 1ll*depth*u;
}
}
int main() {
IOS;
ms(head,-1);
int _;
cin >> _;
for(int i = 1; i <= _; ++ i) {
int op, u, v;
cin >> op;
if(op == 4) q.push_back(i);
else if(op == 3) {
cin >> u;
black[u] = i;
} else if(op == 2) {
int u;
cin >> u;
red.push_back(u);
cred[u] = i;
} else {
cin >> u >> v;
add(u,v);
e.push_back({u,v,i});
}
}
for(auto it : red)
if(!vis[it])
dfs(it);
rebuild();
for(auto it : red)
find_path(it,cred[it],0,1);
for(int i = 1; i <= _; ++ i) ans[i] ^= ans[i-1];
cout << ans[q[0]];
for(int i = 1; i < q.size(); ++ i)
cout << "\n" << (ans[q[i]] ^ ans[q[i-1]]);
}
/*
6
1 2 1
1 1 4
1 4 3
2 2
3 3
4
*/