grz:水floodfill。注意所有格子高度相等的情况。

gaz:由于规定了连接方向，不用担心去绝对值怎么变号。只需把两组x各自加起来，减一减；两组y各自加起来，减一减。然后加起来。

biu:100000个点2000000条边的无向图，求它的补图的各个连通分量。

由于补图边数太多，直接上并查集肯定吃不消。考虑原图中度数最小的点v0，由于
[tex]n\text{deg}(v_0)\leq \sum_{v}\text{deg}(v)=2m[/tex]
同时
[tex]\text{deg}(v_0)<n[/tex]
可以得知这个点的度数不超过4000。那么问题规模就缩减到了4000，因为其他的点在补图中都与v0邻接，它们同属一个连通分量。于是就能过了。这样做复杂度仍然是线性的。
还有一种拉链表的做法http://www.cfanz.cn/index.php?c=article&a=read&id=56775以后再研究吧。。

meg:每次修改边(u,v)（u是父亲v是儿子）时，影响到的是以v为根的子树中所有结点。线段树维护DFS序即可。

wag:题目相当于是求允许有负数位的四进制表示，使各位绝对值之和最小。先转四进制（高精除单精，不断取余）。然后是DP。
比如四进制数123，它可以是120 + 3 或是130 + (-1)（110 + 7等情况不用考虑，因为若同一种砝码出现大于等于4次就不是最优解）。设f为最小所需砝码数，即有f(123)=min{f(12)+3,f(13)+1}。容易看出最优子结构的性质，从高位DP，对于每一个i要算两个f，分别是原值和加一后所对应的最小砝码数（比如上面的f(12)和f(13)）。
统计方法数目只需在转移时候加一加就好。

odw:砝码两两互为倍数关系，从小到大排个序，可以发现不同的砝码种类数是log(10^9)级别的，只有30左右。
根据贪心的思想，砝码从小到大依次装入一定是最优的
把每个容器的容量写成砝码大小的进制表示，比如当有3,9,18,54这些种类的砝码时，133的容量可以写成2*54+1*18+0*9+2*3+1，末尾的+1永远用不上，可以舍弃，那么各位从低到高分别是(2,0,1,2)。
把所有容器都写成这种表示，并把同一位上全部累加。比如说我们还有一个容器(0,1,2,0)，那么两个容器累加的结果就是(2,1,3,2)。
当我们正在放大小为3的砝码时，就使用最低位上的容量。比如我们只有1个大小为3的砝码，那么塞入以后剩余容量为(1,1,3,2)。接下来要放大小为9的砝码，最低位上的那个1就永远用不上了。假如我们有2个9，而第二位上只有1的容量，那么就往高位借一个18拆成两个9，变成(2,3,2,2)，然后塞入后剩余(2,1,2,2)。以此类推。
当剩余容量不够再放入时即停止，当前已放入的砝码个数即为最优答案。

zap:要求[tex]1\leq x \leq a,1\leq y\leq b,\text{gcd}(x,y)=d[/tex]，
等价于求[tex]1\leq x \leq a',1\leq y \leq b',\text{gcd}(x,y)=1[/tex]，其中[tex]a'=\left \lfloor \frac{a}{d} \right \rfloor,b'=\left \lfloor \frac{b}{d} \right \rfloor[/tex]。
所求答案即为[tex]\sum_{x=1}^{a'}\sum_{y=1}^{b'} [\text{gcd}(x,y)=1][/tex]
[tex]=\sum_{x=1}^{a'}\sum_{y=1}^{b'}\sum_{t|gcd(x,y)}\mu(t)[/tex]

[tex]=\sum_{t=1}^{\text{min}(a',b')}\left \lfloor \frac{a'}{t} \right \rfloor \left \lfloor \frac{b'}{t} \right \rfloor \mu(t)[/tex]
对于连续一段t，[tex]\left \lfloor \frac{a'}{t} \right \rfloor \left \lfloor \frac{b'}{t} \right \rfloor[/tex]的值是相同的，预处理出莫比乌斯函数的前缀和，然后分段累加即可。容易发现分成的段数是根号级别的，所以不会T。