prerequisite: Dynamic Connectivity Problem Offline (segment tree on timeline)
The intended solution is cancer -- dividing queries to blocks of size sqrt, then considering only "important edges" (something similar to JOI18 collapse).
Actually, we can abuse the fact that the online queries are encoded weakly -- variable last can only be zero or one, which mean each edge toggle query has two possible real edge
Let's analyze the process of standard segtree on timeline solution to offline-DCP. Considering an edge (u, v) which lives from L-th to R-th minute, we can see that by the time we "add" the edge, we know answers to queries before the L-th minute.
Back to our problem, if (u, v) has potential to be toggled in queries numbered x1, x2, x3, ..., xk, then we can create timed edges {u, v, (x1 - x2)}, {u, v, (x2 - x3)}, ..., {u, v, (x(k-1) - xk)}. (notice the open intervals) But won't this add excess fake edges ? No, we can maintain an boolean array active[] storing whether the edge is real, at the current time.
Now on when we reach a toggle-type query on a leaf node of the segment tree, we use the information of past queries to fetch the real edge, and toggle that edge in the active[] array. Then, at each node of the segment tree, instead of processing all edges whose timestamps cover the node's interval, we only consider the active edges.
Time complexity: O(n lg ^ 2n)
Note: I am pretty sure the LCT offline dynacon could be used to solve this problem in a similar fashion, with better O(n lgn) complexity, but I have not implemented it yet.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 200000
#define Q 200000
#define Q_ (1 << 18)
#define X (1 << 24) /* max(Q * 2, dsu undo stack size) */
int n, m, m_, op[Q], xx[Q], yy[Q]
, uu[Q << 1], vv[Q << 1], ii[X], jj[X], jj_[X]
/* ii[], jj[], are used for sorting uu[], vv[] and ii[], jj[], jj_[] are reused for dsu rollback */
, occ[Q << 1], start[Q << 1], end[Q << 1] /* prepare() */
, active[Q << 1]
, k
, ff[N] /* counting sort */
, /* dsu w/ undo */ ds[N], top, last
, *eh[Q_ << 1], eo[Q_ << 1];
void append(int i, int j) {
int o = eo[i]++;
if (! o)
eh[i] = (int*)malloc(sizeof **eh * 2);
else if (!(o & (o - 1)))
eh[i] = (int*)realloc(eh[i], sizeof **eh * o * 2);
eh[i][o] = j;
}
int ds_find(int i) {
if (ds[i] < 0)
return i;
return ds_find(ds[i]);
}
int ds_unite(int i, int j) {
i = ds_find(i), j = ds_find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
i ^= j, j ^= i, i ^= j;
ii[top] = i, jj[top] = j; jj_[top] = ds[j]; ++top;
ds[i] += ds[j];
ds[j] = i;
return 1;
}
void ds_undo() {
int i, j, j_;
--top;
i = ii[top], j = jj[top], j_ = jj_[top];
ds[i] -= j_;
ds[j] = j_;
}
int id(int u, int v) {
int lower, upper, mid;
lower = -1, upper = k;
while (upper - lower > 1) {
mid = lower + (upper - lower) / 2;
if (uu[mid] > u || (uu[mid] == u && vv[mid] >= v))
upper = mid;
else
lower = mid;
}
return upper;
}
void input() {
memset(ds, -1, sizeof ds);
scanf("%d%d", &n, &m);
for (m_ = 1; m_ < m; m_ <<= 1)
;
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", op + i, xx + i, yy + i);
if (op[i] == 2)
continue;
for (int fakelast = 0; fakelast < 2; ++fakelast, ++k) {
uu[k] = (xx[i] + fakelast - 1) % n, vv[k] = (yy[i] + fakelast - 1) % n;
ii[k] = k;
if (uu[k] > vv[k])
uu[k] ^= vv[k], vv[k] ^= uu[k], uu[k] ^= vv[k];
}
}
for (int i = 0; i < k; ++i)
++ff[vv[i]];
for (int i = 1; i < n; ++i)
ff[i] += ff[i - 1];
for (int i = 0; i < k; ++i)
jj[--ff[vv[i]]] = i;
memset(ff, 0, sizeof ff);
for (int i = 0; i < k; ++i)
++ff[uu[i]];
for (int i = 1; i < n; ++i)
ff[i] += ff[i - 1];
for (int i = k - 1; i >= 0; --i)
ii[--ff[uu[jj[i]]]] = jj[i];
for (int i = 0; i < k; ++i)
jj[i] = uu[ii[i]];
memcpy(uu, jj, sizeof uu);
for (int i = 0; i < k; ++i)
jj[i] = vv[ii[i]];
memcpy(vv, jj, sizeof vv);
}
void putedge(int id, int l, int r) {
if (l + 1 >= r)
return;
l += m_;
r += m_;
for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (l & 1 ^ 1)
append(l ^ 1, id);
if (r & 1)
append(r ^ 1, id);
}
}
void prepare() {
for (int i = 0; i < k; ++i)
++end[id(uu[i], vv[i])];
for (int l = 0, i = 0; i < k; ++i)
start[i] = l, l += end[i], end[i] = start[i];
for (int ru, rv, i = 0; i < m; ++i) {
if (op[i] == 2)
continue;
for (int fakelast = 0; fakelast < 2; ++fakelast) {
ru = (xx[i] + fakelast - 1) % n, rv = (yy[i] + fakelast - 1) % n;
if (ru > rv)
ru ^= rv, rv ^= ru, ru ^= rv;
occ[end[id(ru, rv)]++] = i;
}
}
for (int last_put, i = 0; i < k; ++i) {
if (start[i] == end[i])
continue;
last_put = occ[start[i]];
for (int j = start[i] + 1; j ^ end[i]; ++j)
putedge(i, last_put, occ[j]), last_put = occ[j];
putedge(i, last_put, m);
}
}
void dnc(int v, int l, int r) {
if (l >= m)
return;
int inserted = 0;
for (int j, i = 0; i < eo[v]; ++i)
if (active[j = eh[v][i]])
inserted += ds_unite(uu[j], vv[j]);
if (l + 1 == r) {
int ru, rv;
ru = (xx[l] + last - 1) % n, rv = (yy[l] + last - 1) % n;
if (ru > rv)
ru ^= rv, rv ^= ru, ru ^= rv;
if (op[l] == 2) {
last = ds_find(ru) == ds_find(rv);
putchar(last + '0');
} else
active[id(ru, rv)] ^= 1;
} else {
int md = (l + r) / 2;
dnc(v << 1, l, md);
dnc(v << 1 | 1, md, r);
}
while (inserted--)
ds_undo();
}
int main(){
input();
prepare();
dnc(1, 0, m_);
return 0;
}