这道题里最有用的(
Range Insert Subset
Range Query [n?] In Set
破案了 我那五个点是因为维护不知道有什么用的东西炸了
删了就过了
题面
[JRKSJ R4] risrqnis
给你一个长度为 \(n\) 的序列 \(a\)，有 \(q\) 次操作，初始有 \(m\) 个空集 \(S\)，共有两种操作，如下：
1 l r k，将 \(l\sim r\) 加入集合 \(S_k\)，即 \(S_k\gets S_k\cup\{x|l\le x\le r\}\)；
2 l r k，查询对于所有 \(l\le i\le r\) 的 \(a_i\) 中有多少个在集合 \(S_k\) 中，即查询 \(\displaystyle\sum_{i=l}^r[a_i\in S_k]\)。
\(\text{Subtask}\) \(n,q\le\) \(m\le\) 分值 \(\text{Time Limit}\) \(1\) \(10^6\) \(1\) \(30\) \(1500\text{ ms}\) \(2\) \(5\times 10^3\) \(3\times 10^5\) \(15\) \(1000\text{ ms}\) \(3\) \(10^5\) \(10^5\) \(15\) \(1500\text{ ms}\) \(4\) \(3\times 10^5\) \(10^9\) \(40\) \(3000\text{ ms}\) 对于 \(100\%\) 的数据，\(1\le n,q\le 10^6\)，\(1\le m\le 10^9\)，\(1\le a_i\le 10^9\)。
操作 \(1\) 中 \(1\le l\le r\le 10^9\)，操作 \(2\) 中 \(1\le l\le r\le n\)。所有操作中 \(1\le k\le m\)。
没有一个 \(\text{Subtask}\) 取到所有数据范围的最大值，各个 \(\text{Subtask}\) 都有自己的限制。请阅读数据范围表。
我把所有对做题有帮助的部分都粘过来了。最有帮助的在最开头。第二有帮助的是“本题输入文件较大”后面那段。
然后开始解题。
Solution
观察操作性质可以发现每个集合的操作都是独立的。因此可以将各集合的操作分别进行。\(m \le 10^9\) 就是唬你的
首先讨论当 \(m = 1\) 时的解法。由于这时只有一个集合，而每个 \(a_i\) 只需要被加入一次集合，因此可以暴力进行。
沿用这篇闲话里对元素标记的方式，我们使用并查集维护“加入第 \(i\) 个元素时应当加入哪个元素”，跳跃的复杂度均摊是 \(O(n \ \alpha(n))\) 的。加入元素直接使用树状数组在下标位置插入一个 \(1\)，查询时前缀和差分即可。这部分的总时间复杂度是 \(O(n\log n)\)的。
然后 \(m \neq 1\)。这时如果直接沿用上面的方式是很不优的。考虑根号分治。我们分别讨论操作数 \(\le \sqrt q\) 和 \(> \sqrt q\) 的两种集合。
1. \(> \sqrt q\)
此类集合的数量最多是 \(\sqrt q\) 个，一个元素总共加入次数是 \(O(\sqrt q)\)，因此可以考虑沿用如上思路。但是我们发现加入一个元素的总复杂度是 \(O(\sqrt q \log n\ \alpha(n))\) 的，但查询的总复杂度是 \(O(\log n)\) 的。这样很不平衡。因此考虑有限制根号平衡，即使用加入复杂度 \(O(1)\) 查询复杂度 \(O(\sqrt n)\) 的值域分块代替树状数组，因此有这部分的复杂度 \(O(n \ \alpha(n)\sqrt q + n \sqrt n)\)。
看题解说这个 \(\alpha\) 似乎可以通过把并查集换成 ODT 得到严格复杂度。好像确实 因为这样在这部分的总花销是 \(O(n \log n)\) 的，然后摊掉就是对的了。我反正写不出来，wa四个点。正好是我忘记维护加链表时对的那几个点。
我猜测这题数据是卡着分治的边出的，每个点对应一种分治方法。
2. \(\le \sqrt q\)
这时候暴力加入元素寄了。
但我们可以考虑特殊性质。容易发现每个集合对应的值域连续段数 \(\le \sqrt q\)。
考虑使用一个颜色段均摊结构维护值域连续段，查询时就看 \(a\) 在这段查询区间内有多少个数落在当前集合的值域段内就行。这时为了维护查询，我们再考虑一个根号平衡。插入顶多进行 \(O(n)\) 次，但是查询次数是 \(O(n\sqrt q)\) 的。因此考虑使用一个加入复杂度 \(O(\sqrt n)\) 查询复杂度 \(O(1)\) 的前缀和值域分块代替两行前你脑子里出现的什么数据结构。
我们发现这么写保存区间需要 \(O(n \sqrt q)\) 的空间，算一下发现炸的很死。考虑一个区间离线，我们把最终区间用一个前向星啥的链式数据结构存起来，到最后只需要用前向星做一下扫描线就行。
这部分的复杂度是 \(O(n \sqrt n + n \sqrt q)\)。线性空间。
你把这几部分的做法拼吧拼吧就能得到200+行 然后调起来费死劲
然后我发现这题玄学调一下块长能很快
我猜测 \(\color{black}{\text{L}}\color{red}{\text{etItDown}}\) 学长是“稍微”进行了一波块长的优化
反正我是不打算卡
总结：是一道比较优秀的根号分治题目，综合运用了各式根号分治与平衡思想。
但其实想写这题的初心还是上琴糖。
code
#include <bits/stdc++.h>
using namespace std;
inline void get(int & x){ /* 快读 */ }
#define rep(i,a,b) for (register int (i) = (a); (i) <= (b); ++(i))
#define pre(i,a,b) for (register int (i) = (a); (i) >= (b); --(i))
const int N = 1e6 + 10;
int n, q, m, sqn, sqq, sn, lsh[N], ans[N];
int lp[N], rp[N], bl[N], opr[N], a[N];
bool cmp(const int & a, const int & b) {
if (lsh[a] != lsh[b]) return lsh[a] < lsh[b];
return a < b;
}
namespace Subtask1 {
int typ, l, r, tmp, fa[N];
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
int Index[N];
void add(int p) { for (; p <= n; p += p & -p) ++ Index[p]; }
int query(int p) {
int ret = 0;
for (; p; p ^= p & -p) ret += Index[p];
return ret;
}
void main() {
rep(i,1,n+1) fa[i] = i;
while (q--) {
get(typ, l, r, tmp);
if (typ == 1) {
l = lower_bound(lsh+1, lsh+1+n, l) - lsh;
r = upper_bound(lsh+1, lsh+1+n, r) - lsh - 1;
for (int i = find(l); i <= r; i = find(i + 1)) add(a[i]), fa[i] = fa[i + 1];
} else cout << query(r) - query(l - 1) << '\n';
}
}
}
struct queries {
int typ, l, r, k, id;
bool operator < (const queries & b) const {
if (k != b.k) return k < b.k;
return id < b.id;
}
} qry[N];
namespace Les {
int head[N], mlc;
struct ep {
int next, l, r, cont;
} e[N<<2];
void adde(int x, int l, int r, int cont) {
e[++mlc] = { head[x], l, r, cont };
head[x] = mlc;
}
struct node {
int l, r, st;
node (int _l, int _r, int _s) : l(_l), r(_r), st(_s) {}
bool operator < (const node & b) const { return l < b.l; }
} ; set < node > st;
template<typename iter> iter erase(iter itr, int t) {
adde(itr->r, itr->st, t, 1);
adde(itr->l-1, itr->st, t, -1);
return st.erase(itr);
}
int cntblk[1000], cntpts[N];
void add(int p) {
int bel = bl[p];
rep(i, p, rp[bel]) cntpts[i]++;
rep(i, bel+1, sn) cntblk[i]++;
}
int query(int x) { return cntpts[x] + cntblk[bl[x]]; }
void solve(int L, int R) {
st.clear();
rep(i,L,R) {
if (qry[i].typ == 2) continue;
int l = lower_bound(lsh+1, lsh+1+n, qry[i].l) - lsh;
int r = upper_bound(lsh+1, lsh+1+n, qry[i].r) - lsh - 1;
if (l > r) continue;
if (!st.empty()) {
auto itl = st.lower_bound({l, 0, 0}), itr = st.upper_bound({r, 0, 0});
if (itl != st.begin() and prev(itl)->r >= l) -- itl;
if (itr != st.begin() and (--itr)->r >= l) {
l = min(l, itl->l), r = max(r, itr->r);
while(itl != itr) itl = erase(itl, i);
erase(itr, i);
}
} st.emplace(l, r, i);
} for (auto x : st) adde(x.r, x.st, R, 1), adde(x.l - 1, x.st, R, -1);
}
void getAns() {
rep(u,1,n) {
add(a[u]);
for (int i = head[u]; i; i = e[i].next) {
rep(j,e[i].l,e[i].r) if (qry[j].typ == 2)
ans[qry[j].id] += e[i].cont * (query(qry[j].r) - query(qry[j].l - 1));
}
}
}
}
namespace Gre {
int fa[N];
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
int cntblk[1000], cntpts[N];
void add(int p) { cntpts[p]++; cntblk[bl[p]]++; }
int query(int l, int r) {
int bl_l = bl[l], bl_r = bl[r], ret = 0;
if (bl_l == bl_r) rep(i, l, r) ret += cntpts[i];
else {
rep(i, l, rp[bl_l]) ret += cntpts[i];
rep(i, lp[bl_r], r) ret += cntpts[i];
rep(i, bl_l+1, bl_r-1) ret += cntblk[i];
} return ret;
}
void solve(int L, int R) {
rep(i,1,n+1) fa[i] = i;
rep(i,1,sn) cntblk[i] = 0;
rep(i,1,n) cntpts[i] = 0;
rep(i,L,R) {
if (qry[i].typ == 1) {
int l = lower_bound(lsh+1, lsh+1+n, qry[i].l) - lsh;
int r = upper_bound(lsh+1, lsh+1+n, qry[i].r) - lsh - 1;
for (int i = find(l); i <= r; i = find(i + 1)) add(a[i]), fa[i] = fa[i + 1];
} else ans[qry[i].id] = query(qry[i].l, qry[i].r);
}
}
}
namespace SubtaskElse {
void main() {
rep(i,1,sn) lp[i] = (i-1) * sqn + 1, rp[i] = min(n, i * sqn);
rep(i,1,n) bl[i] = (i-1) / sqn + 1;
rep(i,1,q) get(qry[i].typ, qry[i].l, qry[i].r, qry[i].k), opr[i] = qry[i].typ, qry[i].id = i;
sort(qry+1, qry+1+q);
for (int l = 1, r; l <= q; l = r + 1) {
r = l;
while (qry[l].k == qry[r+1].k) r++;
if (r - l + 1 <= sqq) Les :: solve(l, r);
else Gre :: solve(l, r);
} Les :: getAns();
rep(i,1,q) if(opr[i] == 2) cout << ans[i] << '\n';
}
}
signed main() {
ios::sync_with_stdio(false); cout.tie(0);
get(n, q, m);
sqn = pow(n, 0.6); sqq = pow(q, 0.6); sn = (n + sqn - 1) / sqn;
rep(i,1,n) get(lsh[i]), a[i] = i;
sort(a+1, a+1+n, cmp); sort(lsh+1, lsh+1+n);
if (m == 1) Subtask1 :: main();
else SubtaskElse :: main();
return 0;
}
