好像很少有关于top数组性质的博客。 for(int i=top[x];fa[i];i=top[fa[i]]) 可以遍历所有子树中含有x节点的重链链头节点（或叶子节点），由于重链不超过log(n)个,所以这个循环复杂度是O(logN)的。设i是重链链头节点，f是i的父节点，则i是f的轻儿子。所以，如果有操作：对于x节点，他的所有儿子均加上不同的值，且这个值只与儿子节点自身和提供的值有关，那么，可以只更新x节点的重儿子，在x节点加上标记，查询的时候加上答案即可。 D. Tree Queries Hanh is a famous biologist. He loves growing trees ...

Send Boxes to Alice (Hard Version) 给定      a   1    ,    a   2    ,   …   ,    a   n     a_1,a_2,\dots,a_n   a1​,a2​,…,an​，求使      a    x   1     =    a    x   2     =   ⋯   =    a    x   t     =   k   ，   t   =     s   u   m    k     a_{x_1}=a_{x_2}=\dots=a_{x_t}=k，t=\frac{sum}{k}   ax1​​=ax2​​=⋯=a...

解决树上关于子树信息的静态问题，如某节点子树中符合某条件的个数。 cf-600E 给定一棵树，每个节点有一个颜色，求节点x的子树中出现次数最多的颜色，如果有相同次数的，颜色id相加。 考虑暴力，遍历x的每个节点，统计，若只用一个数组，那么两个子节点之间必须要清空数组。 优化，对于清空操作，选择x的轻儿子进行清空，重儿子最后遍历，不需要清空，然后将信息合并给x。 #include<bits/stdc++.h> using namespace std; char buf[1<<20],*P1=buf,*P2=buf; #define gc() (P1==P2&&am...

Cheap Robot You’re given a simple, undirected, connected, weighted graph with n nodes and m edges. Nodes are numbered from 1 to n. There are exactly k centrals (recharge points), which are nodes 1,2,…,k. We consider a robot moving into this graph, with a battery of capacity c, not fixed by the const...

Antenna Coverage 给定若n个区间,每次操作可以使一个区间左右拓宽1,求最小操作次数使得区间[1,m]均被覆盖. 考虑dp: dp[i]=区间[i,m]均被覆盖的最小花费 转移:      d   p   [   i   ]   =   d   p   [   i   +   1   ]    dp[i]=dp[i+1]   dp[i]=dp[i+1],如果     [   1   ,   i   ]    [1,i]   [1,i]被原始区间覆盖. 否则,     p   =   l   −   i   ,   d   p   [   i   ]   =   m   i   n...

cdq分治可以很好地处理平面点对间具有某种性质的值或数量，最近点对也不例外。 参考OI Wiki 先对x排序，cdq返回点集内部最近点对的距离记为mindis。 考虑如何合并左右区间，对于处于点集A的点a和B的点b，显然      ∣   a   .   x   −   b   .   x   ∣   <   =   m   i   n   d   i   s    |a.x-b.x|<=mindis   ∣a.x−b.x∣<=mindis 设a，b属于C，找到C后，对于点p，k属于C，显然也要满足      ∣   p   .   y   −   k   .   y   ∣...

首先，如果有某序列      a   i     a_i   ai​，则      ∑    i   =   1    n    ∣    a   i    −   k   ∣    \sum_{i=1}^n|a_i-k|   ∑i=1n​∣ai​−k∣取最小值时，k为      a   i     a_i   ai​的中位数。（因为如果是pos，则pos向靠近中位数的位置移动能更小），这个性质也能dp 有n个人站成一排，每个人有      a   i     a_i   ai​张纸牌，求最小移动次数使得每个人纸牌数一样，一张纸牌交给旁边的人记为一次移动。 如果tot是n的倍数，则有解，设t=...

可求解多维偏序问题 三维偏序（陌上花开） 有 nn 个元素，第 ii 个元素有       a   i     a_i   ai​、      b   i     b_i   bi​ 、      c   i     c_i   ci​ 三个属性，设      f   (   i   )    f(i)   f(i)表示满足      a   j    ≤    a   i     a_j \leq a_i   aj​≤ai​且       b   j    ≤    b   i     b_j \leq b_i   bj​≤bi​ 且       c   j    ≤    c   i   ...

给定一个长度为      n   (   n   ≤   1    0   5    )    n(n \leq 10^5 )   n(n≤105) 的数列      a   1    ,    a   2    ,   …   ,    a   n     {a_1,a_2,…,a_n}   a1​,a2​,…,an​ ，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。 求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。 先差分，      d   1    =    a   1    ,    d    n ...

费解的开关 你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态 10111 01101 10111 10000 11011 在改变了最左上角的灯的状态后将变成： 01111 11101 10111 10000 11011 再改变它正中间的灯后状态将变成： 01111 11001 11001 10100 11011 给定一些游戏的初始状态，编写程序判断游戏...

斐波那契        f   1    +    f   2    +   ⋯   +    f   n    =    f    n   +   2     −   1    f_1+f_2+\dots+f_n=f_{n+2}−1   f1​+f2​+⋯+fn​=fn+2​−1       f   1   2    +    f   2   2    +   ⋯   +    f   n   2    =    f   n    ⋅    f    n   +   1      f_1^2+f_2^2+\dots+f_n^2=f_{n}⋅f_{n+1}   f12​+f22​+⋯+fn2​...

快读 char buf[1<<20],*P1=buf,*P2=buf; #define gc() (P1==P2&&(P2=(P1=buf)+fread(buf,1,1<<20,stdin),P1==P2)?EOF:*P1++) #define gc() getchar() #define TT template<class T>inline TT bool read(T &x){ x=0;register char c=gc();register bool f=0; while(c<48||c>57){if(c==EOF...

静态主席树 #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) const int MAXN=10; int n,m,a[MAXN],b[MAXN],N; //a为原数组，b为离散后的数组，N为离散后的个数 int root[MAXN],sum[MAXN<<5],node_num; //root[i]:插入i个节点后的树的编号 //sum[i]:节点i代表的区间内数字出现的次数 int lson[MAXN<<5],rson[MAXN<<5]; //ls...

伸展树 #include<bits/stdc++.h> using namespace std; template<class T> inline bool read(T &x){ x=0;register char c=getchar();register bool f=0; while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();} while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); if(f)x=-x; re...