LOJ6669 Nauuo and Binary Tree 解题笔记
题目来源 LOJ6669 Nauuo and Binary Tree 题意简述 这是一道交互题。 有一棵以 111 为根的二叉树，你可以询问任意两点之间的距离，求出每个点的父亲。 节点数不超过 300030003000 ，你最多可以进行 300003000030000 次询问。 解题思路 观察数据范围可知，本题可以接受 O(n2)O(n^2)O(n2) 的时间复杂度，但关键在于如何降低询问复杂度。 显然，本题需要由浅到深地逐层加入节点，否则就无从下手。 设当前待插入的节点为 xxx 。 又由于本题的树满足二叉树的特殊性质，所以可以考虑 xxx 是去左子树还是右子树。 如果暴力询问 xxx 到左儿子和右儿子的距离，选择走哪一棵子树，最坏询问复杂度为 O(n2)O(n^2)O(n2) ，具体情况如下图。 ..
更多P3384 【模板】重链剖分/树链剖分 树剖提高模板
题目来源 P3384 【模板】重链剖分/树链剖分 题意简述 已知一棵包含 NNN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上 zzz。 2 x y，表示求树从 xxx 到 yyy 结点最短路径上所有节点的值之和。 3 x z，表示将以 xxx 为根节点的子树内所有节点值都加上 zzz。 4 x 表示求以 xxx 为根节点的子树内所有节点值之和 1≤N≤1051\le N \leq {10}^51≤N≤105，1≤M≤1051\le M \leq {10}^51≤M≤105，1≤R≤N1\le R\le N1≤R≤N，1≤P≤231−11\le P \le 2^{31}-11≤P..
更多P3379 最近公共祖先 树剖基础模板
来不及解释了，直接上代码 #include<bits/stdc++.h> #define ll long long #define N 500100 using namespace std; ll n,m,s,x,y,a,b; vector<ll> g[N]; bool vis[N]; ll fa[N],dep[N],siz[N],son[N]; ll top[N],tot,dfn[N],rnk[N]; inline void dfs1(ll root, ll depth){ vis[root] = true; dep[root] = depth; ll maxSon = 0; for(auto soni : g[root]){ if(vis[s..
更多P1494 [国家集训队] 小Z的袜子 解题笔记
题目来源 P1494 [国家集训队] 小 Z 的袜子 题意简述 有一个长度为 nnn 的序列 {ci}\{c_i\}{ci}。现在给出 mmm 个询问，每次给出两个数 l,rl,rl,r，从编号在 lll 到 rrr 之间的数中随机选出两个不同位置的数，求两个数相等的概率。 n,m≤5×104,ci≤nn,m\le5\times10^4,c_i\le nn,m≤5×104,ci≤n 解题思路 本题保证 ci≤nc_i\le nci≤n 。事实上，如果不满足这个条件，我们也可以对序列做离散化操作，因为数字的绝对大小与解题无关。 cic_ici 的值域相当有限，于是便可以考虑用桶来维护区间中不同数字的数量。 每次移动区间端点后，只需要考虑新加进来的这个数和前面的数相等的概率是多少，经过某些 O(1..
更多Codeforces-Till I Collapse 解题笔记
题目来源 Codeforces Round 406 (Div. 1) C. Till I Collapse Vjudge页面 题意简述 长度为 nnn 的正整数序列 aia_iai ，数字表示颜色。将序列划分成尽可能少的连续段，每段中颜色的数量不能超过 kkk 。对于所有的 k∈[1,n]k\in[1,n]k∈[1,n] 输出答案。 n≤1×105,ai≤nn\le1\times10^5,a_i\le nn≤1×105,ai≤n 解题思路 暴力的贪心做法是，对于一个确定的 kkk ，从左往右进行划分，尽可能把每一段划分得更长。因为所有的段都是连续的，一个接一个排列，显然，这样的贪心策略不会使得答案更劣。暴力的复杂度为 O(nk)O(nk)O(nk) 。 显然，确定一个区间端点后，区间长度越大，区间..
更多SPOJ Give Away 解题笔记
简直和 UVA-12003 Array Transformer 解题笔记 一模一样。 把这题写一遍单纯是为了巩固分块实现能力。 实际写起来还真的 WA 了一发，确实有很多易错的地方，绝知此事要躬行。 尤其是循环的对象问题。是循环原序列还是块序列？想清楚再写。 #include<bits/stdc++.h> #define N 500100 #define Q 100100 using namespace std; int n,x[N],q; int op,a,b,c; int id[N],len,num; vector<int> block[N]; inline void change(int a, int b){ int aid = id[a]; x[a] = ..
更多UVA-11990 Dynamic Inversion 解题笔记
题目来源 UVA - 11990 Dynamic Inversion Vjudge 页面 题意简述 将一个 n≤2×105n\le 2\times10^5n≤2×105 的排列逐个删去 m≤1×105m\le1\times10^5m≤1×105 个元素，问每次删除元素之前，排列中有多少个逆序对。 解题思路 本题和 UVA-12003 Array Transformer 解题笔记 几乎一模一样，都是分块并在每次修改后保持块内有序，由此可使用二分查找实现高效的查询。 在求逆序对数量初值的时候使用树状数组即可，此后每一次删掉一个数字就查询其左侧比它大的数的数量，在总逆序对数量中减掉即可。 保持块内有序的方式依然可以使用冒泡排序，减少一个 log\loglog 。 与 UVA-12003 实在太像了，代码略..
更多UVA-12003 Array Transformer 解题笔记
题目来源 UVA - 12003 - Array Transformer Vjudge 页面 题意简述 长度为 n≤3×105n\le 3\times10^5n≤3×105 的序列做 m≤5×104m\le 5\times10^4m≤5×104 次操作，每次操作询问 [L,R][L,R][L,R] 之间小于 vvv 的数的个数 kkk ，然后将 apa_pap 修改为 ⌊u∗kR−L+1⌋\displaystyle \left\lfloor \frac{u*k}{R-L+1} \right\rfloor⌊R−L+1u∗k⌋ 。 解题思路 显然这题用线段树是很容易解的，不过我把这个题当做分块的练习题来做，不使用任何树形数据结构。 假设块长为 sss 每次修改完后将 ppp 所在块内的数据排序，复杂度..
更多LOJ6280 分块入门 区间和 解题笔记
题目来源 LibreOJ 6280 数列分块入门 4 题意简述 序列区间加与查询区间和， n≤5×104n\le5\times 10^4n≤5×104 。 解题思路 分块，操作区间中不是整块的部分暴力求解，是整块的部分打标记。 重点在时间复杂度的计算上。 最坏复杂度为操作区间几乎覆盖整个序列时，此时中间的整块数量近似于 ns\displaystyle\frac{n}{s}sn ，两端的非整块长度为 2s2s2s 。忽略常数，单次操作最坏时间复杂度为 O(ns+s)\displaystyle O(\frac{n}{s}+s)O(sn+s) 。 运用基本不等式 ns+s≥2ns⋅s=2n\displaystyle\frac{n}{s}+s\ge2\sqrt{\frac{n}{s}\cdot s}=2\..
更多P5150 生日礼物 题解
虽然题目不难，但背后蕴含的考点还是很有意思的。 本题的核心考点是唯一分解定理。 此考点曾在NOIP中涉及，非常重要！！！ 例如 NOIP2009 Hankson的趣味题 唯一分解定理：设 pip_ipi 表示第 iii 个质数，那么对于任意正整数NNN，都有唯一的一组 a1,a2,a3…ana_1,a_2,a_3\dots a_na1,a2,a3…an ，使得 N=p1a1×p2a2×p3a3×⋯×pnanN=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}\times\dots\times p_n^{a_n} N=p1a1×p2a2×p3a3×⋯×pnan 其中 aia_iai 可以等于000。 用白话文说：任何数都可以表示为他的质因数们的若..
更多