count
可以发现若能分为 (k) 组当且仅当：
- (k\mid n) .
- 每个子树的大小为(k) 的倍数的恰有(\dfrac nk) 个 .
证明可以和 Sakura 交流一下，这边只会感性理解 .
于是直接维护，需要精细实现 .
首先给所有数 (a_i) 减去 (i)，于是答案就是最长不下降子序列长度 .
证明大概就是 (a_i-a_j\le i-j\Longleftrightarrow a_i-i\le a_j-j) .
时间复杂度 (O(n\log n)) .
最远点对
线段树维护 dis 最大的两个端点，合并的时候枚举 6 种可能合并 .
LCA 可以树剖做，这样线段树建树大概是 (O(n\log^2n)) .
查询的时候查一下 ([a,b]) 查一下 ([c,d]) 然后 4 种情况讨论即可 .
正确性问 Eafoo .
Code
using namespace std;
typedef long long ll;
typedef double db;
typedef pair pii;
const int N = 123456, LgN = __lg(N), INF = 0x3f3f3f3f;
vector g[N];
inline void addedge(int u, int v, ll w){g[u].emplace_back(make_pair(v, w));}
inline void ade(int u, int v, ll w){addedge(u, v, w); addedge(v, u, w);}
int n, q;
namespace HLD
{
int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N], dis[N], cc;
void dfs1(int u)
{
siz[u] = 1;
for (auto e : g[u])
{
int v = e.first, w = e.second;
if (fa[u] == v) continue;
dep[v] = dep[u] + 1; dis[v] = dis[u] + w;
fa[v] = u;
dfs1(v);
siz[u] += siz[v];
if (!son[u]|| (siz[v] > siz[son[u]])) son[u] = v;
}
}
void dfs2(int u, int t)
{
top[u] = t;
rnk[++cc] = u; dfn[u] = cc;
if (!son[u]) return ;
dfs2(son[u], t);
for (auto e : g[u])
if ((e.first != son[u]) && (e.first != fa[u])) dfs2(e.first, e.first);
}
inline int lca(int u, int v)
{
while (top[u] != top[v])
{
if (!u || !v) return 0;
if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
else v = fa[top[v]];
}
return dep[u] > dep[v] ? v : u;
}
inline int dist(int u, int v){return dis[u] + dis[v] - 2 * dis[lca(u, v)];}
}
struct SMT
{
#define ls u << 1
#define rs u << 1 | 1
#define mid ((l + r) >> 1)
struct Node{int u, l, r, L, R;}tr[N << 2];
inline static Node merge(const Node& a, const Node& b)
{
int p1 = a.L, p2 = a.R, p3 = b.L, p4 = b.R, maxn = 0; Node ans;
auto _ = [&](int a, int b){int __ = HLD :: dist(a, b); if (__ > maxn){maxn = __; ans.L = a; ans.R = b;}};
_(p1, p2); _(p1, p3); _(p1, p4); _(p2, p3); _(p2, p4); _(p3, p4);
return ans;
}
inline void pushup(int u){Node _ = merge(tr[ls], tr[rs]); tr[u].L = _.L; tr[u].R = _.R;}
inline void build(int u, int l, int r)
{
tr[u].l = l; tr[u].r = r;
if (l == r){tr[u].L = tr[u].R = l; return ;}
build(ls, l, mid); build(rs, mid+1, r);
pushup(u);
}
inline Node query(int u, int L, int R)
{
int l = tr[u].l, r = tr[u].r;
if ((L mid)) return merge(query(ls, L, R), query(rs, L, R));
if (L
春节十二响
考虑一条链的情况，我们将 (1) 点左右的左链 (L) 和右链 (R) 排序，只需要贪心的把内存占用排名相同的选上即可，正确性显然 .
于是推广到任意树，对于每个点用一个堆维护一下内存占用，合并即可每次取堆顶弹出，剩余的单算 .
分治，我们只需要把每个子树的答案合并，考虑启发式合并，可以证明时间复杂度为 (O(n\log n)) .
Code
using namespace std;
typedef long long ll;
typedef double db;
typedef pair pii;
const int N = 1e6 + 1;
vector g[N];
inline void addedge(int u, int v){g[u].emplace_back(v);}
inline void ade(int u, int v){addedge(u, v); addedge(v, u);}
int n, a[N];
priority_queue q[N];
vector now;
inline void merge(int x, int y)
{
if (q[x].size() < q[y].size()) swap(q[x], q[y]);
while (!q[y].empty())
{
now.emplace_back(max(q[x].top(), q[y].top()));
q[x].pop(); q[y].pop();
}
for (auto it = now.rbegin(); it != now.rend(); ++it) q[x].push(*it);
now.clear();
}
void dfs(int u)
{
for (int v : g[u]){dfs(v); merge(u, v);}
q[u].push(a[u]);
}
int main()
{
scanf("%d", &n);
for (int i=1; i
Original: https://www.cnblogs.com/CDOI-24374/p/16538863.html
Author: Jijidawang
Title: 来自学长的馈赠7 社论
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584453/
转载文章受原作者版权保护。转载请注明原作者出处！