<h1 style="font-size:40px;">长郡第3次集训总结</h1>

写在之前

OJ地址问题

如果 oj.kuang.cf 访问不通就用 ojj.kuang.cf

关于OJ的推荐

赵康老师搭建的OJ

地址：120.79.19.114

基本系统：UOJ-System

配置：1Ghz/1G

优点：随时都在线，不会出现无法访问情况

我搭建的OJ

地址：oj.kuang.cf

地址：oj.zendee.cn

地址：ojj.kuang.cf

两个地址哪个访问的通就访问哪个吧

基本系统：QingDaoOJ

配置：2.6Ghz/4G

缺点：目前暂时搭建在本机虚拟机中，还没有转移到服务器上，所以我没开机的时候无法访问

阅读本总结的须知

关于题目编号

以CJ开头的题目编号是长郡集训考试的题目

以P或者CF或者UVA之类的题目开头的题目是自己在洛谷上刷题的题目编号

本题解提供我自己OJ和洛谷上题目的链接，可以随意在哪个上面测评

关于标程代码

会在题解最后附上，建议看了思路过后自己写，写不出来再看标程

长郡集训总结

CJ190725A

题目链接

http://oj.kuang.cf/problem/190725A

https://www.luogu.org/problemnew/show/U79299

基本思路

转换思路，把一个位置能管理到某些人转换为一个位置能被某些人管理到

至于怎么查询一个人能被哪些人管理到，直接树上倍增就行了

标记一个人能被哪些人管理到，树链剖分或者树上差分都可以

涉及知识点

树上倍增，树上差分，深度优先搜索

CJ190725B

题目链接

http://oj.kuang.cf/problem/190725B

https://www.luogu.org/problemnew/show/U79300

基本思路

分析题目，你会发现这似乎是一道三维偏序的题目，然后想用CDQ分治去完成

但是CDQ分治求解三维偏序问题的复杂度是$nlog^2n$ 在这题中只能过掉 $70\%$ 数据

冷静分析题目可以发现题目有一个特殊性质，那就是每一种能力值都不会有重复，也就是对于每一种能力值，都是一个排列。

所以考虑容斥原理，因为现在是要求同时满足三个条件的点对的个数，我们不妨先求出所有两两满足条件的点对个数。大体思路是这样，具体过程详见标程代码。

标程代码我每个部分分都写出来了，可以参考一下

//正解 容斥
    //S(i,j) = (pp[i].a > pp[j].a) + (pp[i].b > pp[j].b) + (pp[i].c > pp[j].c)
    //M(i,j) = max{S(i,j) , S(j,i)}
    //a: cnt whose [M(i,j) = 2]
    //b: cnt whose [M(i,j) = 3]
    //a + b = n * (n - 1) / 2;
    //令 TT 为两两逆序对组数，即 (pp[i].a > pp[j].a && pp[i].b > pp[j].b) + (pp[i].a > pp[j].a && pp[i].c > pp[j].c) + (pp[i].c > pp[j].c && pp[i].b > pp[j].b)
    //TT = 3*b + a
    //TT - n * (n-1) / 2 = 2*b --> b = TT / 2 - n * (n-1) / 4

涉及知识点

CDQ分治求三维偏序，容斥，树状数组，排序

CJ190725C

题目链接

http://oj.kuang.cf/problem/190725C

https://www.luogu.org/problemnew/show/U79301

基本思路

贪心 + DP

涉及知识点

思维，动态规划

CJ190725D

题目链接

http://oj.kuang.cf/problem/190725D

https://www.luogu.org/problemnew/show/U79302

基本思路

这题我没做出来

但是题解说是：

期望DP+贪心。设F[i]表示在i的子树中找到壳要走的期望步数，G[i]表示在i的子树中没找到壳回来要走的期望步数
儿子向父亲转移时，用贪心考虑先走哪个儿子即可

CJ190723A

题目链接

http://oj.kuang.cf/problem/190723A

https://www.luogu.org/problemnew/show/U78916

基本思路

其实这道题部分分暗示你做法很明显

我都是看了部分分，想部分分解法然后想出了正解

观察subtask1的任务特征，w 和 X 只有两种取值，1 和 2

首先一个很容易想到的是，读入的所有大于X的边权插入图中是没有意义的，你把图中所有大于X的边删除也不会对答案有任何影响

所以我们读入的时候索性不插入大于X的边

接下来分类讨论，$X=1$的时候，把所有$w>1$的边删掉，很明显就是问你图中每一个连通块中点对的个数，你可能会想计算答案用 $cnt * (cnt-1) / 2$ 计算，其中cnt为每个连通块的点个数

那么现在$X=2$呢，由于$w≤2$，所以肯定删不掉边了，那么我们自然想到把$w=1$的边先加进去，形成若干连通块，这个时候每个连通块内没有任何点对满足限制，答案暂时为0。然后你再尝试将$w=2$ 的边加进去，这个时候你就会惊奇的发现，你联通任意两个连通块，对答案的贡献实际上就是两个连通块点个数相乘

所以你想出了正解，正解就是先加入所有$w<X$的边，形成若干连通块。然后加入所有$w=X$的边，计算每一条边加进去的贡献。

那么维护连通块点的个数，你也许可以用dfs或者set。但是这里提供一个更简单的方法那就是并查集+维护size，具体可网上搜索介绍

涉及知识点

观察数据范围想正解，并查集维护大小

CJ190723B

http://oj.kuang.cf/problem/190723B

https://www.luogu.org/problemnew/show/U78918

基本思路

这道题很简单，大脑里面稍微想象一下情景或者手造几颗树就可以得到答案了。

重点是如何找点对$(i,j)$形成的路径中(这里我规定i,j在同一条链上即他们的lca=i或者j)，较浅的一个节点的儿子，这个其实倍增一下就好了

涉及知识点

倍增求LCA，倍增思想，树链剖分

CJ190723C

http://oj.kuang.cf/problem/190723C

https://www.luogu.org/problemnew/show/U78919

基本思路

这题主要是思维，对于是$s_1->t_1,s_2->t_2$的最短路径，只可能有两种情况，一种是他们中间有一部分公共的路径，一种是他们中间没有任何一部分公共路径

对于有公共路径的情况，你只需要枚举公共路径的起始节点，这样计算一次必须要的线缆是多少。实际上题目求切断的线缆尽量多就是要让你保留线缆尽量少。

所以所有你算出的结果取min就好了

至于求最短路，你大可使用n次$dijkstra$，但是介于超时可能性极大，而且图中每个边边权都是1，你为啥不用n次BFS求最短路呢？

涉及知识点

广度优先搜索，类似DP？，思维

CJ190723D

http://oj.kuang.cf/problem/190723D

https://www.luogu.org/problemnew/show/U78920

基本思路

这题主要是生成树加边，但是有撤销操作，而路径压缩版本的并查集是不支持撤销操作的

这里介绍并查集的另一种优化方式，那就是按秩合并并查集，也叫启发式合并并查集，它可以支持你回退最后k次合并操作，很符合这题的要求

知道这个知识点后，写这道题也就很简单了，其余细节参考官方题解

http://vfleaking.blog.uoj.ac/blog/15

涉及知识点

按秩合并并查集，离线处理操作

CJ190726A

http://oj.kuang.cf/problem/190726A

https://www.luogu.org/problemnew/show/U79486

基本思路

这道题有很暴力的BFS搜索方法，官方题解也是给的暴力的BFS搜索方法

当然我也有很暴力的DP方法，设$DP[sta]$ 表示用给定的n个树，乱七八糟异或一通，乱七八糟把某一位改一通，能够达到sta状态的最小步数，那么很明显答案就是$min\{ cnt(s ⊕ t),dp[s ⊕ t]\}$ 其中⊕表示异或，然后cnt表示求这个数的二进制下有多少1

至于如何DP嘛，类似于背包问题？你可以看看标程，用队列实现的DP

涉及知识点

动态规划，广度优先搜索，思维

CJ190726B

http://oj.kuang.cf/problem/190726B

https://www.luogu.org/problemnew/show/U79488

基本思路

一道字符串DP题，思路转换为找一个原来串里面出现过的最短的串，满足可以在后面接上一个在原串中后面没有出现过的字符

DP+贪心
最短不出现序列必然是一个出现过的序列（可以为空）+一个字母
设fi表示在i位置，往后第一个字母ch在哪里。
设dp[i]表示在i位置，造出最短不出现序列所需长度
然后倒着DP得出答案，正着贪心输出解即可。

涉及知识点

动态规划，贪心

CJ190726C

http://oj.kuang.cf/problem/190726C

https://www.luogu.org/problemnew/show/U79490

基本思路

一道很好的欧拉反演欧拉函数的题目，重点在于你要推出之前的式子

看到要用欧拉函数先别慌着跳下一道题，这题用到的化简知识点非常套路，记住了就可以，思维难度比较低

但是真正难的是原始式子的推导，对于在同一行或者同一列的三个点的答案贡献，实际上就是$ans1=m*C_m^3 + n * C_m^3$

对于斜着的三个点，容易发现，实际上你就是要在原来的点阵图中框出若干个直角三角形，在这个三角形的斜边上碰到多少个点，答案就加上这么多点×2，为什么×2？因为这里规定三角形直角一定在图左下角，×2相当于把三角形对称一下，计算答案

枚举三角形可以考虑只枚举两条直角边的长度，然后平移，具体推导过程可以自己推一下，最终的结果就是：

$ans2 = 2\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}(n-i)(m-j)(gcd(i,j)-1)$

看到式子里面有gcd，然后又是$O(n,m)$的复杂度，你是不是慌了？实际上，对于处理这里类问题有一个通用的碰运气化简方法，其核心是下面这个式子

对于任意一个正整数x，$\sum\limits_{d|x}φ(d) = x$

证明？自己百度吧，这是欧拉函数的最基本性质之一

所以我们把$gcd(i,j)$ 当成 上面式子中的 x，就可以化简 ans2 为

$ans2 = 2\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}(n-i)(m-j)(\sum\limits_{d|gcd(i,j)}φ(d)-1)$

把后面的那个减1拿出来，就比较爽

$ans2 = 2(\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}(n-i)(m-j)\sum\limits_{d|gcd(i,j)}φ(d) - \sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}(n-i)(m-j))$

然后是一个技巧，更换枚举顺序，把通过枚举i，j确定d改为通过枚举d来确定i，j来进一步化简时间复杂度

式子就可以写成这样子，搞不懂的同学多想想怎么由i，j算d的，返回去怎么通过d推出i，j

$ans2=2(\sum\limits_{d=1}^{min(n-1,m-1)}φ(d)\sum\limits_{i=1}^{\lfloor\frac{n-1}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m-1}{d}\rfloor}(n-di)(m-dj) - \sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}(n-i)(m-j))$

然后又一个重要的技巧，那就是形如这样的式子

$\sum\limits_{i=x1}^{y1}\sum\limits_{j=x2}^{y2}i*j$

注意，这里后面不一定是i*j，只要是后面是两个等差数列相乘的，都可以O1算，因为这个式子可以调换顺序，变成这个样子

$\sum\limits_{i=x1}^{y1}i * \sum\limits_{j=x2}^{y2}j$

两个求和都是等差数列求和，高斯求和不用多说了吧，然后相乘

所以上面的ans2的后面的两坨，都可以O(1)求得，整体复杂度O(min(n-1,m-1))

涉及知识点

欧拉函数化简，套路性化简，等差数列求和，数论

CJ190726D

http://oj.kuang.cf/problem/190726D

https://www.luogu.org/problemnew/show/U79491

基本思路

我做不来，看官方题解吧。

第二类斯特林数+prufer序列+推式子

涉及知识点

第二类斯特林数+prufer序列+推式子

CJ190729A

http://oj.kuang.cf/problem/190729A

https://www.luogu.org/problem/U80110

基本思路

简单送分题，将整数q分解质因数过后，所有因数个数只有为2的时候Bob胜利，否则Alice胜利

因为无论如何，只要对方取数过后留给你的因数个数还剩2个，你就输了，你只能取一个，然后对方就取不到了

所以除非先手Alice一来就被拥有两个因数，否则她都可以只给Bob剩下2个因数，让自己赢

涉及知识点

质数筛法，分解质因数，思维，简单博弈

CJ190729B

http://oj.kuang.cf/problem/190729B

https://www.luogu.org/problemnew/show/U80111

基本思路

考虑贪心的思维，如果一个视频的流量可以同时杀死多个蔡徐坤，那么肯定必须物尽其用，杀死流量需求最大的蔡徐坤。所以暴力想法就是把蔡徐坤们按照流量排序，然后把鬼畜视频按照花费排序，从小到大的枚举每个视频，对于每个视频能杀死一堆蔡徐坤，就杀死流量最大的蔡徐坤

但是时间复杂度明显不对，考虑如何优化。看题目数据范围，蔡徐坤需要的流量和视频流量都在$10^6$内，那么完全可以用桶来存，不知道桶是什么的，可以把桶看成一个数组，数组每个位置存流量为其下标的物品。如果是蔡徐坤桶，那么每个位置存当前下标流量下有多少个蔡徐坤；如果是鬼畜视频桶，实际上是一个$10^6$大小的vector，因为同一个花费的视频可能有多个。桶的优化在于，你可以在很快的时间$(O(n))$内从小到大遍历，而不必花费$O(nlogn)$去排序，这也算是用空间换时间的一种方式吧。

第二个优化是，如何找到所有能被该视频杀死的蔡徐坤里面，流量最大的蔡徐坤，然后把他杀死？其实你可以用链表跳，但是更快也更直观的方式是用路径压缩版本的并查集。试想蔡徐坤桶里面每个下标对应并查集中的一个元素：如果一个桶里面有值(即所有存活的蔡徐坤里面有这个流量的蔡徐坤)，那么这个元素$i$的$fa[i]=i$，表示这个地方有值；如果一个桶里面没有值(即所有存活的蔡徐坤里面没有这个流量的蔡徐坤)，那么这个元素$i$的$fa[i]=get(i-1)$表示这个地方没有值，要找流量更小的蔡徐坤就去前面找。

然后对于每个视频，只需要在蔡徐坤桶里面去用$fa[]$跳就行了

具体参考标程

涉及知识点

路径压缩并查集，桶，贪心思想，优化思想

鸡你太美！

Codechef REIGN

https://cn.vjudge.net/problem/CodeChef-REIGN

基本思路

先$O(n)$的扫描两遍数组，第一遍从头到尾预处理出对于$i$结尾的前缀，最大的连续和$pre[i]$，第二遍从尾到头预处理出对于$i$开头的后缀，最大的连续和$suf[i]$。处理可用以前的贪心思想处理

然后$O(n)$的枚举一个点$p$，在这个点前的一段区间里面找一段最大连续和，即$pre[p]$，再在这个点后$p+k+1$的位置找到一段最大连续和(因为题目规定两段必须相差大于$k$)，即$suf[p+k+1]$，对于所有枚举的点$p$取最大值即可

涉及知识点

预处理，贪心

CodeForces 1037E

https://cn.vjudge.net/problem/CodeForces-1037E

基本思路

考虑转换思想，将每条边加进来就得一次答案转换为先把所有边加进来再删边。于是我们可以先离线所有操作，然后算出最后的答案，注意中途维护每个点的度数$degree[i]$。

然后倒着删除每条边，对于删除的每条边，有两个点会度数减少，同时造成很多人无法去旅行，造成的影响可以用BFS搜索得到。注意一点，对于一个已经无法去旅游的人，直接标记，下次搜索就不用管他了，因为管他或者不管他都不会影响答案。

涉及知识点

广度优先搜索，思维转换，离线询问

Codechef DIGJUMP

https://cn.vjudge.net/problem/CodeChef-DIGJUMP

基本思路

这题其实本来就是暴搜，不过纯暴搜是过不去的，需要一点点优化。

稍微读题就知道，其实这个题可以把跳的过程看成是图上行走的过程，你会发现暴力跑图复杂度不对，所以如何优化？考虑到对于权值相同的节点，如果在图上其实是两两相连的，也就是一大坨块，我们可以在心中把他们缩成一个点，然后再在图上跑。当然实际搜索的时候也不是真正的建图出来跑，只是模拟那个过程，同一个权值的一堆点只会入队一次，出队后就再也不会push进来了，所以复杂度有了保证

涉及知识点

广度优先搜索，图形转化思想，优化思想

Codechef PERMPART

https://cn.vjudge.net/problem/CodeChef-PERMPART

基本思路

这题的解法非常神奇，首先我先不说这道题，单纯讲一个更普通的问题，问题如下

给你一个长n的数组a[i]，你可以花费1块钱把一个位置+1，或者-1，问将原数组修改成单调不升序列的最小花费(n<=100000)

这个问题的题解在这里：https://blog.csdn.net/can919/article/details/79068186

你可能会想到设$dp[i][j]$ 表示做到第$i$个数，最后一个位置为$j$的时候的最小花费，然后转移为$dp[i+1][j]=min(dp[i][k])+|j-a[i]|;$

但是分析一下可以发现，这个dp的转移复杂度是不对的，即使是将后面转移用神奇方法优化到$O(1)$复杂度，你前面的枚举也是$O(n^2)$，所以这种方法是不太科学的

然后题解里面用了很大的篇幅来讲证明以及一些内部原理，其实我也不是太懂，但是我想说的就是，这个问题的最终结论，也就是固定解法：优先队列，就当作模板去记一记也未尝不可

priority_queue<int,vector<int>,greater<int> > pq;
int ans;
for(int i=1;i<=n;i++){
    pq.push(a[i]);
    if(!pq.empty() && pq.top() < a[i]){
        ans += a[i] - pq.top();
        pq.pop();
        pq.push(a[i]);
    }
}

然后回到这道题，可以发现，数字的位置与你最后求得的答案实际上是无关的，因为题目只要求你拆分出一个个的排列，不要求这些排列要连续，所以位置是可调的。有一个东西很容易想到，那就是如果题目中给出的数据中有$a[i]>2*n$了，如果是要通过添加数字的方法去构成排列，显然需要大于$n$的代价，显然将它删除更划算。

所以对于所有$a[i]>2*n$的数，我们的决策是直接删除

然后是剩下的数，我们可以将它们放在一个桶里面，记录每个数出现的次数。现在看出这道题和我之前举例的那个题的关系了吗？是的，这道题现在问题转变为让你求最小代价，使得桶中的元素单调不降，这样才满足可以从中分出若干个排列，很简单的想想就可以明白。

涉及知识点

最小代价求单调不降(升)子序列，桶计数，思维转换

ZJOI2007 仓库建设

http://ojj.kuang.cf/problem/12

https://www.luogu.org/problem/P2120

基本思路

一道斜率优化DP题，只需要大力推式子就好了，如果不会推斜率优化式子的，请看我的《斜率优化DP学习笔记》

首先我们可以设$dp[i]$表示在第$i$个工厂设立仓库，前$i$个工厂最小的花费。那么容易推出转移方程

$dp[i]=C_i + min\{dp[j]+\sum\limits_{k=j+1}^{i-1}P_k(X_i-X_k)\}(j<i)$

把括号中打开可以得

$dp[i]=C_i+min\{dp[j]+X_i\sum\limits_{k=j+1}^{i-1}P_k-\sum\limits_{k=j+1}^{i-1}P_kX_k\}$

我们发现式子中有两个求和符号，都可以用前缀和优化到$O(1)$得求和符号值

所以不妨设$F(x)=\sum\limits_{i=1}^xP_i$，$T(x)=\sum\limits_{i=1}^xP_iX_i$

原始可以化简为

$dp[i]=C_i+min\{dp[j]+X_i*(F(i-1)-F(j))-(T(i-1)-T(j))\}$

现在问题转换为要求后面一坨表达式对于所有$j<i$的最小值

暴力求解的话，对于每一个$i$计算最小值为$O(n)$，整题复杂度为$O(n^2)$，明显过不去，考虑斜率优化转移，开始推式子

设决策$k_1<k_2$，且$k_2$优于$k_1$

用式子写出来即$dp[k_1]+X[i]F[i-1]-X[i]F[k_1]-T[i-1]+T[k_1]>dp[k_2]+X[i]F[i-1]-X[i]F[k_2]-T[i-1]+T[k_2]$

左右两边约去相同项，将与 $i$ 无关项移到不等式一侧，可以得到:

$dp[k_1]-dp[k_2]+T[k_1]-T[k_2]>X[i](F[k_1]-F[k_2])$

将所有与 $i$ 无关的项放在不等式一边，注意这里我们之前假设的是$k_2>k_1$，所以这里$F[k_1]-F[k_2]<0$，除过去要变号

$\frac{dp[k_1]-dp[k_2]+T[k_1]-T[k_2]}{F[k_1]-F[k_2]}<X[i]$

注意到左侧分子部分可以抽象为一个函数

不妨令$M(x)=dp[x]+T[x]$

于是式子可以化成标准斜率式：$\frac{M(k_1)-M(k_2)}{F[k_1]-F[k_2]}<X[i]$

然后就可以斜率优化转移dp了

涉及知识点

斜率优化，前缀和

CJ190805A

http://ojj.kuang.cf/problem/16

基本思路

考虑将输入的所有牌按照花色分组，对于每一种花色，按照牌的数字大小排序并去重。原题就相当于在每种花色中找出连续一段，使得这一段(最大值-最小值+1) <= n，并且这一段长度尽量长，那么答案就是n-每一个段长度的最大值

具体实现分组可离散化，查一段可以二分或倍增

涉及知识点

二分，倍增，离散化

CJ190805B

http://ojj.kuang.cf/problem/17

基本思路

顺次枚举每一个$a[i]$，顺便把$i$之前的数维护一个$last[j]$表示在$i$之前，最后一次拥有$j$这个子集的数出现的位置

然后查询的时候就可以枚举$a[i]$的每个子集$sub$，判断$last[sub]$是否在$[i-b[i],i]$范围内，如果不在这个范围内，则这个子集贡献+1

枚举一个数的所有子集，可以用以下方法(枚举$x$的子集)

for(int sub=x;sub;sub=(sub-1)&x){
    //sub 就是枚举的子集
}

涉及知识点

枚举子集，思维

CJ190805C

http://ojj.kuang.cf/problem/18

基本思路

分析题目可以知道，如果几个大楼能够两两相互到达，即几个大楼在同一个强连通块内，那么超人如果可以救一个楼的火，就可以救这个块内其他楼的火，所以考虑$tarjan$缩点，将原图转换成$DAG$

缩点完后的新图中，每个点的点权就对应原图中联通块所有点的权值和

然后问题转换为从起点$S$开始，经过某些点过后到指定点集$P$,使得经过的点点权尽量大。

由于是$DAG$,所以有很多特殊性质可以用到，比如我们就可以把点权转换到连向他的边上，使得求点权最大变为$DAG$上求最长路问题

对于$DAG$最长路问题，有几个固定解法，各有优劣，下面列举最常用两种

SPFA

将边权设置为原边权的相反数，然后跑最短路，由于是$DAG$不存在环，所以可以放心SPFA，然后结果再取相反数就是最长路

注意的是，这个方法可能会被卡时间

拓扑排序

$DAG$上求最长路的标准做法就是拓扑排序，类似于$BFS$搜索，首先把入度为0的所有点push进队列，然后依次对队列中每个点向周围搜索，然后周围点度数-1，如果减了后度数为0了，就再push进队列里面继续搜索。

最后可以求出$DAG$上的最长路

涉及知识点

$tarjan$缩点，$DAG上最长路$

BZOJ1303

https://cn.vjudge.net/problem/HYSBZ-1303

基本思路

分三种情况，一种是以b所在位置为开头，往后拓展，长度为奇数且以b为中位数的；一种是以b所在位置为结尾，往前拓展，长度为奇数且以b为中位数的；一种是将b包含在中间，以b为中位数的

我们把整个序列重新赋值一下，大于b的数赋值为1，小于b的数赋值为-1，b本身赋值为0。前两种情况就很好处理了，直接从b开始向前向后扫一遍就行了，加到0就说明当前序列合法。现在考虑将b包含在中间的情况，也就是b前选一段，b后选一段，使得两段和加起来为0，这个只需要在之前扫描的时候用桶记录一边出现的可能的和的个数，由于可能出现负数，可以用map存或者全部加上一个数使得其为正数，然后再扫另外一边的时候检查有没有在桶里有出现当前和的相反数，如果出现了，那么必然相加为0，是合法情况，所以答案加上桶中的个数

涉及知识点

思维，map

BZOJ2783

https://cn.vjudge.net/problem/HYSBZ-2783

基本思路

这道题问题是：给定一棵树，和一个值$S$，每个节点有一个权值，问你整棵树有多少条路径覆盖的节点权值总和刚好为$S$

实际上换个角度考虑，这个问题变为：对于每个节点，是否能够在该节点祖先地方找到一个节点，使得他们之间（包括自身）的权值加起来为$S$。凡是与祖先有关的问题，首先就可以思考一下倍增，这道题倍增的确是可以做的。首先找到树的根，读入时维护每个节点入度，入度为0即为根，然后以这个根开始dfs，维护每个节点（包括自身）到根节点路径上点权值和，然后维护倍增数组，对于每个点，就往上跳，找到路径点权和小于等于S的最浅节点，如果能找到这个节点，答案+1就可以了

涉及知识点

倍增，思维转换

BZOJ3631

https://cn.vjudge.net/problem/HYSBZ-3631

基本思路

这个题的题意就是维护一棵树的点权，最初都是0，然后有一种操作，那就是$modify(x,y)$，表示将$x,y$简单路径上每个点权都+1，多次操作，问你最终每个点的点权

像这种树上区间修改的问题，我们有两种做法，一种是树链剖分后建线段树维护，这种方法优势在于支持操作比较多，线段树支持的操作它都支持，缺点是很难写，而且常数大。另一种方法是树上差分，差分需要求LCA，所以需要用倍增或者树剖求LCA。

这里因为只涉及区间加操作，所以果断树上差分，差分过程是这样的。

假设要修改$x,y$路径上的点权，全部加上$w$，设$c = lca(x,y),fc=fa[c]$

只需要$dt[x]+=w,dt[y]+=w,dt[c]-=w,dt[fc]-=w$

然后求最终的数组的时候，这样dfs一遍就求出来了

void dfs3(int u){
    for(int i=p[u];~i;i=E[i].nxt){
        int v = E[i].v;
        if(v == fa[u]) continue;
        dfs3(v);
        dt[u] += dt[v]; 
    }
}

涉及知识点

倍增，树链剖分，树上差分

P1083 借教室

https://www.luogu.org/problem/P1083

基本思路

转换一下问题，这道题实际上就是给定一个数组，你需要实现一下操作：区间查询最小值，区间加上一个数（这道题实际上是区间加上负数），所以直接一个带lazy标记的线段树就可以实现了，具体看标程

涉及知识点

线段树+lazy标记

P2161 [SHOI2009]会场预约

https://www.luogu.org/problem/P2161

基本思路

题目大意：不断加线段，每次将线段覆盖的其他线段删除（没覆盖完也要删除），并问你每次删除线段条数或者剩余线段总数

要实现这道题需要的操作，实际上就是在加入一条线段的时候，计算有多少线段被删除了。线段被删除的条件是要么完全被新加入的线段覆盖，要么是新加入的线段的左右端点在这个欲删除线段内。于是我们可以开一个数组，对于每一条线段，我们给予他一个ID，然后在数组中它对应区间的值全部设置为这个ID

然后问题转换成，区间更新，区间查询不同ID的个数是多少，这个可以用线段树来做，只不过合并过程要判断一下，线段树每一个节点需要维护：lv该区间最左边的值是多少，rv该区间最右边的值是多少，cnt这个区间包含多少ID不同的区间。合并区间$a,b$的时候，结果的$res.cnt=a.cnt+b.cnt$，但是如果$a.rv==b.lv$，那么实际上合并过后中间是一段，所以还要$res.cnt--$

这题很多细节问题，需要自己手写线段树感受，debug我de了很久...

涉及知识点

线段树+lazy标记，自定义线段树区间合并，题意转换

P1880 [NOI1995]石子合并

https://www.luogu.org/problem/P1880

基本思路

基本题意：一个环，相邻两堆石子可以合并到一起，每次花费石子个数和这么多体力，求最小体力和最大体力将所有石子合成一堆

以前是用小根堆贪心做的，后来发现好像有问题。所以这次试试区间dp的做法，毕竟区间dp也是dp中很重要的知识点

对于区间dp的问题，通常我们的状态都很单一，就是$dp[i][j]$表示区间i~j的xxx答案，最多也就在后面添个几维附加状态，也很好想。如果你看到$n$范围特别小，而且是关于区间的问题的时候，你就要往区间dp方向去想了。

这道题，典型的区间dp问题，设$mindp[i][j]$表示合并区间i~j的范围内的石子，最小花费,$maxdp[i][j]$同理。由于这是环，所以我们化环为链，把数组复制一遍接在原数组后面，这样就可以在链上dp啦。

转移方程就是$mindp[i][j]=mindp[i][k] + mindp[k+1][j] + prea[j] - prea[i-1]$，其中k为我们枚举的i~j区间内的一个中间点，$prea[]$表示复制完的数组的前缀和。由此可以看出套路，区间dp的进行实际上就是小区间不断合并或者拓展成大区间的过程，至于区间dp代码的实现，可以参考标程。

涉及知识点

区间dp

计蒜客-银河战舰

https://www.jisuanke.com/course/940/253772（访问不通就看题目描述）

题目背景

瑞奥和玛德利德是非常好的朋友。瑞奥平时的爱好是吹牛，玛德利德的爱好是戳穿瑞奥吹的牛。
这天瑞奥和玛德利德来到了宇宙空间站，瑞奥向玛德利德炫耀这个空间站里所有的银河战舰都是自
己的。整个空间站可以看成一个无限大的二维平面，每个战舰都可以看做一个点，在空间站中一共
分布着 艘银河战舰。
玛德利德：“你说这些都是你的，那你让他们动一动啊”。
瑞奥：“诶你看,那艘动了！”。
玛德利德：“操作指令由我来发，一共有 5 种动的方法......”。
瑞奥：“我觉得这样有失公正......”。

题目描述

第一行一个正整数$N$，表示战舰的数量

接下来$N$行，每行两个实数，代表第$i$个战舰的$x,y$坐标

然后一个正整数$M$，代表调度的次数

接下来$M$行操作，每个操作都是如下类型的一种：

$M\ l\ r\ p\ q$：把编号在$[l,r]$区间内的战舰$x$坐标加上$p$,$y$坐标加上

$q$
$X\ l\ r$：把编号在$[l,r]$区间内的战舰沿$x$轴翻转

$Y\ l\ r$：把编号在$[l,r]$区间内的战舰沿$y$轴翻转

$O\ l\ r$：把编号在$[l,r]$区间内的战舰沿直线$y=x$翻转

$R\ l\ r\ a$：把编号在$[l,r]$区间内的战舰绕原点逆时针旋转$a°$

注意，$p,q,a$均可能为小数

输出格式

输出包括$N$行，代表着$N$艘战舰经过$M$次调度之后的坐标(保留两位小数)

样例输入

3
1 2
-2 2.5
0 -3
3
X 1 3
M 1 3 3 6
R 1 3 90

样例输出

-4.00 4.00
-3.50 1.00
-9.00 3.00

基本思路

这里涉及到维护区间内战舰的二维坐标信息，但是可以发现，一般的线段树是不能实现这样复杂的区间内让某一个坐标取相反数，或者是交换两个坐标，或者是旋转坐标，如果可以，纯线段树的方法未免也太复杂了一点。

对于这样的空间几何问题，可以考虑考虑矩阵乘法。因为矩阵乘法的本质就是空间内图形变换的过程，所以这道题可以转换为线段树区间乘法，然后最后查询每一位置的结果。只不过这里线段树的区间乘法是乘上的一个矩阵。

由于矩阵拥有结合律，即 $A * B * C*...*Z=A*(B*C*...*Z)$，所以我们只要用线段树维护好所有请求后，最终每个位置的矩阵结果(即这里的$B*C*...Z$)，再用输入坐标(即这里的$A$)乘上结果矩阵就是最终答案了(即$A*B*C*...*Z$)。

下面考虑如何构造变换矩阵，首先是状态矩阵，表示某个编号战舰的状态的矩阵，即包含该战舰的坐标，具体分析操作可以知道，$M$操作是将坐标分别加上$p,q$，由于涉及到常数操作，所以我们需要在矩阵中放入一个常数$1$来实现常数的增加操作，于是构造出的状态矩阵是这样子：$\begin{bmatrix} x & y & 1\end{bmatrix}$

表示当前它的坐标是$(x,y)$，后面那个$1$正如上文所说，是用来常数操作使用的

下面来看各种操作的转移矩阵，具体推导过程不作详细叙述，只有最后一个旋转需要详细说一下。

1.操作$M$，参数$p,q$，转移矩阵为：

$\begin{bmatrix}x&y&1\end{bmatrix}*\begin{bmatrix}1&0&0\\0&1&0\\p&q&1\end{bmatrix}=\begin{bmatrix}x+p&y+q&1\end{bmatrix}$

2.操作$X$，参数无，转移矩阵为：

$\begin{bmatrix}x&y&1\end{bmatrix}*\begin{bmatrix}1&0&0\\0&-1&0\\0&0&1\end{bmatrix}=\begin{bmatrix}x&-y&1\end{bmatrix}$

3.操作$Y$，参数无，转移矩阵为：

$\begin{bmatrix}x&y&1\end{bmatrix}*\begin{bmatrix}-1&0&0\\0&1&0\\0&0&1\end{bmatrix}=\begin{bmatrix}-x&y&1\end{bmatrix}$

4.操作$O$，参数无，转移矩阵为：

$\begin{bmatrix}x&y&1\end{bmatrix}*\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}=\begin{bmatrix}y&x&1\end{bmatrix}$

5.操作$R$，参数$a$，转移矩阵为：

需要特别注意这里题目中$a$给的是角度，单位为度，而c++的math函数库中的一系列三角函数比如$cos,sin,acos$等传入的参数都是弧度，单位是RAD，所以需要将输入的$a$进行转换，具体公式是：$π\ rad = 180°$，所以读入的$a=a/180*π$

还有需要补充一个旋转公式，那就是对于一个点$(x,y)$，绕原点逆时针旋转$a$的角度后过后，新的点坐标为$(x\ cosa-y\ sina,x\ sina+y\ cosa)$

所以转移矩阵就很明了了：

$\begin{bmatrix}x&y&1\end{bmatrix}*\begin{bmatrix}cosa&sina&0\\-sina&cosa&0\\0&0&1\end{bmatrix}=\begin{bmatrix}xcosa-ysina&xsina+ycosa&1\end{bmatrix}$

然后得到这些矩阵的推导，我们就可以用线段树区间乘单点查放心做了，由于矩阵乘法的结合律，所以可以证明做法没有问题。注意一下最后需要把所有的$lazy$标记全部$pushdown$下去

具体可看标程做法

涉及知识点

简单平面几何，矩阵乘法，线段树区间乘单点查

P3294 [SCOI2016]背单词

https://www.luogu.org/problem/P3294

基本思路

贪心+trie树

考虑情况1，消耗过于巨大，所以肯定不能让情况1出现。

所以考虑每个单词倒着建立trie树，维护每个单词的终端节点位置。这样一个当一个单词为另一个单词的后缀时，这个后缀在trie树上的终端结点一定是长串在trie树上终端节点的祖先。

建立完trie树后，问题转换为在trie树上对于每个终端节点，分别编号，使得每个结点的编号减去其父亲结点编号的和最小，这里的父亲节点需要特别说明，并不是trie树节点上的父亲，而是指在这个节点的所有祖先中，距离它最近的一个终端节点。

于是对于所有终端节点，可以重新建立一棵只含终端节点的新树，而维持原trie树上的父子关系。贪心的想，为了达到最小和，肯定优先走size较小的子树更优。所以我们可以建完新树过后，维护每个节点儿子子树的size，然后优先走size较小的儿子，并编号计算答案。

实现方面，建立新树如何寻找一个节点的父亲(含义同上)，可以dfs原trie树时用一个栈记录上一个访问的终端节点。如何存储新树中每个节点的儿子还要从小到大访问，这个可以每次手动sort或者全局使用priority_queue，具体实现参考标程，使用的是priority_queue.

涉及知识点

贪心，字典树(trie tree)，深度优先搜索，栈

题目标程

CJ190725A

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn = 2*100010;
const int maxm = maxn;
struct edge{
 int v,nxt,w;
}E[maxm*2];
int p[maxn],eid;
void init(){
 memset(p,-1,sizeof p);
 eid = 0;
}
void insert(int u,int v,int w){
 E[eid].v = v;
 E[eid].w = w;
 E[eid].nxt = p[u];
 p[u] = eid++;
}
void insert2(int u,int v,int w){
 insert(u,v,w);
 insert(v,u,w);
}
int w[maxn];
int depw[maxn],anc[maxn][25],dep[maxn];
int dt[maxn];
int n;
void dfs(int u){
 //cout << "dep:" << dep[u] << endl;
 for(int i=p[u];~i;i=E[i].nxt){
     int v = E[i].v;
     int w = E[i].w;
     if(v == anc[u][0]) continue;
     anc[v][0] = u;
     depw[v] = depw[u] + w;
     dep[v] = dep[u] + 1;
     dfs(v);
 }
}
void getanc(){
 for(int i=1;(1 << i) <= n;i++){
     for(int j=1;j<=n;j++){
         anc[j][i] = anc[anc[j][i-1]][i-1];
     }
 }
}
void modify(int x,int y,int w){
 //dt
 if(dep[x] > dep[y]) swap(x,y);
 dt[anc[x][0]] -= w;
 dt[y] += w;
}
void solve(int u){
 int now = u;
 for(int i=21;i>=0;i--){
     int aanc = anc[now][i];
     if(aanc == 0) continue;
     if(depw[u] - depw[aanc] <= w[u]) now = aanc;
 }
 modify(now,u,1);
}
void calctree(int u){
 for(int i=p[u];~i;i=E[i].nxt){
     int v = E[i].v;
     if(v == anc[u][0]) continue;
     calctree(v);
     dt[u] += dt[v];
 }
}
signed main(){
 //freopen("A3.in","r",stdin);
 init();
 scanf("%lld",&n);
 for(int i=1;i<=n;i++) scanf("%lld",w+i);
 for(int i=2;i<=n;i++){
     int v,w;
     scanf("%lld%lld",&v,&w);
     insert2(i,v,w);
 }
 dep[1] = 1;
 dfs(1);
 getanc();
 for(int i=1;i<=n;i++) solve(i);
 calctree(1);
 for(int i=1;i<=n;i++){
     if(i == 1) printf("%lld",dt[i]-1);
     else printf(" %lld",dt[i]-1);
 }
 return 0;
} 

CJ190725B

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2*1000010;
int n;
struct RandSpace{
 long long seed;
 long long Rand() {
     return seed = ((seed*19260817) ^ 233333) & ((1<<24)-1);
 }
 void gen(int *A){
     for(register int i = 1; i <= n; i++) A[i] = i;
     for(register int i = 1; i <= n; i++) swap(A[i], A[Rand()%i + 1]);
 }
}rs[3];
struct Person{
 int a,b,c;
}pp[maxn],qq[maxn];
int qqpos = 0;
int tmpa[maxn];
inline bool strongCmp(const Person &a,const Person &b){
 return (a.a < b.a) && (a.b < b.b) && (a.c < b.c);
}
ll ans = 0;
namespace solve30{
 //暴力
 void solve(){
     ans = 0;
     for(int i=1;i<=n;i++){
         for(int j=i+1;j<=n;j++){
             if(strongCmp(pp[i],pp[j]) || strongCmp(pp[j],pp[i])) ans++;
         }
     }
     printf("%lld\n",ans);
 }
}
namespace solve70{
 //CDQ分治三维偏序
 int C[maxn];
 int lowbit(int x){
     return x & -x;
 }
 void update(int pos,int v){
     for(int i=pos;i<=n;i+=lowbit(i)){
         C[i] += v;
     }
 }
 int query(int pos){
     int ret = 0;
     for(int i=pos;i>0;i-=lowbit(i)){
         ret += C[i];
     }
     return ret;
 }
 inline bool cmp(const Person &a,const Person &b){
     return a.a < b.a;
 }
 int ans = 0;
 void CDQ_sort(int l,int r){
     if(l == r) return;
     int mid = (l + r) >> 1;
     
     CDQ_sort(l,mid);
     CDQ_sort(mid+1,r);
     qqpos = 0;
     int p1=l,p2=mid+1;
     while(p1 <= mid || p2 <= r){
         if(p1 <= mid && (pp[p1].b < pp[p2].b || p2 > r)){
             qq[++qqpos] = pp[p1];
             update(pp[p1].c,1);
             ++p1;
         }else{
             qq[++qqpos] = pp[p2];
             ans += query(pp[p2].c-1);
             ++p2;
         }
     }
     for(int i=l;i<=mid;i++) update(pp[i].c,-1);
     for(int i=1;i<=qqpos;i++){
         pp[l+i-1] = qq[i];
     }
 }
 void solve(){
     sort(pp+1,pp+1+n,cmp);
     ans = 0;
     CDQ_sort(1,n);
     printf("%d\n",ans);
 }
}
namespace solve100{
 //正解 容斥
 //S(i,j) = (pp[i].a > pp[j].a) + (pp[i].b > pp[j].b) + (pp[i].c > pp[j].c)
 //M(i,j) = max{S(i,j) , S(j,i)}
 //a: cnt whose [M(i,j) = 2]
 //b: cnt whose [M(i,j) = 3]
 //a + b = n * (n - 1) / 2;
 //令 TT 为两两逆序对组数，即 (pp[i].a > pp[j].a && pp[i].b > pp[j].b) + (pp[i].a > pp[j].a && pp[i].c > pp[j].c) + (pp[i].c > pp[j].c && pp[i].b > pp[j].b)
 //TT = 3*b + a
 //TT - n * (n-1) / 2 = 2*b --> b = TT / 2 - n * (n-1) / 4
 long long ans = 0;
 long long TT = 0;
 int C[maxn];
 int lowbit(int x){
     return x & -x;
 }
 void update(int pos,int v){
     for(int i=pos;i<=n;i+=lowbit(i)){
         C[i] += v;
     }
 }
 int query(int pos){
     int ret = 0;
     for(int i=pos;i>0;i-=lowbit(i)){
         ret += C[i];
     }
     return ret;
 }
 inline bool cmp1(const Person &a,const Person &b){
     return a.a < b.a;
 }
 inline bool cmp2(const Person &a,const Person &b){
     return a.b < b.b;
 }
 void solve(){
     //a,b 逆序对
     sort(pp+1,pp+1+n,cmp1);
     for(int i=1;i<=n;i++){
         if(i == 1){
             update(pp[i].b,1);
             continue;
         }
         TT += query(pp[i].b-1);
         update(pp[i].b,1);
     }
     //a,c 逆序对
     memset(C,0,sizeof C);
     sort(pp+1,pp+1+n,cmp1);
     for(int i=1;i<=n;i++){
         if(i == 1){
             update(pp[i].c,1);
             continue;
         }
         TT += query(pp[i].c-1);
         update(pp[i].c,1);
     }
     //b,c 逆序对
     memset(C,0,sizeof C);
     sort(pp+1,pp+1+n,cmp2);
     for(int i=1;i<=n;i++){
         if(i == 1){
             update(pp[i].c,1);
             continue;
         }
         TT += query(pp[i].c-1);
         update(pp[i].c,1);
     }
     //cout << "TT:" << TT << endl;
     //cout << "ans:" << TT / 2 - n * (n-1) / 4 << endl;
     printf("%lld\n",TT / 2 - 1ll * n * (n-1) / 4);
 }
}
int main(){
 scanf("%d",&n);
 for(register int i=0;i<3;i++){
     scanf("%lld",&rs[i].seed);
 }
 rs[0].gen(tmpa);
 for(register int i=1;i<=n;i++) pp[i].a = tmpa[i];
 rs[1].gen(tmpa);
 for(register int i=1;i<=n;i++) pp[i].b = tmpa[i];
 rs[2].gen(tmpa);
 for(register int i=1;i<=n;i++) pp[i].c = tmpa[i];
 if(n <= 5000) solve30::solve();
 else if(n <= 100010) solve70::solve();
 else solve100::solve();
 return 0;
}

CJ190725C

#include <bits/stdc++.h>
using namespace std;
int n,h;
struct node {
 int a,b;
}W[4010];
bool cmp(node x,node y){
 return x.a+x.b<y.a+y.b;
}
int dp[4010];
int main () {
 scanf("%d",&n);
 memset(dp,-1,sizeof(dp));
 dp[0] = 0;
 for (register int i = 1; i <= n; i++){
     scanf("%d%d",&W[i].a,&W[i].b);
     dp[0] += W[i].a;
 }
 scanf("%d",&h);
 sort(W+1,W+n+1,cmp);
 for (register int i = 1; i <= n; i++){
     for (register int j = i; j >= 1; j--){
         if (dp[j-1]+W[i].b>=h){
             dp[j] = max(dp[j],dp[j-1]-W[i].a);
         }
     }
 }
 for (register int i = n; i >= 0; i--){
     if (dp[i]>=0){
         printf("%d",i);
         return 0;
     }
 }
 return 0;
}

CJ190723A

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int maxm = 2 * 100010;
struct edge{
  int u,v,w;
}E2[maxm * 2];
int e2id;
int n,m,X;
inline bool cmp(const edge &a,const edge &b){
  return a.w < b.w;
}
int fa[maxn],size[maxn];
void initfa(){
  for(int i=0;i<=n;i++) fa[i] = i,size[i] = 1;
}
int get(int x){
  if(fa[x] == x) return x;
  return fa[x] = get(fa[x]);
}
long long ans = 0;
void merge(int x,int y,int isadd){
  int fx = get(x),fy = get(y);
  if(fx == fy) return;
  fa[fx] = fy;
  ans += size[fy] * size[fx] * isadd;
  size[fy] += size[fx];
}
int main(){
  scanf("%d%d%d",&n,&m,&X);
  initfa();
  for(int i=1;i<=m;i++){
      int u,v,w;
      scanf("%d%d%d",&u,&v,&w);
      if(w > X) continue;
      E2[i].u = u;
      E2[i].v = v;
      E2[i].w = w;
      if(w < X) {
          merge(u,v,0);
      }
  }
  for(int i=1;i<=m;i++){
      if(E2[i].w == X){
          merge(E2[i].u,E2[i].v,1);
      }
  }
  printf("%lld\n",ans);
  return 0;
} 

CJ190723B

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
const int maxm = 2 * 200010;
int n,q;
struct edge{
  int v,nxt;
}E[maxm * 2];
int p[maxn],eid;
void init(){
  memset(p,-1,sizeof p);
  eid = 0;
}
void insert(int u,int v){
  E[eid].v = v;
  E[eid].nxt = p[u];
  p[u] = eid++;
}
void insert2(int u,int v){
  insert(u,v);
  insert(v,u);
}
int size[maxn],fa[maxn],hson[maxn],dep[maxn],anc[maxn][25];
void dfs1(int u){
  //printf("u:%d\n",u);
  size[u] = 1;
  int msize = 0;
  for(int i=p[u];~i;i=E[i].nxt){
      int v = E[i].v;
      if(fa[u] == v) continue;
      dep[v] = dep[u] + 1;
      fa[v] = u;
      anc[v][0] = u;
      dfs1(v);
      size[u] += size[v];
      if(size[v] > msize){
          msize = size[v];
          hson[u] = v;
      }
  }
}
int top[maxn];
void dfs2(int u,int tp){
  top[u] = tp;
  if(hson[u]){
      dfs2(hson[u],tp);
  }
  for(int i=p[u];~i;i=E[i].nxt){
      int v = E[i].v;
      if(v == fa[u] || v == hson[u]) continue;
      dfs2(v,v); 
  }
}
int lca(int x,int y){
  while(top[x] != top[y]){
      if(dep[top[x]] < dep[top[y]]) swap(x,y);
      x = fa[top[x]];
  }
  return dep[x] > dep[y] ? y : x;
}
void getanc(){
  for(int i=1;(1 << i) <= n;i++){
      for(int j=1;j<=n;j++){
          anc[j][i] = anc[anc[j][i-1]][i-1];
      }
  }
}
int solve(int x,int y){
  int tlca = lca(x,y);
  if(tlca != x && tlca != y){
      return size[x] + size[y];
  }else{
      if(dep[x] > dep[y]) swap(x,y);
      int now = y;
      for(int i=20;i>=0;i--){
          if(dep[anc[now][i]] > dep[x]) now = anc[now][i];
      }
      return size[y] + n - size[now];
  }
}
int main(){
  init();
  scanf("%d%d",&n,&q);
  for(int i=1;i<=n-1;i++){
      int u,v;
      scanf("%d%d",&u,&v);
      insert2(u,v);
  }
  dep[1] = 1;
  dfs1(1);
  dfs2(1,1);
  getanc();
  for(int i=1;i<=q;i++){
      int u,v;
      scanf("%d%d",&u,&v);
      printf("%d\n",solve(u,v));
  }
  return 0;
}

CJ190723C

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3010,maxm = 4010;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct edge{
 int v,w,nxt;
}E[maxm*2];
int p[maxn],eid;
void init(){
 memset(p,-1,sizeof p);
 eid = 0;
}
void insert(int u,int v,int w){
 E[eid].v = v;
 E[eid].w = w;
 E[eid].nxt = p[u];
 p[u] = eid++;
}
int n,m;
bool vis[maxn];
int dist[maxn][maxn];
void BFS(int u){
 memset(vis,false,sizeof(vis));
 queue<int> q;
 q.push(u);
 dist[u][u] = 0;
 vis[u] = true;
 while(!q.empty()){
     int now = q.front();
     q.pop();
     for (int i=p[now];~i;i=E[i].nxt){
         int v = E[i].v;
         if (!vis[v]){
             dist[u][v] = dist[u][now]+1;
             vis[v] = true;
             q.push(v);
         }
     }
 }
}
int s1,t1,l1,s2,t2,l2;
int ans = 0;
int solve(int x,int y){
 int res = 0x3f3f3f3f;
 if (dist[x][y]+dist[x][s1]+dist[y][t1]<=l1&&dist[x][y]+dist[x][s2]+dist[y][t2]<=l2){
     res = dist[x][y]+dist[x][s1]+dist[x][s2]+dist[y][t1]+dist[y][t2];
 }
 if (dist[x][y]+dist[x][s1]+dist[y][t1]<=l1&&dist[x][y]+dist[x][t2]+dist[y][s2]<=l2){
     res = min(res,dist[x][y]+dist[x][s1]+dist[x][t2]+dist[y][s2]+dist[y][t1]);
 }
 return res;
}
int main(){
 //freopen("buff.in","r",stdin);
 //freopen("buff.out","w",stdout);
 memset(dist,0x3f,sizeof dist);
 init();
 scanf("%d%d",&n,&m);
 for(int i=1;i<=m;i++){
     int u,v;
     scanf("%d%d",&u,&v);
     insert(u,v,1);
     insert(v,u,1);
 }
 scanf("%d%d%d%d%d%d",&s1,&t1,&l1,&s2,&t2,&l2);
 for(int i=1;i<=n;i++) BFS(i);
 if(dist[s1][t1] > l1 || dist[s2][t2] > l2){
     printf("That's all trouble!\n");
     return 0;
 }
 ans = max(ans,m-dist[s1][t1]-dist[s2][t2]);
 for(int i=1;i<=n;i++){
     for(int j=1;j<=n;j++){
         ans = max(ans,m-solve(i,j));
     }
 }
 printf("%d\n",ans);
 return 0;
}

CJ190723D

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 100;
int n,m;
struct Ufs{
 int fa[maxn],size[maxn];
 void initfa(){
     for(int i=1;i<=n;i++) fa[i] = i,size[i] = 1;
 }
 int get(int x){
     while(fa[x] != x) x = fa[x];
     return x;
 }
 int org_fa_s[maxn],fx_s[maxn],psta=0;
 bool merge(int x,int y){
     //printf("merge:%d %d\n",x,y);
     int fx = get(x),fy = get(y);
     if(fx == fy) {
         psta++;
         org_fa_s[psta] = fx_s[psta] = -1;
         return false;
     }
     if(size[fx] > size[fy]) swap(fx,fy);
     size[fy] += size[fx];
     fx_s[++psta] = fx;
     org_fa_s[psta] = fa[fx];
     fa[fx] = fy;
     return true;
 }
 bool undo(){
     if(psta <= 0) return false;
     int fx = fx_s[psta];
     int org_fa = org_fa_s[psta--];
     if(fx == -1 && org_fa == -1) return false;
     int fy = fa[fx];
     size[fy] -= size[fx];
     fa[fx] = org_fa;
     return true;
 }
}ufs;
int ans[maxn],pans=0,ew[maxn],pew=0;
int nowcnt = 0,nowans = 0;
struct CMD{
 char cmd;
 int p1,p2;
}cmds[(int)5e5+100];
int main(){
 scanf("%d%d",&n,&m);
 ufs.initfa();
 for(int i=1;i<=m;i++){
     char cmd[10];
     scanf("%s",cmd);
     if(cmd[0] == 'A'){
         cmds[i].cmd = 'A';
         scanf("%d%d",&cmds[i].p1,&cmds[i].p2);
     }else if(cmd[0] == 'D'){
         cmds[i].cmd = 'D';
         scanf("%d",&cmds[i].p1);
     }else if(cmd[0] == 'R'){
         cmds[i].cmd = 'R';
     }
 }
 for(int i=1;i<=m;i++){
     if(cmds[i].cmd == 'A'){
         if(ufs.merge(cmds[i].p1,cmds[i].p2)){
             nowans += i;
             nowcnt++;
             ew[++pew] = i;
         }
         if(nowcnt == n-1){
             printf("%d\n",nowans);
             ans[++pans] = nowans;
         }else{
             printf("0\n");
             ans[++pans] = 0;
         }
     }else if(cmds[i].cmd == 'D'){
         //printf("act:delete>>>\n");
         int k = cmds[i].p1;
         if(i+1<=m && cmds[i+1].cmd == 'R'){
             //printf("delete>>>return:pans:%d k:%d\n",pans,k);
             printf("%d\n",ans[pans-k]);
             continue;
         }else{
             for(int j=1;j<=k;j++){
                 if(ufs.undo()){
                     nowcnt--;
                     nowans -= ew[pew--];
                     pans--;
                 }
             }
             if(nowcnt == n-1){
                 printf("%d\n",nowans);
             }else{
                 printf("0\n");
             }
         }
     }else{
         if(cmds[i-1].cmd == 'A'){
             if(ufs.undo()){
                 nowcnt--;
                 nowans -= ew[pew--];
             }
             if(nowcnt == n-1){
                 printf("%d\n",nowans);
             }else{
                 printf("0\n");
             }
         }else{
             if(nowcnt == n-1) printf("%d\n",nowans);
             else printf("0\n");
         }
     }
 }
 return 0;
}

CJ190726A

#include <bits/stdc++.h>
using namespace std;
int t;
int n,q;
const int maxn = 25;
int a[maxn];
const int mod = 998244353;
namespace solve50{
 inline int hcnt(int num){
     register int ret = 0;
     while(num){
         ret += (num & 1);
         num >>= 1;
     }
     return ret;
 }
 int totans = 0;
 void solve(int id,int s,int t){
     int curans = 0x3f3f3f3f;
     int baks = s;
     for(int i=0;i<(1<<n);i++){
         //printf("i=%d\n",i);
         int xorsum = 0;
         int choicecnt = 0;
         for(int j=0;j<n;j++){
             if(i & (1 << j)){
                 xorsum ^= a[j+1];
                 //printf(">> xorsum ^= %d\n",a[j+1]);
                 choicecnt++;
             }
         }
         //printf(">>pres:%d\n",s);
         //printf(">>s=%d ^ %d\n",s,xorsum);
         s = s ^ xorsum;
         //printf(">>xorsum:%d s:%d\n",xorsum,s);
         curans = min(curans,choicecnt + hcnt(t ^ s));
         s = baks;
     }
     //printf("id:%d ans=%d\n",id,curans);
     if(curans != 0x3f3f3f3f) totans += curans * id;
     totans %= mod;
 }
 void init(){
     totans = 0;
 }
 void out(){
     printf("%d\n",totans);
 }
}
namespace solveDP{
 inline int hcnt(int num){
     register int ret = 0;
     while(num){
         ret += (num & 1);
         num >>= 1;
     }
     return ret;
 }
 long long ans = 0;
 const int range = (1 << 18) + 1;
 int dp[range];
 void init(){
     ans = 0;
     memset(dp,0x3f,sizeof dp);
     queue<int> q;
     for(int i=1;i<=n;i++){
         dp[a[i]] = 1;
         q.push(a[i]);
     }
     while(!q.empty()){
         int now = q.front();
         q.pop();
         for(int i=1;i<=n;i++){
             if(dp[now] + 1 < dp[now ^ a[i]]){
                 dp[now ^ a[i]] = dp[now] + 1;
                 if((now ^ a[i] < range)) q.push(now ^ a[i]);
             }
         }
         for(int bit=0;bit<=17;bit++){
             if(dp[now] + 1 < dp[now ^ (1 << bit)]){
                 dp[now ^ (1 << bit)] = dp[now] + 1;
                 if((now ^ (1 << bit)) < range) q.push(now ^ (1 << bit));
             }
         }
     }
 }
 void solve(int i,int s,int t){
     ans += 1ll * i * min(hcnt(s ^ t),dp[s ^ t]) % mod;
     //printf("id=%d ans:%d\n",i,min(hcnt(s ^ t),dp[s ^ t]));
     ans %= mod;
 }
 void out(){
     printf("%lld\n",ans);
 } 
}
int main(){
 //freopen("a.in","r",stdin);
 //freopen("a.out","w",stdout);
 scanf("%d",&t);
 while(t--){
     scanf("%d%d",&n,&q);
     for(int i=1;i<=n;i++) scanf("%d",a+i);
     if(n <= 3) solve50::init();
     else solveDP::init();
     for(int i=1;i<=q;i++){
         int s,t;
         scanf("%d%d",&s,&t);
         if(n <= 3) solve50::solve(i,s,t);
         else solveDP::solve(i,s,t);
     }
     if(n <= 3) solve50::out();
     else solveDP::out();
 }
 return 0;
}

CJ190726B

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
int len,tmp[26];
char mp[500010];
int pos[500010][26];
int dp[500010];
void dfs(int u,int len){
 if (len==1){
     for (register int i = 0; i < 26; i++){
         if (pos[u][i]==1e9){
             printf("%c",(char)('a'+i));
             return;
         }
     }
 }
 for (register int i = 0; i < 26; i++){
     if (dp[pos[u][i]]==len){
         printf("%c",(char)('a'+i));
         dfs(pos[u][i],len-1);
         break;
     }
 }
}
int main () {
 scanf("%s",mp+1);
 len = strlen(mp+1);
 for (register int i = 0; i < 26; i++)tmp[i] = 1e9;
 for (register int i = len; i >= 1; i--){
     memcpy(pos[i],tmp,sizeof(pos[i]));
     tmp[mp[i]-'a'] = min(tmp[mp[i]-'a'],i);
 }
 memcpy(pos[0],tmp,sizeof(pos[0]));
 for (register int i = len; i >= 1; i--){
     dp[i] = 1e9;
     for (register int j = 0; j < 26; j++){
         if (pos[i][j]!=1e9){
             dp[i] = min(dp[pos[i][j]]+1,dp[i]);
         }else {
             dp[i] = 2;
         }
     }
 }
 for (register int i = 0; i < 26; i++){
     if (pos[0][i]==1e9){
         printf("%c",(char)('a'+i));
         return 0;
     }
 }
 int ans = 1e9;
 for (register int i = 0; i < 26; i++){
     ans = min(ans,dp[tmp[i]]);
 }
 dfs(0,ans);
 return 0;
}

CJ190726C

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 10;
int n,m;
const int mod = 1e9 + 7;
int phi[maxn],prime[maxn];
int cnt = 0;
bool vis[maxn];
void initPhi(){
 phi[1] = 1;
 vis[1] = true;
 for(int i=2;i<maxn;i++){
     if(!vis[i]){
         prime[++cnt] = i;
         phi[i] = i-1;
     }
     for(int j=1;j<=cnt;j++){
         if(i * prime[j] >= maxn) break;
         vis[i * prime[j]] = true;
         if(i % prime[j] == 0){
             phi[i * prime[j]] = phi[i] * prime[j];
             break;
         }else{
             phi[i * prime[j]] = phi[i] * phi[prime[j]];
         }
     }
 }
}
ll sum1 = 0,sum2 = 0,sum3 = 0;
ll inv2 = 500000004,inv6 = 166666668;
ll C(int _n,int _m){
 return 1ull * _n * (_n - 1) % mod * (_n - 2) % mod * inv6 % mod;
}
void calcSum3(){
 sum3 = (1ull * n * C(m,3) % mod + 1ull * m * C(n,3) % mod) % mod;
}
signed main(){
 //freopen("c.in","r",stdin);
 //freopen("c.out","w",stdout);
 scanf("%d%d",&n,&m);
 initPhi();
 /*
 for(int i=1;i<=100;i++){
     printf("phi[%d]=%lld\n",i,phi[i]);
 }
 */
 calcSum3();
 int lim = min(n-1,m-1);
 for(int d=1;d<=lim;d++){
     int t1 = (m-1) / d;
     ll s1 = 1ull * (m - d + m - 1ull * t1 * d) * t1 % mod * inv2 % mod;
     int t2 = (n-1) / d;
     ll s2 = 1ull * (n - d + n - 1ull * t2 * d) * t2 % mod * inv2 % mod;
     sum1 += 1ull * s1 * s2 % mod * phi[d] % mod;
     sum1 %= mod;
     //printf("res[d=%lld]=%lld\n",d,sum1);
 }
 int t1 = m-1;
 ll s1 = ((1ull * m * t1 % mod - 1ull * (1 + t1) * t1 % mod * inv2 % mod) + mod) % mod;
 int t2 = n-1;
 ll s2 = ((1ull * n * t2 % mod - 1ull * (1 + t2) * t2 % mod * inv2 % mod) + mod) % mod;
 s2 *= s1;
 s2 %= mod;
 sum2 = s2;
 //printf("sum1=%lld sum2=%lld sum3=%lld\n",sum1,sum2,sum3);
 printf("%llu\n",(sum3 + ((sum1-sum2)%mod+mod)%mod*2) % mod);
 return 0;
}

Codechef REIGN

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 100100;
int T,n,k;
int a[maxn];
int premax[maxn],sufmax[maxn];
signed main(){
 scanf("%lld",&T);
 while(T--){
     int ans = -1e18;
     memset(premax,0,sizeof premax);
     memset(sufmax,0,sizeof sufmax);
     scanf("%lld%lld",&n,&k);
     for(int i=1;i<=n;i++) scanf("%lld",a+i);
     int nowsum = 0;
     int nowmaxlen = 0;
     premax[0] = -1e18;
     for(int i=1;i<=n;i++){
         nowsum += a[i];
         if(nowsum < 0){
             
             premax[i] = max(premax[i-1],nowsum);
             nowsum = 0;
             nowmaxlen = 0;
             continue;
         }
         premax[i] = max(premax[i-1],nowsum);
         ++nowmaxlen;
     }
     nowsum = 0;
     nowmaxlen = 0;
     sufmax[n+1] = -1e18;
     for(int i=n;i>=1;i--){
         nowsum += a[i];
         if(nowsum < 0){
             
             sufmax[i] = max(sufmax[i+1],nowsum);
             nowsum = 0;
             nowmaxlen = 0;
             continue;
         }
         sufmax[i] = max(sufmax[i+1],nowsum);
         ++nowmaxlen;
     }
     //for(int i=1;i<=n;i++) cout << "premax[" << i << "]=" << premax[i] << endl;
     //cout << endl;
     //for(int i=1;i<=n;i++) cout << "sufmax[" << i << "]=" << sufmax[i] << endl;
     
     for(int i=1;i<=n-k-1;i++){
         ans = max(ans,premax[i] + sufmax[i+k+1]);
     }
     printf("%lld\n",ans);
 }
 return 0;
} 

CodeForces 1037E

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
vector<int> G[maxn];
int uu[maxn],vv[maxn];
int degree[maxn];
int ans[maxn];
int nowans = 0;
int n,m,k;
bool del[maxn];
void BFS(int u){
 queue<int> q;
 q.push(u);
 del[u] = true;
 degree[u]--;
 while(!q.empty()){
     u = q.front();
     q.pop();
     nowans--;
     for(int i=0;i<G[u].size();i++){
         int v = G[u][i];
         if(del[v]) continue;
         degree[v]--;
         if(degree[v] < k){
             del[v] = true;
             q.push(v);
         }
     }
 }
}
int main(){
 scanf("%d%d%d",&n,&m,&k);
 for(int i=1;i<=m;i++){
     scanf("%d%d",uu+i,vv+i);
     G[uu[i]].push_back(vv[i]);
     G[vv[i]].push_back(uu[i]);
     degree[uu[i]]++;
     degree[vv[i]]++;
 }
 nowans = n;
 for(int i=1;i<=n;i++){
     if(!del[i] && degree[i] < k){
         BFS(i);
     }
 }
 ans[m] = nowans;
 for(int i=m;i>=1;i--){
     if(!del[uu[i]]) degree[vv[i]]--;
     if(!del[vv[i]]) degree[uu[i]]--;
     G[uu[i]].pop_back();
     G[vv[i]].pop_back();
     if(!del[uu[i]] && degree[uu[i]] < k) BFS(uu[i]);
     if(!del[vv[i]] && degree[vv[i]] < k) BFS(vv[i]);
     ans[i-1] = nowans;
     if(nowans == 0) break;
 }
 for(int i=1;i<=m;i++){
     printf("%d\n",ans[i]);//
 }//
 return 0;
}

Codechef DIGJUMP

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
char str[maxn];
int len;
vector<int> buk[11];
int dis[maxn];
bool vis[maxn];
bool visbuk[11];
int BFS(int x){
 queue<int> q;
 q.push(x);
 vis[x] = true;
 while(!q.empty()){
     int now = q.front();
     //printf("now:%d\n",now);
     q.pop();
     if(now == len-1){
         return dis[now];
     }
     if(now - 1 >= 0 && dis[now-1] > dis[now] + 1){
         dis[now-1] = dis[now] + 1;
         if(!vis[now-1]) {
             vis[now-1] = true;
             q.push(now-1);
         }
     }
     if(now + 1 < len && dis[now + 1] > dis[now] + 1){
         dis[now+1] = dis[now] + 1;
         if(!vis[now+1]) {
             vis[now+1] = true;
             q.push(now+1);
         }
     }
     if(visbuk[str[now]-'0']) continue;
     for(int i=0;i<buk[str[now]-'0'].size();i++){
         if(!vis[buk[str[now]-'0'][i]]) {
             vis[buk[str[now]-'0'][i]] = true;
             q.push(buk[str[now]-'0'][i]);
         }
         dis[buk[str[now]-'0'][i]] = min(dis[buk[str[now]-'0'][i]],dis[now]+1);
     }
     visbuk[str[now]-'0'] = true;
 }
 return -23333;
}
int main(){
 scanf("%s",str);
 memset(dis,0x3f,sizeof dis);
 len = strlen(str);
 for(int i=0;i<len;i++){
     buk[str[i] - '0'].push_back(i);
 }
 dis[0] = 1;
 int ans = BFS(0);
 printf("%d\n",ans-1);
 return 0;
}

Codechef PERMPART

#include <bits/stdc++.h>
using namespace std;
int T,n;
const int maxn = 1000100;
int a[maxn],buk[maxn*2];
signed main(){
 scanf("%d",&T);
 while(T--){
     int ans1 = 0;
     scanf("%d",&n);
     memset(buk,0,sizeof buk);
     int maxa = 0;
     for(int i=1;i<=n;i++){
         scanf("%d",a+i);
         if(a[i] > 2 * n){
             ans1++;
         }else{
             buk[a[i]]++;
             maxa = max(maxa,a[i]);
         }
     }
     priority_queue<int,vector<int>,greater<int> > pq;
     int ans2 = 0;
     for(int i=1;i<=maxa;i++){
         pq.push(buk[i]);
         if(!pq.empty() && pq.top() < buk[i]){
             ans2 += buk[i] - pq.top();
             pq.pop();
             pq.push(buk[i]);
         }
     }
     printf("%d\n",ans1+ans2);
 }
 return 0;
}

ZJOI2007 仓库建设

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000100;
int n; 
ll X[maxn],P[maxn],C[maxn];
ll F[maxn],T[maxn];
ll dp[maxn];
ll M(int x){
 return dp[x] + T[x];
}
int q[maxn * 2];
void doDP(){
 int head=0,tail=-1;
 q[++tail] = 0;
 dp[0] = 0;
 for(int i=1;i<=n;i++){
     while(head < tail){
         int k1 = q[head],k2 = q[head+1];
         if(1.0*(M(k1) - M(k2))/(F[k1] - F[k2]) <= X[i]){
             head++;
         }else{
             break;
         }
     }
     int bestk = q[head];
     dp[i] = C[i] + dp[bestk] + X[i] * (F[i-1] - F[bestk]) - (T[i-1] - T[bestk]);
     //printf("dp[%d]=%lld\n",i,dp[i]);
     while(head < tail){
         int k1 = q[tail],k2 = q[tail-1];
         double kk1 = 1.0 * (M(k1) - M(k2)) / (F[k1] - F[k2]);
         double kk2 = 1.0 * (M(i) - M(k1)) / (F[i] - F[k1]);
         if(kk2 <= kk1){
             tail--;
         }else{
             break;
         }
     }
     q[++tail] = i;
 }
}
int main(){
 scanf("%d",&n);
 for(int i=1;i<=n;i++){
     scanf("%lld%lld%lld",&X[i],&P[i],&C[i]);
     F[i] = F[i-1] + P[i];
     T[i] = T[i-1] + P[i] * X[i];
 }
 doDP();
 printf("%lld\n",dp[n]);
 return 0;
}

BZOJ1303

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n,b;
int a[maxn];
int tmp[maxn];
int ans = 0;
int posb = -1;
map<int,int> mp;
int main(){
 scanf("%d%d",&n,&b);
 for(int i=1;i<=n;i++) scanf("%d",a+i);
 for(int i=1;i<=n;i++){
     if(a[i] < b) tmp[i] = -1;
     else if(a[i] == b) tmp[i] = 0,posb = i;
     else if(a[i] > b) tmp[i] = 1;
 }
 int presum = 0;
 for(int i=posb-1;i>=1;i--){
     presum += tmp[i];
     if(presum == 0) ans++;
     mp[presum]++;
 }
 presum = 0;
 for(int i=posb+1;i<=n;i++){
     presum += tmp[i];
     if(presum == 0) ans++;
     if(mp.count(-presum)) ans += mp[-presum];
 }
 printf("%d\n",ans+1);
 return 0;
} 

BZOJ2783

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct edge{
 int v,nxt;
}E[maxn*2];
int p[maxn],eid;
void init(){
 memset(p,-1,sizeof p);
 eid = 0;
}
void insert(int u,int v){
 E[eid].v = v;
 E[eid].nxt = p[u];
 p[u] = eid++;
}
void insert2(int u,int v){
 insert(u,v);
 insert(v,u);
}
int n,s;
int root;
int pw[maxn];
int x[maxn],y[maxn];
int in[maxn];
int dis[maxn],dep[maxn],anc[maxn][21];
void dfs(int u){
 for(int i=p[u];~i;i=E[i].nxt){
     int v = E[i].v;
     if(v == anc[u][0]) continue;
     anc[v][0] = u;
     dep[v] = dep[u] + 1;
     dis[v] = dis[u] + pw[v];
     dfs(v);
 }
}
void calcAnc(){
 for(int i=1;i<=20;i++){
     for(int j=1;j<=n;j++){
         anc[j][i] = anc[anc[j][i-1]][i-1];
     }
 }
}
int ans = 0;
void solve(int po){
 //printf("solve %d\n",po);
 if(po == root){
     ans += (pw[po] == s);
     //printf("ans += %d\n",(int)(pw[po] == s));
     return;
 }
 int cur = po;
 for(int i=20;i>=0;i--){
     int ancc = anc[cur][i];
     int llen = dis[po] - dis[anc[ancc][0]];
     if(llen <= s) cur = ancc;
 }
 //printf("cur:%d\n",cur);
 int llenn = dis[po] - dis[anc[cur][0]];
 //printf("llenn:%d\n",llenn);
 ans += (llenn == s);
 //printf("ans += %d\n",(int)(llenn == s));
}
int main(){
 init();
 scanf("%d%d",&n,&s);
 for(int i=1;i<=n;i++) scanf("%d",pw+i);
 for(int i=1;i<=n-1;i++){
     scanf("%d%d",x+i,y+i);
     insert2(x[i],y[i]);
     in[y[i]]++;
 }
 for(int i=1;i<=n;i++)
     if(!in[i]){
         root = i;
         break;
     }
 dis[root] = pw[root];
 dep[root] = 0;
 dfs(root);
 anc[root][0] = n+1;
 pw[n+1] = 0;
 calcAnc();
 for(int i=1;i<=n;i++){
     solve(i);
 }
 printf("%d\n",ans);
 return 0;
}

BZOJ3631

#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010;
const int maxm = maxn * 2;
struct edge{
 int v,nxt;
}E[maxm];
int p[maxn],eid;
void init(){
 memset(p,-1,sizeof p);
 eid = 0;
}
void insert(int u,int v){
 E[eid].v = v;
 E[eid].nxt = p[u];
 p[u] = eid++;
}
void insert2(int u,int v){
 insert(u,v);
 insert(v,u);
}
int n;
int a[maxn];
int size[maxn],hson[maxn],dep[maxn],fa[maxn];
void dfs1(int u){
 int maxsz = 0;
 size[u] = 1;
 for(int i=p[u];~i;i=E[i].nxt){
     int v = E[i].v;
     if(fa[u] == v) continue;
     fa[v] = u;
     dep[v] = dep[u] + 1;
     dfs1(v);
     size[u] += size[v];
     if(size[v] > maxsz){
         hson[u] = v;
         maxsz = size[v];
     }
 }
}
int top[maxn];
void dfs2(int u,int tp){
 top[u] = tp;
 if(hson[u]){
     dfs2(hson[u],tp);
 }
 for(int i=p[u];~i;i=E[i].nxt){
     int v = E[i].v;
     if(v == fa[u]) continue;
     if(v == hson[u]) continue;
     dfs2(v,v);
 }
}
int lca(int xx,int yy){
 while(top[xx] != top[yy]){
     if(dep[top[xx]] < dep[top[yy]]) swap(xx,yy);
     xx = fa[top[xx]];
 }
 return dep[xx] < dep[yy] ? xx : yy;
}
int dt[maxn];
void modify(int x,int y,int v){
 int cc = lca(x,y);
 int facc = fa[cc];
 dt[x] += v;
 dt[y] += v;
 dt[facc] -= v;
 dt[cc] -= v;
}
void dfs3(int u){
 for(int i=p[u];~i;i=E[i].nxt){
     int v = E[i].v;
     if(v == fa[u]) continue;
     dfs3(v);
     dt[u] += dt[v]; 
 }
}
int main(){
 init();
 scanf("%d",&n);
 for(int i=1;i<=n;i++) scanf("%d",a+i);
 for(int i=1;i<=n-1;i++){
     int u,v;
     scanf("%d%d",&u,&v);
     insert2(u,v);
 }
 dep[1] = 1;
 dfs1(1);
 dfs2(1,1);
 modify(a[1],a[1],1);
 for(int i=2;i<=n;i++){
     modify(a[i-1],a[i-1],-1);
     modify(a[i-1],a[i],1);
 }
 modify(a[n],a[n],-1);
 dfs3(1);
 for(int i=1;i<=n;i++){
     printf("%d\n",dt[i]);
 } 
 return 0;    
}

P1083 借教室

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
struct node{
    int lazy;
    int minv;
}T[maxn<<2];
int n,m;
int R[maxn];
void pushup(int id){
    T[id].minv = min(T[id<<1].minv,T[id<<1|1].minv);
}
void pushdown(int id){
    if(T[id].lazy){
        T[id<<1].lazy += T[id].lazy;
        T[id<<1|1].lazy += T[id].lazy;
        T[id<<1].minv += T[id].lazy;
        T[id<<1|1].minv += T[id].lazy;
        T[id].lazy = 0;
    }
}
void build(int id,int l,int r){
    if(l == r){
        T[id].minv = R[l];
        return;
    }
    int mid = l + r >> 1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    pushup(id);
}
void update(int id,int l,int r,int x,int y,int v){
    if(x <= l && r <= y){
        T[id].lazy += v;
        T[id].minv += v;
        return;
    }
    pushdown(id);
    int mid = l + r >> 1;
    if(x <= mid){
        update(id<<1,l,mid,x,y,v);
    }
    if(y > mid){
        update(id<<1|1,mid+1,r,x,y,v);
    }
    pushup(id);
}
int query(int id,int l,int r,int x,int y){
    if(x <= l && r <= y){
        return T[id].minv;
    }
    pushdown(id);
    int mid = l + r >> 1;
    int ret = 0x3f3f3f3f;
    if(x <= mid){
        ret = min(ret,query(id<<1,l,mid,x,y));
    }
    if(y > mid){
        ret = min(ret,query(id<<1|1,mid+1,r,x,y));
    }
    return ret;
}
vector<int> cant;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",R+i);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int d,s,t;
        scanf("%d%d%d",&d,&s,&t);
        int minv = query(1,1,n,s,t);
        if(minv < d){
            cant.push_back(i);
            
        }else{
            update(1,1,n,s,t,-d);
        }
    }
    if(cant.size()==0){
        printf("0\n");
        return 0;
    }
    printf("-1\n");
    printf("%d\n",cant[0]);
    return 0;
}

P2161 [SHOI2009]会场预约

标程用词不雅，请不要学习！

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn = 500010;
const int fuckyou = 500000;
struct node{
    int lv,rv;
    int cnt;
    int lazy;
    node(){
        lazy = -1;
        cnt = 0;
    } 
}T[maxn<<2];
void pushdown(int id){
    if(T[id].lazy != -1){
        //printf("pushdown\n");
        T[id<<1].lazy = T[id].lazy;
        T[id<<1|1].lazy = T[id].lazy;
        if(T[id].lazy) T[id<<1].cnt = 1;
        else T[id<<1].cnt = 0;
        if(T[id].lazy) T[id<<1|1].cnt = 1;
        else T[id<<1|1].cnt = 0;
        T[id<<1].lv = T[id<<1].rv = T[id].lazy;
        T[id<<1|1].lv = T[id<<1|1].rv = T[id].lazy;
        T[id].lazy = -1;
    } 
}
node merge(const node &a,const node &b){
    node ret;
    ret.lv = a.lv;
    ret.rv = b.rv;
    ret.cnt = a.cnt + b.cnt;
    //printf("a.cnt=%d b.cnt=%d a.rv = %d b.lv = %d\n",a.cnt,b.cnt,a.rv,b.lv);
    if(a.rv == b.lv && a.rv != 0) {
        ret.cnt--;
        //cout << "cnt--" << endl;
    }
    ret.cnt = max(ret.cnt,0ll);
    //cout << "ret.cnt=" << ret.cnt << endl;
    return ret;
}
void pushup(int id){
    T[id] = merge(T[id<<1],T[id<<1|1]);
}
node query(int id,int l,int r,int x,int y){
    //printf("query l=%d r=%d\n",l,r);
    if(x <= l && r <= y){
        return T[id];
    }
    pushdown(id);
    int mid = l + r >> 1;
    node ret;
    ret.cnt = -999;
    if(x <= mid){
        ret = query(id<<1,l,mid,x,y);
    }
    if(y > mid){
        if(ret.cnt != -999) ret = merge(ret,query(id<<1|1,mid+1,r,x,y));
        else ret = query(id<<1|1,mid+1,r,x,y);
    }
    return ret;
}
void update(int id,int l,int r,int x,int y,int v){
    if(x <= l && r <= y){
        T[id].lazy = v;
        if(v != 0) T[id].cnt = 1;
        else T[id].cnt = 0;
        T[id].lv = T[id].rv = v;
        return;
    }
    pushdown(id);
    int mid = l + r >> 1;
    if(x <= mid){
        update(id<<1,l,mid,x,y,v);
    }
    if(y > mid){
        update(id<<1|1,mid+1,r,x,y,v);
    }
    pushup(id);
}
int n;
int now = 0;
int L[maxn],R[maxn];
void fuckyoumother(int id,int l,int r){
    L[id] = l,R[id] = r;
    int jian = query(1,1,fuckyou,l,r).cnt;
    now -= jian;
    now++;
    cout << jian << '\n';
    int sl = L[query(1,1,fuckyou,l,l).lv];
    int sr = R[query(1,1,fuckyou,r,r).lv];
    if(sl == 0) sl = l;
    if(sr == 0) sr = r;
    update(1,1,fuckyou,sl,sr,0);
    update(1,1,fuckyou,l,r,id);
    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        char cc;
        cin >> cc;
        if(cc == 'A'){
            int l,r;
            cin >> l >> r;
            fuckyoumother(i,l,r); 
        }else{
            cout << now << '\n';
        }
        //cout << "fuckyou" << endl;
    }
    return 0;
}

P1880 [NOI1995]石子合并

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110*2;
int n;
int a[maxn],prea[maxn];
long long mindp[maxn][maxn],maxdp[maxn][maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i+n] = a[i];    
    }
    for(int i=1;i<=2*n;i++) prea[i] = prea[i-1] + a[i];
    memset(mindp,0,sizeof mindp);
    memset(maxdp,0,sizeof maxdp);
    for(int len=1;len<2*n;len++){
        for(int i=1,j=i+len;i<=2*n && j<=2*n;i++,j=i+len){
            mindp[i][j] = 1e18;
            for(int k=i;k<j;k++){
                mindp[i][j] = min(mindp[i][j],mindp[i][k] + mindp[k+1][j] + prea[j] - prea[i-1]);
                //printf("mindp[%d][%d]=%lld\n",i,j,mindp[i][j]);
                //printf("prea[%d] - prea[%d]=%d\n",j,i-1,prea[j] - prea[i-1]);
                maxdp[i][j] = max(maxdp[i][j],maxdp[i][k] + maxdp[k+1][j] + prea[j] - prea[i-1]);
            }
        }
    }
    long long minans = 0x3f3f3f3f;
    long long maxans = 0;
    for(int i=1;i<=n;i++){
        //cout << ">>" << mindp[i][i+n-1] << endl;
        minans = min(minans,mindp[i][i+n-1]);
        maxans = max(maxans,maxdp[i][i+n-1]);
    }
    printf("%lld\n%lld",minans,maxans);
    return 0;
}

计蒜客-银河战舰

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const double pi = acos(-1);
struct Matrix{
    int n,m;
    double mat[6][6];
    Matrix(){}
    Matrix(int _n,int _m){
        n = _n;
        m = _m;
        memset(mat,0,sizeof mat);
    }
    Matrix(int _n,int _m,char unit){
        n = _n;
        m = _m;
        memset(mat,0,sizeof mat);
        for(int i=0;i<3;i++){
            mat[i][i] = 1;
        }
    }
    double* operator [] (const int x) {
        return mat[x];
    }
    Matrix operator * (Matrix &b) const{
        Matrix res(3,3);
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    res[i][j] += mat[i][k] * b[k][j];
                }
            }
        }
        return res;
    }
    void operator *= (Matrix b) {
        *this = *this * b;
    }
};
struct node{
    Matrix lazymul;
    node(){
        lazymul = Matrix(3,3,'E');
    }
    int l,r;
}T[maxn << 2];
void build(int id,int l,int r){
    T[id].l = l;
    T[id].r = r;
    if(l == r){
        return;
    }
    int mid = l + r >> 1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
}
void pushdown(int id){
    T[id<<1].lazymul *= T[id].lazymul;
    T[id<<1|1].lazymul *= T[id].lazymul;
    T[id].lazymul = Matrix(3,3,'E');
}
void updateMul(int id,int l,int r,int x,int y,Matrix &val){
    if(x <= l && r <= y){
        T[id].lazymul *= val;
        return;
    }
    int mid = l + r >> 1;
    pushdown(id);
    if(x <= mid){
        updateMul(id<<1,l,mid,x,y,val);
    }
    if(y > mid){
        updateMul(id<<1|1,mid+1,r,x,y,val);
    }
}
Matrix* query(int id,int l,int r,int x){
    if(l == r){
        return &T[id].lazymul;
    }
    pushdown(id);
    int mid = l + r >> 1;
    if(x <= mid){
        return query(id<<1,l,mid,x);
    }else{
        return query(id<<1|1,mid+1,r,x);
    }
}
int n,m;
double xx[maxn],yy[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&xx[i],&yy[i]);
    }
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        char cc;
        scanf(" %c",&cc);
        if(cc == 'M'){
            double l,r,p,q;
            scanf("%lf%lf%lf%lf",&l,&r,&p,&q);
            Matrix mat(3,3);
            mat[0][0] = 1;
            mat[1][1] = 1;
            mat[2][0] = p;
            mat[2][1] = q;
            mat[2][2] = 1;
            updateMul(1,1,n,l,r,mat);
        }else if(cc == 'X'){
            int l,r;
            scanf("%d%d",&l,&r);
            Matrix mat(3,3);
            mat[0][0] = 1;
            mat[1][1] = -1;
            mat[2][2] = 1;
            updateMul(1,1,n,l,r,mat);
        }else if(cc == 'Y'){
            int l,r;
            scanf("%d%d",&l,&r);
            Matrix mat(3,3);
            mat[0][0] = -1;
            mat[1][1] = 1;
            mat[2][2] = 1;
            updateMul(1,1,n,l,r,mat);
        }else if(cc == 'O'){
            int l,r;
            scanf("%d%d",&l,&r);
            Matrix mat(3,3);
            mat[0][1] = 1;
            mat[1][0] = 1;
            mat[2][2] = 1;
            updateMul(1,1,n,l,r,mat);
        }else if(cc == 'R'){
            int l,r;
            double a;
            scanf("%d%d%lf",&l,&r,&a);
            a = 1.0 * a * pi / 180;
            Matrix mat(3,3);
            mat[0][0] = cos(a);
            mat[0][1] = sin(a);
            mat[1][0] = -sin(a);
            mat[1][1] = cos(a);
            mat[2][2] = 1;
            updateMul(1,1,n,l,r,mat);
        }
    }
    for(int i=1;i<=n;i++){
        Matrix qr = *query(1,1,n,i);
        Matrix org(3,3);
        org[0][0] = xx[i],org[0][1] = yy[i],org[0][2] = 1;
        Matrix ans = org * qr;
        printf("%.2lf %.2lf\n",ans[0][0],ans[0][1]);
    }
    return 0;
}

P3294 [SCOI2016]背单词

标程取名有点丑，简单解释一下

dfs1就是从原trie树中建立新的图，st[]就是题解所提及的栈

dfs1_就是维护新图的newsz[]，即新图子树大小，并把计算结果放入优先队列son[]

dfs2就是按照newsz[]从小到大的顺序dfs，val[]记录的就是给每个终端节点分配的编号

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500010;
int ch[maxn][26],id=0;
int cnt[maxn];
int sz[maxn];
ll ans = 0;
void insert(char *s){
    int len = strlen(s);
    int p = 0;
    for(int i=len-1;i>=0;i--){
        if(ch[p][s[i]-'a']){
            p = ch[p][s[i]-'a'];
        }else{
            ch[p][s[i]-'a'] = ++id;
            p = ch[p][s[i]-'a'];
        }
        sz[p]++;
    }
    cnt[p]++;
}
int n;
char str[100010];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > son[maxn];
vector<int> sons[maxn];

int newsz[maxn];
int st[maxn],pst=0;
void dfs1(int u){
    if(cnt[u]){
        sons[st[pst]].push_back(u);
        st[++pst] = u;
    }
    for(int i=0;i<26;i++){
        int v = ch[u][i];
        if(v){
            dfs1(v);
        }
    }
    if(cnt[u]){
        --pst;
    }
}
void dfs1_(int u){
    newsz[u] = 1;
    for(int i=0;i<sons[u].size();i++){
        int v = sons[u][i];
        dfs1_(v);
        son[u].push(make_pair(newsz[v],v));
        //printf("%d.push(%d,%d)\n",u,newsz[v],v);
        newsz[u] += newsz[v];
    }
}
int val[maxn];
int nowstep = 0;
void dfs2(int u){
    //cout << "u:" << u << endl;
    if(cnt[u]){
        val[u] = ++nowstep;
        //printf("val[%d]=%d\n",u,val[u]);
        ans += val[u] - st[pst];
        st[++pst] = val[u];
    }
    while(!son[u].empty()){
        pair<int,int> now = son[u].top();
        //printf("now:%d,%d\n",now.first,now.second);
        son[u].pop();
        dfs2(now.second);
    }
    if(cnt[u]){
        pst--;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",str);
        insert(str);
    }
    
    dfs1(0);
    dfs1_(0);
    dfs2(0);
    printf("%lld\n",ans);
    return 0;
}

未完待续