看到这个问题，我们先分析下什么时候不可行。 为了方便我们称的区间为区间，称的区间为区间 经过漫长的讨论，我们发现只有当一个区间是一个区间的子区间时答案是不存在，其他情况都可以通过构造得到。 那么问题就转化为判断每一个区间是否是某个区间的子区间。 不难想到把区间要求离线下来，同时对于每个点用并查集维护它所在区间的左端点和右端点（即把连续的区间拼接起来）。只要一个区间里的每一个点都满足它所在的区间的左端点不大于区间的左端点且它所在的区间的右端点不小于区间的右端点，那么这个区间就是区间的子区间。 构造的话我们只要搞一个差分数组就行了。 #include<bits/stdc++.h> us...

做法前面的大佬都说的很清楚了，这题的关键主要在于对宗教建线段树和动态开点。 既然是动态开点就要记录下每个节点的左右儿子，这里用引用调用来更新每个点的左右儿子。事实上能对答案产生贡献的只有有值的节点，所以对于没有值的节点我们不需要把它建出来，这样可以省不少空间。这里仿照了Owen_codeisking大佬的写法。 void update(ll &p,ll l,ll r,ll pos,ll det) { if(!p) p = ++tot;//新节点 if(l == r)//到了要更新的点的位置。 { tree[p].sum = det; tree[p].maxx = det; return...

扫描线板子题？ 首先离散化是理所当然的，因为这个矩形无上界，我们考虑按排序，从上往下枚举。（其实也算是出题人的暗示） 接下来的问题是如何统计下界为的矩形数量，事实上我们只关心矩形的和,自然而然想到枚举,枚举什么？？枚举和会让复杂度爆炸。 考虑如何优化，（当然是换个东西枚举）我们选择枚举相同的点，对于一个点，在左侧的点会对产生贡献，在右侧的点会对产生贡献。但是我们发现这样有重复的矩形！ 仔细思考一波，事实上不同的产生的矩形是不同的，对于一个点，只有在(这里)到之间的还没有被统计过。这样我们只需要统计右侧的点和到之间的点的数量，再根据乘法原理得到答案就行了。 萌新：统计要枚举啊。 神犇：出门左转树...

这题事实上要我们求的是: 当前拼接好的串的后缀 和 待拼接串的前缀 的最大匹配长度。 可能有点绕，我们结合样例2来理解下。 当前拼接好的串  待拼接串  后缀和前缀的最大匹配  最大匹配长度  所以我们只要把 加入到当前拼接好的串。 此时当前拼接好的串  这下应该理解了吧 那么怎么求最大匹配长度呢？ 匹配？想到啥？ KMP! 和待拼接串的前缀匹配？ 那么构造一个待拼接串在前,当前拼接好的串在后的新串，求出当前拼接好的串的最后一个字符的值不就行了？(啥是[](https://www.luogu.org/problem/P3375)?) 值得注意的是最大匹配长度不会超过待拼接串的长度，所以每次只要...

蒟蒻不会单调队列，怎么办？另类方法，一样AC 题目要我们求最小的，这看上去就不太好直接求。怎么办？ 一个常见的想法，将原问题转换成判定性问题:给定弹跳距离的范围，能否获得至少分。(注意:玩家可以在任意时刻结束游戏，所以只要出现一个时刻的分数满足即可） 一个朴素的想法:可以DP! 每次找前面合法状态(即符合弹跳距离)中当前分数最大的状态转移。 ，朴素的枚举好像会挂。怎么优化？ 注意到每次事实上有用的只有分数最大的那个状态，想到了啥？ RMQ?优先队列？(我也不知道为啥想到的不是单调队列而是优先队列) 想到这里那么这一题已经基本做完了。 用优先队列维护所有合法状态，每次取出堆顶转移即可。 实测不开...

树形dp模板题首先建一个虚拟节点0，让原本的森林变成一颗树。然后我们设dp[i][j]表示以i为根的子树中,选j门课的最大价值。转移时我们枚举当前以x为根的子树选课的数量(t)，以及分配给x的子节点y多少节课(j)。不难写出方程：dp[x][t]=max(dp[x][t],dp[x][t-j]+dp[y][j]); #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn=510; const ll INF=2147483647; ll n,m,s,a[maxn],dp[maxn...

k=1时，如果我们新修建一个道路，那么就会有一段路程少走一遍。此时选择连接树的直径的两个端点显然是最优的。 难就难在k=2的时候，还是上面的思路，先连接两个直径的端点。假设我们接下来连接的是x,y两个叶子结点，它们到直径的距离分别为dis[x],dis[y]，并设直径上两点的距离为d[u,v]，这里u,v分别为x,y所在链和直径的交点。 因此最后的答案会增加d[u,v]-dis[x]-dis[y]。要使答案最小，那么也就是使dis[x]+dis[y]-d[u,v]最大。这其实就是把u到v路径上的边权取反后，树的最长链。 再求一次树的直径就好了。注意:因为最后有负边权存在，用dfs/bfs来求会...

k=1时，如果我们新修建一个道路，那么就会有一段路程少走一遍。此时选择连接树的直径的两个端点显然是最优的。      难就难在k=2的时候，还是上面的思路，先连接两个直径的端点。假设我们接下来连接的是x,y两个叶子结点，它们到直径的距离分别为dis[x],dis[y]，并设直径上两点的距离为d[u,v]，这里u,v分别为x,y所在链和直径的交点。      因此最后的答案会增加d[u,v]-dis[x]-dis[y]。要使答案最小，那么也就是使dis[x]+dis[y]-d[u,v]最大。这其实就是把u到v路径上的边权取反后，树的最长链。      再求一次树的直径就好了。注意:因为最后有负边...