191003数据结构---金华

CodeForces 103D

给定长度为 \(n\) 的数组 \(a_1,a_2,··· ,a_n\)，\(q\) 次询问，每次给出 \(x,y,k\)，你要 求出 \(\sum_{i=1}^{k} a_{x+iy}\)。 \(n,m≤ 3×10^5，x+ky≤n\)。

sol：

讨论\(y\)的大小，若小于\(\sqrt{M}\)预处理，大于就暴力做。复杂度\(O(N\sqrt{M})\)

BZOJ 2054

给定长度为$ n$ 的序列，$m $次操作，每次操作形如把 \([l,r]\) 覆盖为 \(k\)，求 所有操作后的序列。 \(n≤ 10^6，m≤ 10^7\)。

sol：

考虑操作倒序，对于序列维护并查集，代表它下一个未被染色的点，暴力维护。
复杂度\(O(NlogN)\)

CodeForces 480E

一个 \(n\timesm\)的网格，有的位置上有障碍物。\(q\) 次操作，每次会把 \((x,y)\) 变成障碍物，问每次操作后最大的无障碍正方形大小。 \(n,m,q≤ 2000\)。

sol：

考虑把障碍物全加入后再逐个删除，易得正方形边长不降。枚举边长，维护一个点向左向右最多能走几格，在一个障碍被去掉后暴力修改一行。检验一个正方形是否合法只要用单调队列维护一下即可。复杂度\(O(NM+qN)\)

ZJOI 2016 旅行者

一个$ n×m \(的网格，相邻的点之间连接一条无向边。 给出每条边的边权，\)q$ 次询问 \((x1,y1)\) 到 $(x2,y2) $的最短路。 \(n×m≤ 2×10^4，q≤ 10^5\)。

sol：

考虑分治，每次选择矩形较长的边从中间剖开，对于线上的每一个点做一遍到其他每一个点的最短路。这样显然所有询问点对经过这条线的最短路都能算出。因为每次都是剖的长边，所以剩下矩形的较长边的边长一定小于\(\sqrt{S}\)，S为原矩形的面积。故复杂度\(O(S\sqrt{S}logS+qlogS)\)

平面最近点对

给定平面上的$ N $个点，求最近点对。 \(1 ≤N≤ 10^5\)。

sol：

分治，每次把点分成两半，现在就只要考虑经过中线的点了。设距离为h，那就只有中线左右距离为h的点有用。对于每个这样的点，........每次至多只有7个点能与它产生贡献。复杂度\(O(NlogN)\)

一道例题

给定$ N$ 个点的多边形及其三角剖分，\(Q\) 次询问两点最短路。$ 1 ≤N,Q≤ 10^5\(。 ####sol： 选一条边切开，计算经过这两个点的最短路，分治下去即可。 复杂度\)O(Nlog_{1.5}N)$ 证明？？？

BZOJ 1468

给定一棵 \(N\) 个点的树，求有多少对点距离不超过 \(K\)。$ 1 ≤N≤ 2×10^5$。

sol：

点分治模板题。

BZOJ 2599

给定一棵$ N \(个点的树，每条边有一个长度。求所有距离等于\) K$ 的简单 路径中，边数最小是多少。$ 1 ≤N≤ 2×10^5，1 ≤K≤ 10^6$。

sol：

点分治，就比上一题多记一下长度为k的路径最小使用的边数即可，注意不要算两遍同一棵子树里的边。

另一道例题

给定一棵$ N$ 个点的树，求有多少个区间 \([L,R]\) 满足 \(L,L+ 1,L+ 2,··· ,R\) 这些点对应了一条路径。 \(1 ≤N≤ 10^5\)。

sol：

点分治，对于一个分治重心\(x\)，只需要在剩下的子树内找到根节点编号为\(x+1\)和\(x-1\)的点，找到经过\(x\)的极长合法路径，设路径长度为\(len\)，则\(x\)的贡献为\(len-1\)。

三维偏序问题

给定$ N $个点 \((x_i,y_i,z_i)\)，求有多少对 \((i,j)\)，满足如下三个条件： \(x_i < x_j； y_i < y_j； z_i < z_j\)。$ 1 ≤N≤ 2×10^5$。

sol：

板。

BZOJ 2683

给定一个无限大的网格，两种操作：单点加一个数，或者询问某个矩形 内部的权值和。 \(1 ≤N≤ 2×10^5\)。

sol：

按时间分治。

BZOJ 2716

维护点集，每次加入一个点，或者询问距离一个点曼哈顿距离最近点 是多远。$ 1 ≤N≤ 5×10^5$。

sol：

4遍CDQ

191003数据结构---金华

原文：https://www.cnblogs.com/zxynothing/p/11619234.html