给定一个最初为空的数组，然后进行 \(n\) 次操作，每次操作给定 \(x,l,r,k\)，在数组末尾插入 \(x\) ，然后查询满足 \(mex(\{a_i, a_{i + 1}, \dots, a_j\}) = k\) 的数对 \((i,j)\) 的个数，强制在线。
\(mex(S)\) 表示集合 \(S\) 中最小的未出现的 自然数。
\(n \leq 2 \times 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 \times 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 << "\033[32;1m" << #args << " -> ", err(args)
#else
#define dbg(...)
#endif
inline void err() { std::cerr << "\033[0m\n"; }
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\n", 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]\)），即 \[ \begin{aligned} &\sum_{i = l}^r\sum_{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]\right)\\ &\{\text{note } s_k = \sum_{j = l}^rb[k][j]\}\\ = &(r + 1)\sum_{k = 1}^rs_k - \sum_{k = 1}^rk\cdot s_k \end{aligned} \] 所以直接在线段树上维护两个值 \(v, v \times time\) 就行了。
每个数都要维护可持久化线段树，要注意写法，容易爆内存（直接改上面的程序成功MLE了）。
#include <bits/stdc++.h>
#ifdef LOCAL
#define dbg(args...) std::cerr << "\033[32;1m" << #args << " -> ", err(args)
#else
#define dbg(...)
#endif
inline void err() { std::cerr << "\033[0m\n"; }
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\n", ans);
}
return 0;
}最后修改于 2021-08-13