题解

Difficulty：5.3 / Template

Tag：线段树分治，可撤销并查集

我们画一条时间轴，所有边的存在时间都可看做一个区间。我们建一颗线段树，把每个区间分成 $O(\log q)$ 个小区间。发现这些小区间之间有这样一个关系：要么互不相关，要么包含。

我们从 $[1,q]$ 开始递归左右子树，会发现最先结束的边一定是最后加的边，所以可以用可撤销并查集完成。

码风丑的要死（

namespace cjdst{
    struct node{
		int id, tmp, x, y;
		bool operator < (const node &b) const{
			if(tmp != b.tmp) return tmp < b.tmp;
			if(x != b.x) return x < b.x;
			return y < b.y;
		}
	};
	
	class Segtree{
		std::vector <std::vector <node>> tr;
		std::vector <int> left, right;
		
		void build(int u, int l, int r){
			left[u] = l, right[u] = r;
			if(l == r) return;
			int mid = (l + r) >> 1;
			build(u << 1, l, mid);
			build(u << 1 | 1, mid + 1, r);
		}
		
		void _modify(int u, int l, int r, node val){
			if(left[u] >= l && right[u] <= r){
				tr[u].push_back(val);
				return;
			}
			if(right[u << 1] >= l) _modify(u << 1, l, r, val);
			if(left[u << 1 | 1] <= r) _modify(u << 1 | 1, l, r, val);
		}
		
		int _solve(int u, std::vector <node> &cur, dsu &un){
			ll ans = 0;
			for(auto it:tr[u]){
				if(it.tmp == 1){
					cur.push_back(it);
					un.merge(it.x, it.y);
				}
			}
			if(left[u] == right[u]){
				for(auto it:tr[u]){
					if(it.tmp == 3 && un.find(it.x) == un.find(it.y)){
						ans ^= it.id;
					}
				}
			}else{
				ans = _solve(u << 1, cur, un) ^ _solve(u << 1 | 1, cur, un);
			}
			for(auto it:tr[u]){
				if(it.tmp == 1){
					cur.pop_back();
					un.cancel();
				}
			}
			return ans;
		}

		public:

		Segtree(){}
		Segtree(int n){
			tr.resize(n * 4 + 5);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			build(1, 1, n);
		}
		void modify(int l, int r, node val){
			_modify(1, l, r, val);
		}
		int solve(std::vector <node> &cur, dsu &un){
			return _solve(1, cur, un);
		}
	};

	void solve(){
		int n, m;
		std::cin >> n >> m;
		std::vector <node> a(m + 5);
		Segtree tr(m + 5);
		std::map <node, std::vector <int>> mp;
		for(int i = 1; i <= m; i++){
			std::cin >> a[i].tmp >> a[i].x >> a[i].y;
			if(a[i].x > a[i].y) std::swap(a[i].x, a[i].y);
			if(a[i].tmp == 1){
				mp[a[i]].push_back(i);
				a[i].id = i;
			}else if(a[i].tmp == 2){
				a[i].tmp = 1;
				int l = mp[a[i]].back();
				mp[a[i]].pop_back();
				a[i].id = i;
				tr.modify(l, i - 1, a[i]);
			}else{
				a[i].id = i;
				tr.modify(i, i, a[i]);
			}
		}
		for(auto it:mp){
			auto tmp = it.first;
			for(int j:it.second){
				tmp.id = j;
				tr.modify(j, m, tmp);
			}
		}
		std::cerr << 1; 
		std::vector <node> cur;
		dsu u(n);
		std::cout << tr.solve(cur, u) << '\n';
	}
}

时间复杂度：$O(q\log q\log n)$，常数太大差点没跑过（