tle on #5,救救孩子
做法和题解是一样的
救救孩子吧,求求了 /kel /kel
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
struct edge { int x, y, k; };
int N, M;
map<pair<int, int>, pair<int, int> > S;
struct linearBase {
int T[31];
void insert(int x) {
for (int i = 30; i >= 0; --i) if (x & (1 << i)) {
if (T[i]) x ^= T[i];
else { T[i] = x; break; }
}
}
int query(int x) {
for (int i = 30; i >= 0; --i) if ((x ^ T[i]) < x) x ^= T[i];
return x;
}
} lb;
struct disjointSetUnion {
int fa[MAXN], rnk[MAXN], val[MAXN];
pair<int*, int> stk[MAXN]; int slen;
void init() { slen = 0; for (int i = 1; i <= N; ++i) fa[i] = i, rnk[i] = 1, val[i] = 0; }
int get(int x) { return fa[x] != x ? get(fa[x]) : x; }
int getdis(int x) { return fa[x] != x ? (getdis(fa[x]) ^ val[x]) : 0; }
int merge(int x, int y, int k) {
x = get(x), y = get(y); if (rnk[x] > rnk[y]) swap(x, y); int cnt = 0;
stk[++slen] = make_pair(&fa[x], fa[x]), stk[++slen] = make_pair(&val[x], val[x]), cnt += 2;
fa[x] = y, val[x] = k;
if (rnk[x] == rnk[y]) stk[++slen] = make_pair(&rnk[y], rnk[y]), ++rnk[y], ++cnt;
return cnt;
}
void undo() {
*stk[slen].first = stk[slen].second, --slen;
}
} dsu;
struct segmentTree {
vector<edge> V[MAXN], Q[MAXN];
#define mid ((l + r) >> 1)
void insModify(int o, int l, int r, int L, int R, edge p) {
if (l == L && r == R) V[o].push_back(p);
else {
if (R <= mid) insModify(o << 1, l, mid, L, R, p);
else if (L > mid) insModify(o << 1 | 1, mid + 1, r, L, R, p);
else insModify(o << 1, l, mid, L, mid, p), insModify(o << 1 | 1, mid + 1, r, mid + 1, R, p);
}
}
void insQuery(int o, int l, int r, int pos, edge p) {
if (l == r) Q[o].push_back(p);
else {
if (pos <= mid) insQuery(o << 1, l, mid, pos, p);
else insQuery(o << 1 | 1, mid + 1, r, pos, p);
}
}
void Solve(int o, int l, int r) {
int cnt = 0;
for (edge p : V[o]) {
if (dsu.get(p.x) == dsu.get(p.y)) lb.insert(p.k ^ dsu.getdis(p.x) ^ dsu.getdis(p.y));
else cnt += dsu.merge(p.x, p.y, p.k ^ dsu.getdis(p.x) ^ dsu.getdis(p.y));
}
if (l == r) {
for (edge p : Q[o]) {
printf("%d\n", lb.query(dsu.getdis(p.x) ^ dsu.getdis(p.y)));
}
} else {
linearBase tmp = lb;
Solve(o << 1, l, mid);
lb = tmp;
Solve(o << 1 | 1, mid + 1, r);
}
while (cnt--) dsu.undo();
}
} sgt;
int main() {
scanf("%d%d", &N, &M); int op, u, v, k;
for (int i = 1; i <= M; ++i) {
scanf("%d%d%d", &u, &v, &k);
S.insert(make_pair(make_pair(u, v), make_pair(k, 1)));
}
int Q; scanf("%d", &Q);
for (int i = 1; i <= Q; ++i) {
scanf("%d%d%d", &op, &u, &v);
if (op == 1) scanf("%d", &k), S.insert(make_pair(make_pair(u, v), make_pair(k, i)));
else if (op == 2) {
map<pair<int, int>, pair<int, int> >::iterator it = S.find(make_pair(u, v));
sgt.insModify(1, 1, Q, it->second.second, i - 1, edge{it->first.first, it->first.second, it->second.first});
S.erase(it);
} else sgt.insQuery(1, 1, Q, i, edge{u, v, 0});
}
for (map<pair<int, int>, pair<int, int> >::iterator it = S.begin(); it != S.end(); ++it) {
sgt.insModify(1, 1, Q, it->second.second, Q, edge{it->first.first, it->first.second, it->second.first});
}
dsu.init();
sgt.Solve(1, 1, Q);
return 0;
}