序列,静态,求三个区间的可重集的交的大小,离线,\(n,Q\le 10^5\),3s,500MB
缺乏性质 \(\rightarrow\) bitset
静态区间 \(\rightarrow\) 莫队化为单点改
bitset
支持取交,\(x\) 重复 \(cnt_x\) 次即可,空间 \(O(n^2/w)\),时间 \(O(n\sqrt n+{n^2\over w})\),分三次处理减小空间常数
序列,区间赋值,区间数颜色,离线,\(n,Q\le 10^5\),1s,64MB
数颜色 \(\rightarrow\) 维护 pre
珂朵莉树 \(\rightarrow\) pre
只改变 \(O(Q)\) 次
转化:单点改 pre
,查询 \([l,r]\) 内 pre
小于 \(l\) 的数量
图,动态加边,回退到某历史版本,查询某个连通块中权值第 \(k\) 小,离线。\(n,Q\le 10^5\),500ms,20MB
回退历史版本 & 可离线 \(\rightarrow\) dfs 操作树转为撤销
第 \(k\) 小 & 可合并 \(\rightarrow\) 值域分块 或 bitset
值域分块
值域每 \(B\) 个分成一块,按块离线,记录每个连通块点数。
nth_element
,\(O(nB)\)。总时间复杂度 \(O(n\sqrt{n\log n})\) 或 \(O(n\sqrt{n})\),空间线性。
bitset
压位
查询 bitset
可直接 \(O(n/w)\)。
不能开 \(n\) 个 bitset
\(\rightarrow\) 对于点数小于 \(n/w\) 的连通块用链表维护,同时至多存在 \(w\) 个 bitset
,空间线性。
链表查询,合并同上。链表并入 bitset
可启发式暴力。
总时间复杂度 \(O(n^2/w)\),空间线性。
树,每个点的效果为 \(\operatorname{and}/\operatorname{or}/\operatorname{xor}\) 一个数,单点改,询问 \([0,z]\) 中所有数经过路径操作得到的最大值,无需离线。\(n,Q\le 10^5\),值域 \(2^{64}\),250ms,128MB。
二进制操作 \(\rightarrow\) 拆位
二进制复合 \(\rightarrow\) 压位处理复合矩阵,同时处理 \(k\) 位的复合,\(O(k)\rightarrow O(1)\)
总时间复杂度 \(O(n\log^2n+nk)\)
二维平面,先修改后查询,矩形加,矩形求 \(\max\)。\(n\le 5\times 10^4,Q\le 5\times 10^5\),4s,512MB。
矩阵 \(\rightarrow\) 将一维时间化,离线问题转为在线问题
修改,询问在一段时间区间生效 \(\rightarrow\) 猫树转为对一段后缀有效(即修改后无需撤销,询问等价于查历史信息和)
区间加历史最值即可,时间复杂度 \(O(n\log^2n+Q\log n)\)
序列,单点改,求区间长度不超过 \(c\) 的最大字段和,其中 \(c\) 为全局定值,无需离线。\(n,Q\le 10^6\),6s,512MB。
长度不超过 \(c\) \(\rightarrow\) 每 \(c\) 个位置分一块,询问分为每块内全部或两相邻块之间
相邻块后前缀长度和不超过 \(c\) \(\rightarrow\) 直角三角形模式,分成一个矩形和两个小直角三角形
时间复杂度 \(O(n\log n)\)
二维平面,\(n\) 个带权点,\(m\) 个矩形,\(Q\) 次询问区间 \([l,r]\) 内的矩形并中点权之和,离线。\(n,m\le 10^5,Q\le 10^6\),4s,128MB。
静态区间,难以增量 \(\rightarrow\) 扫右维护左
点出现在区间并中 \(\rightarrow\) 扫右端点,维护每个点最后出现时间
KD-Tree,每次暴力收回子树内的出现时间 tag 即可
询问使用 \(O(1)-O(\sqrt n)\) 的数组维护
时间复杂度 \(O(n\sqrt Q+Q\sqrt n)\)
序列,区间减,询问 \(fa\) 数组形成的树上某两个点的 LCA,无需离线。\(n,Q\le 4\times 10^5\),保证 \(fa_i<i\),2.5s,64MB。
形式奇怪 \(\rightarrow\) 考虑分块
询问 LCA \(\rightarrow\) 不断跳 \(fa\)
不断进行重复操作 \(\rightarrow\) 记录每个点跳出块后的第一个位置
散块直接重构,整块 \(\sqrt n\) 次后全部出块,直接打 tag,询问 trivial,时间复杂度 \(O(n\sqrt n)\)
序列,区间大于 \(x\) 的数减 \(x\),区间和与最小最大值,无需离线。\(n,Q\le 5\times 10^5,a_i\le 10^9\),6s,64MB。
和值域有关 \(\rightarrow\) 值域倍增分块(?)
时间复杂度 \(O(nb\log_bV\log n)\)。空间底层分块后线性。
三个序列 \(a,b,c\),单点改 \(a\),询问有几个 \(i<j<k\le r\) 满足 \(b_{a_i}=a_j=c_{a_k}\),离线。\(n\le 2\times 10^5,Q\le 5\times 10^4\),4s,64MB。
阴间条件 \(\rightarrow\) 单点改 \(a,b,c\),询问 \(b_i=a_j=c_k\)
颜色相关 \(\rightarrow\) 次数大小分治,小者暴力,大者维护
小颜色暴力重新 dp,\(O(Q\sqrt n)\) 次区间加,\(O(Q)\) 次单点查
大颜色维护动态 dp,分块维护块内前缀 dp 结果及前缀块 dp 结果,单点改 \(O(\sqrt n)\),查询 前缀块+块内前缀=\(O(1)\)
总时间复杂度 \(O(Q\sqrt n)\),空间离线做到线性
树,边带权(可以为负),静态,\(Q\) 次询问 \([l,r]\) 内的点对有几种不同的 \(\operatorname{lca}\) 带权深度,离线。注意不保证 \(fa_i\le i\)。\(n\le 10^5,Q\le 5\times 10^5\),500ms,512MB。
合法子区间计数 \(\rightarrow\) 考虑有用点对
树上有用点对 \(\rightarrow\) 重剖,由轻子树合并上来,有用点对 \(O(n\log n)\) 对
问题转化为给定 \(O(n\log n)\) 对带权点对,求区间内存在哪些权值。
静态区间问题 \(\rightarrow\) 扫右维护左,转为在线问题
给前缀放上一个颜色,求单点颜色数,树状数组即可。时间复杂度 \(O(n\log^2 n+Q\log n)\)。
二维平面,抽象信息类,半平面乘,单点查,强制在线。\(Q\le 10^5,x_i,y_i\le 10^9\),操作次数 \(2\times 10^7\),2s,512MB。
无法 KD-Tree(值域过大且无法离线)。
很想离线(?)\(\rightarrow\) 根号重构。
问题变成预处理 \(B\) 次修改后每个位置的答案。
发现易于用 \(O(k^2)\) 的时间合并两个大小为 \(k\) 的子问题,所以递归两个子问题就可以做到 \(O(B^2)\) 处理。
总时间复杂度 \(O(nB+{n^2\over B})=O(n\sqrt n)\)。