给定一个最初为空的数组，然后进行 (n) 次操作，每次操作给定 (x,l,r,k)，在数组末尾插入 (x) ，然后查询满足 (mex({a_i, a_{i + 1}, dots, a_j}) = k) 的数对 ((i,j)) 的个数，强制在线。
(mex(S)) 表示集合 (S) 中最小的未出现的 自然数。
(n leq 2 imes 10^5)。
为表示方便，下面记 (mex(i, j) = mex({a_i, a_{i + 1}, dots, a_j}))。
容易发现，如果向集合 (S) 中添加数，(mex(S)) 不会减小。
所以如果固定右端点 (j)，(mex(i, j)) 是非严格单调减的；固定左端点 (i)，(mex(i, j)) 是非严格单调增的。
维护一个 (n imes n) 矩阵，(A[i][j] = mex(j, i))，则矩阵 (A) 的每一行从左到右都是非严格单调减的，每一列从上到下都是非严格单调增的。
第 (i) 次操作增加一个数 (x)，考虑从第 (i - 1) 行拓展到第 (i) 行时矩阵 (A) 的变化。
首先 (A[i][i]=[x=0])。
下面只考虑 (j < i) 的情况。
如果 (A[i-1][j]=x)，则 (A[i][j]>x)，否则 (A[i][j] = A[i - 1][j])。
所以每次变化的只有等于 (x) 的那些位置，根据单调性，这是一段区间，记为 ([p,q])。
设 (j in [p, q])，要求 (mex(j, i))，只需要知道最后一次出现的位置小于 (j) 的最小的数。所以用线段树维护序列 (seq_{lastpos[x]} = x) ，每次求区间最小值，找到对应位置 (index)，这个位置右边的所有 (A[i][j]) 都等于这个最小值，然后令 (q = index)，反复迭代，直到待求区间为空。
分析一下这个操作的复杂度，每次相当于删除一个区间 ([p,q])，添加若干个小区间。
开始只有一个区间，最后的区间数不超过 (n)，中间只会删除最多 (n) 次区间。
所以添加区间的总次数不会超过 (2n) ，复杂度为 (O(n log n))。
然后考虑回答询问。
矩形交的面积
我们用四元组 ((top,bottom,left,right)) 描述一个矩形 ({(i,j):top leq i leq bottom,left leq j leq right})。
每次询问可以看作是询问矩形 ((l, r, l, r)) 内 (A[i][j]=k) 的个数。
那么由上面 (mex) 的单调性可以发现，(A[i][j] = k) 的点可以组成一个个连通块，每个连通块由若干个矩形构成阶梯状（矩形的 (left) 相同，(right) 递增）。 且前一个连通块的 (right) 小于后一个连通块的 (left)。
问题转化为求这些矩形与询问矩形交的面积之和。
用 std::vector 存下每个 (k) 的所有矩形，维护前缀面积和，二分出相交与非相交的临界点，对于完全包含的用前缀和搞定，对于相交却不包含的，由于是阶梯状，所以也可以 (O(1)) 计算，细节有点多。
由上面的复杂度分析可知，所有矩形的数量不会超过 (2n) 个，所以总复杂度 (O(n log n))。
#include <bits/stdc++.h>
#ifdef LOCAL
#define dbg(args...) std::cerr << " 33[32;1m" << #args << " -> ", err(args)
#else
#define dbg(...)
#endif
inline void err() { std::cerr << " 33[0m
"; }
template<class T, class... U>
inline void err(const T &x, const U &... a) { std::cerr << x << ' '; err(a...); }
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
typedef long long LL;
typedef std::pair<int, int> PII;
constexpr int N(2e5 + 5);
int n;
struct Rect {
int t, b, l, r; // top, bottem, left, right (closed intervals)
Rect(int t, int b, int l, int r): t(t), b(b), l(l), r(r) {}
inline Rect operator&(const Rect &rhs) const {
return Rect(std::max(t, rhs.t), std::min(b, rhs.b), std::max(l, rhs.l), std::min(r, rhs.r));
}
inline LL area() const { return 1LL * std::max(0, b - t + 1) * std::max(0, r - l + 1); }
};
int pos[N];
std::vector<Rect> rect[N];
std::vector<LL> sum[N];
namespace SegTree {
#define ls o << 1
#define rs o << 1 | 1
int min[N << 2];
void update(int o, int l, int r, int x, int y) {
if (l == r) {
min[o] = y; return;
}
int m = l + r >> 1;
x <= m ? update(ls, l, m, x, y) : update(rs, m + 1, r, x, y);
min[o] = std::min(min[ls], min[rs]);
}
int ask(int o, int l, int r, int x) {
if (x < l) return n;
if (r <= x) return min[o];
int m = l + r >> 1;
return std::min(ask(ls, l, m, x), ask(rs, m + 1, r, x));
}
}
bool vis[N];
std::set<int> s;
PII now[N]; // interval
int top[N];
void insert(int i, int v, int l, int r) {
if (s.count(v)) {
if (top[v] == i) {
assert(l == now[v].second + 1);
now[v].second = r;
return;
}
l = now[v].first;
rect[v].emplace_back(top[v], i - 1, now[v].first, now[v].second);
sum[v].push_back(sum[v].back() + rect[v].back().area());
} else {
s.insert(v);
}
top[v] = i, now[v].first = l, now[v].second = r;
}
int main() {
readInt(n);
for (int i = 0; i <= n; i++) rect[i].emplace_back(0, -1, 0, -1), sum[i].push_back(0);
LL ans = 0;
for (int i = 1, mex = 0, x, l, r, k; i <= n; i++) {
readInt(x, l, r, k);
x = (x + ans) % (n + 1);
l = (l + ans) % i + 1;
r = (r + ans) % i + 1;
k = (k + ans) % (n + 1);
if (l > r) std::swap(l, r);
dbg(x, l, r, k);
// append x
for (vis[x] = 1; vis[mex]; mex++) ;
SegTree::update(1, 1, n, i, x);
if (pos[x]) SegTree::update(1, 1, n, pos[x], n);
pos[x] = i;
auto it = s.find(x);
if (it != s.end()) {
s.erase(it);
auto [p, q] = now[x];
rect[x].emplace_back(top[x], i - 1, p, q);
sum[x].push_back(sum[x].back() + rect[x].back().area());
while (p <= q) {
int v = SegTree::ask(1, 1, n, q - 1), idx = smin(v, mex) ? 0 : pos[v];
// dbg(v, pos[v]);
insert(i, v, idx + 1, q);
q = idx;
}
}
insert(i, !x, i, i);
// ask k
auto &a = rect[k];
auto &b = sum[k];
auto qrect = Rect(l, r, l, r);
ans = 0;
// for (auto u: a) ans += (u & qrect).area();
int p = std::partition_point(a.begin(), a.end(), [&](const Rect &v) { return v.b < l || v.r < l; }) - a.begin();
int mp = std::partition_point(a.begin(), a.end(), [&](const Rect &v) { return v.l < l; }) - a.begin() - 1;
int mq = std::partition_point(a.begin(), a.end(), [&](const Rect &v) { return v.l <= r; }) - a.begin() - 1;
int q = std::partition_point(a.begin(), a.end(), [&](const Rect &v) { return v.t <= r && v.l <= r; }) - a.begin() - 1;
if (p > q) {
ans = 0;
} else if (p == q) {
ans = (a[p] & qrect).area();
} else {
ans = b[q] - b[p - 1];
ans -= a[p].area() - (a[p] & qrect).area();
ans -= a[q].area() - (a[q] & qrect).area();
p++, q--;
smin(mp, q), smax(mq, mp + 1);
if (p <= mp) assert(a[p].l == a[mp].l), ans -= Rect(a[p].t, a[mp].b, a[p].l, l - 1).area();
if (mq <= q) assert(a[mq].l == a[q].l), ans -= b[q] - b[mq - 1] - Rect(a[mq].t, a[q].b, a[q].l, r).area();
}
if (s.count(k)) ans += (Rect(top[k], i, now[k].first, now[k].second) & qrect).area();
printf("%lld
", ans);
}
return 0;
}
可持久化线段树
接上矩阵的思路。
看作每个数维护一个二维数组，每次矩阵内的数 (+1) ，然后询问一个矩阵的和。
这个可以用可持久化线段树维护。
可持久化线段树可以想象成一个矩阵 (a[i][j])，第一维是时间，第二维是区间。
类似于树状数组的区间加区间和的方法，维护差分 (b[i][j] = a[i][j] - a[i - 1][j])。
即每次修改时，在 (top) 时间对区间 ((left,right)+1)，在 (bottom + 1) 时间对区间 ((left, right)-1)
查询矩阵和（本题中时间和区间都是 ([l, r])），即
[egin{aligned}
&sum_{i = l}^rsum_{j = l}^r a[i][j]\
= &sum_{i = l}^r sum_{k = 1}^i sum_{j = l}^rb[k][j]\
= &sum_{k = 1}^r sum_{i = k}^r sum_{j = l}^rb[k][j]\
= &sum_{k = 1}^r (r - k + 1) left(sum_{j = l}^rb[k][j]
ight)\
&{ ext{note } s_k = sum_{j = l}^rb[k][j]}\
= &(r + 1)sum_{k = 1}^rs_k - sum_{k = 1}^rkcdot s_k
end{aligned}
]
所以直接在线段树上维护两个值 (v, v imes time) 就行了。
每个数都要维护可持久化线段树，要注意写法，容易爆内存（直接改上面的程序成功MLE了）。
#include <bits/stdc++.h>
#ifdef LOCAL
#define dbg(args...) std::cerr << " 33[32;1m" << #args << " -> ", err(args)
#else
#define dbg(...)
#endif
inline void err() { std::cerr << " 33[0m
"; }
template<class T, class... U>
inline void err(const T &x, const U &... a) { std::cerr << x << ' '; err(a...); }
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
typedef long long LL;
typedef std::pair<int, int> PII;
constexpr int N(2e5 + 5);
int n, pos[N];
namespace SegTree {
#define ls o << 1
#define rs o << 1 | 1
int min[N << 2];
void update(int o, int l, int r, int x, int y) {
if (l == r) {
min[o] = y; return;
}
int m = l + r >> 1;
x <= m ? update(ls, l, m, x, y) : update(rs, m + 1, r, x, y);
min[o] = std::min(min[ls], min[rs]);
}
int ask(int o, int l, int r, int x) {
if (x < l) return n;
if (r <= x) return min[o];
int m = l + r >> 1;
return std::min(ask(ls, l, m, x), ask(rs, m + 1, r, x));
}
#undef ls
#undef rs
}
struct Node {
Node *ls, *rs;
int v; LL vi;
LL sumv, sumvi;
} t[N * 100], *null = t, *ptr = t + 1;
class PerSegTree {
public:
PerSegTree(): root() { root[0] = null; }
void ins(int i, int l, int r, int v) {
auto it = root.rbegin();
assert(it->first <= i);
ins(root[i] = it->second, 1, n, l, r, v, i);
}
LL ask(int l, int r) {
coef = r + 1;
return ask((--root.upper_bound(r))->second, 1, n, l, r);
}
private:
std::map<int, Node*> root;
void ins(Node *&o, int l, int r, int x, int y, int v, int i) {
*ptr = *o, o = ptr++;
o->sumv += 1LL * v * (y - x + 1);
o->sumvi += 1LL * v * i * (y - x + 1);
if (x == l && r == y) {
o->v += v, o->vi += 1LL * v * i;
return;
}
int m = l + r >> 1;
if (y <= m)
ins(o->ls, l, m, x, y, v, i);
else if (x > m)
ins(o->rs, m + 1, r, x, y, v, i);
else
ins(o->ls, l, m, x, m, v, i), ins(o->rs, m + 1, r, m + 1, y, v, i);
}
int coef;
LL ask(Node *o, int l, int r, int x, int y) {
if (x == l && r == y) return coef * o->sumv - o->sumvi;
int m = l + r >> 1;
LL ans = (1LL * coef * o->v - o->vi) * (y - x + 1);
if (y <= m)
ans += ask(o->ls, l, m, x, y);
else if (x > m)
ans += ask(o->rs, m + 1, r, x, y);
else
ans += ask(o->ls, l, m, x, m) + ask(o->rs, m + 1, r, m + 1, y);
return ans;
}
};
bool vis[N];
std::map<int, PII> s;
int main() {
null->ls = null->rs = null;
readInt(n);
std::vector<PerSegTree> t(n + 1);
LL ans = 0;
for (int i = 1, mex = 0, x, l, r, k; i <= n; i++) {
readInt(x, l, r, k);
x = (x + ans) % (n + 1);
l = (l + ans) % i + 1;
r = (r + ans) % i + 1;
k = (k + ans) % (n + 1);
if (l > r) std::swap(l, r);
dbg(x, l, r, k);
for (vis[x] = 1; vis[mex]; mex++) ;
SegTree::update(1, 1, n, i, x);
if (pos[x]) SegTree::update(1, 1, n, pos[x], n);
pos[x] = i;
auto it = s.find(x);
if (it != s.end()) {
auto [p, q] = it->second;
s.erase(it);
t[x].ins(i, p, q, -1);
while (p <= q) {
int v = SegTree::ask(1, 1, n, q - 1), idx = smin(v, mex) ? 0 : pos[v];
t[v].ins(i, std::max(p, idx + 1), q, 1);
s[v] = PII(idx + 1, q);
q = idx;
}
}
auto &[p, q] = s[!x];
p ? q = i : p = q = i;
t[!x].ins(i, i, i, 1);
ans = t[k].ask(l, r);
printf("%lld
", ans);
}
return 0;
}