很厉害的 DS 题，记一下 qiuzx 的做法。
考虑到每次操作实际上只会增加 \(O(1)\) 个连续段，一个想法是对时间轴建线段树，在两个子节点已知时合并父节点，合并两个节点可以 \(O(len\log len)\) 解决，此处的总复杂度是 \(O(q\log^2 q)\) 的。
于是我们解决了 reverse，考虑一下 insert 和 delete。因为 insert 实际上代表的是那一次修改是否对 \(p\) 有影响，所以我们实际上就是要去找第一次修改的时刻，所以可以对每个连续段维护线段树节点管辖的区间内是否存在修改，然后容易线段树上二分解决。
再来考虑 delete 怎么做。根据上面，我们只要修改对应是否修改的标记 flag 即可，如果一个连续段的标记被清空，就向上考虑父节点处其归并出来的段。因为每段只会被从左右的两个段各考虑一次，所以这部分的复杂度是 \(O(q\log q)\) 的。
那么总复杂度就做到了 \(O(q\log^2 q)\)。
#include <bits/stdc++.h>
using namespace std;const int kN = 3e5 + 5, kS = kN * 4, kC = kN * 40;
int n, q, c;struct Node {int l, r, p, q;int flag;bool rev;
} node[kC];
vector<int> nxt[kC];struct Query {int o, l, r, p;
};#define ls (o << 1)
#define rs (o << 1 | 1)struct SGT {vector<int> info[kS], vec[kS];void Up(int o) {if(info[rs].empty()) return ;for(int i : info[ls]) {Node nd = node[i];int cl = nd.l, cr = nd.r;int p = nd.p, q = nd.q;int l = -1, r = info[rs].size();while(l + 1 < r) {int mid = (l + r) >> 1;(node[info[rs][mid]].r < p) ? (l = mid) : (r = mid);}for(int j = r; j < info[rs].size(); j++) {int id = info[rs][j];Node tmp = node[id];if((p > tmp.r) || (q < tmp.l)) break;int tl = max(tmp.l, p), tr = min(tmp.r, q);int pl, pr, nl, nr;if(!nd.rev) {pl = cl + tl - p;pr = cr - q + tr;}else {pl = cl + q - tr;pr = cr - tl + p;}if(!tmp.rev) {nl = tl + (tmp.p - tmp.l);nr = tr + (tmp.p - tmp.l);}else {nl = (tmp.p + tmp.r) - tr;nr = (tmp.p + tmp.r) - tl;}Node nw {pl, pr, nl, nr, min(nd.flag, 1) + min(tmp.flag, 1), nd.rev ^ tmp.rev};node[++c] = nw;nxt[i].push_back(c);nxt[id].push_back(c);info[o].push_back(c);}}vec[o] = info[o];sort(info[o].begin(), info[o].end(),[&](int x, int y) { return node[x].l < node[y].l; });sort(vec[o].begin(), vec[o].end(),[&](int x, int y) { return node[x].p < node[y].p; });}void Modify(int o, int l, int r, int x, int typ, int v) {if(l == r) {if(typ == 1) {node[++c] = Node {1, v, 1, v, 1, 0};info[o].push_back(c);if(v < n) {node[++c] = Node {v + 1, n, v + 1, n, 0, 0};info[o].push_back(c);}}else if(typ == 2) {node[++c] = Node {1, v, 1, v, 0, 1};info[o].push_back(c);if(v < n) {node[++c] = Node {v + 1, n, v + 1, n, 0, 0};info[o].push_back(c);}}else {node[++c] = Node {1, n, 1, n, 0, 0};info[o] = vector<int> {c};}vec[o] = info[o];return ;}int mid = (l + r) >> 1;if(mid >= x) Modify(ls, l, mid, x, typ, v);else Modify(rs, mid + 1, r, x, typ, v);Up(o);}vector<int> Erase(int o, int l, int r, int x) {if(l == r) {vector<int> v;for(int i : info[o]) {if(node[i].flag) {v.push_back(i);node[i].flag = 0;}}return v;}int mid = (l + r) >> 1;vector<int> vson, v;if(mid >= x) {vson = Erase(ls, l, mid, x);}else {vson = Erase(rs, mid + 1, r, x);}for(int i : vson) {for(int to : nxt[i]) {if(!--node[to].flag) v.push_back(to);}}return v;}int GetOld(int o, int v) {int p = -1, q = vec[o].size();while(p + 1 < q) {int mid = (p + q) >> 1;(node[vec[o][mid]].q < v) ? (p = mid) : (q = mid);}Node nd = node[vec[o][q]];if(!nd.rev) {return nd.l + v - nd.p;}else {return nd.l + nd.q - v;}}int GetNew(int o, int v) {int p = -1, q = info[o].size();while(p + 1 < q) {int mid = (p + q) >> 1;(node[info[o][mid]].r < v) ? (p = mid) : (q = mid);}Node nd = node[info[o][q]];if(!nd.rev) {return nd.p + v - nd.l;}else {return nd.p + nd.r - v;}}int GetId(int o, int l, int r, int x, int v, vector<Query> &qry) {if(vec[o].size() && (r <= x)) {int tp = GetOld(o, v);qry.push_back(Query {o, l, r, tp});return tp;}int mid = (l + r) >> 1;if(mid >= x) {return GetId(ls, l, mid, x, v, qry);}else {int p = GetId(rs, mid + 1, r, x, v, qry);return GetId(ls, l, mid, x, p, qry);}}int Find(int o, int l, int r, int v) {int p = -1, q = info[o].size();while(p + 1 < q) {int mid = (p + q) >> 1;(node[info[o][mid]].r < v) ? (p = mid) : (q = mid);}if(!node[info[o][q]].flag) return r + 1;if(l == r) return r;int mid = (l + r) >> 1;int lft = Find(ls, l, mid, v);return (lft > mid) ? Find(rs, mid + 1, r, GetNew(ls, v)) : lft;}
} sgt;int main() {// freopen("1.in", "r", stdin);// freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);cin >> n >> q;int lst = 0;for(int i = 1; i <= q; i++) {int a, b, c;cin >> a >> b >> c;b = (b + lst - 1) % ((a <= 2) ? n : q) + 1;c = (c + lst - 1) % n + 1;sgt.Modify(1, 1, q, i, a, b);if(a == 3) sgt.Erase(1, 1, q, b);vector<Query> vec;sgt.GetId(1, 1, q, i, c, vec);lst = 0;reverse(vec.begin(), vec.end());for(Query k : vec) {int tmp = sgt.Find(k.o, k.l, k.r, k.p);if(tmp <= k.r) {lst = tmp;break;}}cout << lst << "\n";}return 0;
}