从套娃过来的。
首先考虑如何方便地描述所有子区间的 \(\text{mex}\)。这是一个经典套路，考虑扫描线，扫右端点 \(R\)，维护一些极长的段 \([l, r]\) 表示 \([l, R], [l + 1, R], \ldots, [r, R]\) 的 \(\text{mex}\) 都是同一个值 \(x\)。
加入一个数 \(x = a_R\)，就找到 \(\text{mex}\) 为 \(x\) 的左端点区间 \([l, r]\)，现在以这一段的点为左端点，以 \(R\) 右端点的区间 \(\text{mex}\) 不再是 \(x\)，那么我们考虑分裂这个区间。也就是说不断找到最小的数 \(y\)，使得 \(p_y < r\)，那么 \([p_y + 1, r]\) 这段的值就是 \(y\)。暴力更新直到整段都被分裂完毕。然后再加入 \(R\)。
因为一个位置最多被分裂一次，所以总共更新的段数是 \(O(n)\) 的。这也能解释为什么极长的 \(\text{mex}\) 有 \(O(n)\) 段。
由上面那个做法我们可以发现一个数 \(x\) 的贡献是一些左端点在 \([l_1, r_1]\)，右端点在 \([l_2, r_2]\) 的区间，其中 \(r_2\) 有可能是当前正在扫的右端点 \(R\)，也有可能是这一段已经被删除而导致的。
这是一个类似二维数点的形式。数据结构维护左端点，那么每个位置的贡献是一个与当前正在扫的右端点 \(R\) 有关的一次函数形式。因为我们需要查询扫完某个右端点后的答案，所以使用主席树维护，每个值为了快速查主席树的 root 可以开一个 map 或 set。为了方便可以标记永久化。
总复杂度 \(O(n \log n)\)。
code
// Problem: H. Holy Diver
// Contest: Codeforces - Codeforces Global Round 3
// URL: https://codeforces.com/problemset/problem/1148/H
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, al[maxn], ar[maxn], a[maxn];
namespace SGT {
int a[maxn << 2];
inline void pushup(int x) {
a[x] = min(a[x << 1], a[x << 1 | 1]);
}
void update(int rt, int l, int r, int x, int y) {
if (l == r) {
a[rt] = y;
return;
}
int mid = (l + r) >> 1;
(x <= mid) ? update(rt << 1, l, mid, x, y) : update(rt << 1 | 1, mid + 1, r, x, y);
pushup(rt);
}
int find(int rt, int l, int r, int x) {
if (a[rt] >= x) {
return -1;
}
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
if (a[rt << 1] < x) {
return find(rt << 1, l, mid, x);
} else {
return find(rt << 1 | 1, mid + 1, r, x);
}
}
}
map<int, int> rt[maxn];
int nt, ls[maxn << 6], rs[maxn << 6];
ll sum0[maxn << 6], sum1[maxn << 6], tag0[maxn << 6], tag1[maxn << 6];
int build(int l, int r) {
int rt = ++nt;
if (l == r) {
return rt;
}
int mid = (l + r) >> 1;
ls[rt] = build(l, mid);
rs[rt] = build(mid + 1, r);
return rt;
}
int update(int rt, int l, int r, int ql, int qr, ll x, ll y) {
int u = ++nt;
ls[u] = ls[rt];
rs[u] = rs[rt];
sum0[u] = sum0[rt];
sum1[u] = sum1[rt];
tag0[u] = tag0[rt];
tag1[u] = tag1[rt];
if (ql <= l && r <= qr) {
tag0[u] += x;
tag1[u] += y;
return u;
}
sum0[u] += x * (min(r, qr) - max(l, ql) + 1);
sum1[u] += y * (min(r, qr) - max(l, ql) + 1);
int mid = (l + r) >> 1;
if (ql <= mid) {
ls[u] = update(ls[u], l, mid, ql, qr, x, y);
}
if (qr > mid) {
rs[u] = update(rs[u], mid + 1, r, ql, qr, x, y);
}
return u;
}
ll query(int rt, int l, int r, int ql, int qr, ll k) {
if (ql <= l && r <= qr) {
return (sum1[rt] + tag1[rt] * (r - l + 1)) * k + sum0[rt] + tag0[rt] * (r - l + 1);
}
int mid = (l + r) >> 1;
ll res = (tag1[rt] * k + tag0[rt]) * (min(r, qr) - max(l, ql) + 1);
if (ql <= mid) {
res += query(ls[rt], l, mid, ql, qr, k);
}
if (qr > mid) {
res += query(rs[rt], mid + 1, r, ql, qr, k);
}
return res;
}
inline void add(int x, int l, int r, int t) {
int u = (--rt[x].end())->scd;
rt[x][t] = update(u, 1, n, l, r, 1 - t, 1);
if (!al[x]) {
al[x] = l;
ar[x] = r;
} else {
al[x] = min(al[x], l);
ar[x] = max(ar[x], r);
}
}
void solve() {
scanf("%d", &n);
int t = build(1, n);
for (int i = 0; i <= n; ++i) {
rt[i][0] = t;
}
ll lstans = 0;
for (int i = 1, x, l, r, k; i <= n; ++i) {
scanf("%d%d%d%d", &x, &l, &r, &k);
x = (x + lstans) % (n + 1);
l = (l + lstans) % i + 1;
r = (r + lstans) % i + 1;
k = (k + lstans) % (n + 1);
if (l > r) {
swap(l, r);
}
SGT::update(1, 0, n, x, i);
a[x] = i;
if (al[x]) {
int t = ar[x];
while (t >= al[x]) {
int y = SGT::find(1, 0, n, t);
add(y, max(al[x], a[y] + 1), t, i);
t = max(al[x], a[y] + 1) - 1;
}
int u = (--rt[x].end())->scd;
rt[x][i] = update(u, 1, n, al[x], ar[x], i - 1, -1);
al[x] = ar[x] = 0;
}
add(x ? 0 : 1, i, i, i);
printf("%lld\n", lstans = query((--rt[k].upper_bound(r))->scd, 1, n, l, r, r));
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}