T1（莫队，增量式维护答案）
https://www.luogu.com.cn/problem/P1494
1731。
看上一篇总结的莫队。双倍经验。
QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const int N = 50010;
int n, m, L;
int cnt[N], w[N];
struct Query { int l, r, bcnt, id;
bool operator< (const Query& W) const
{
if (bcnt != W.bcnt) return bcnt < W.bcnt;
return r > W.r;
}}q[N];
PLL ans[N];
void work(int x, int type, LL& res)
{
res -= (LL)cnt[x] * (cnt[x] - 1) / 2; //无论加还是减，之前的都没了
cnt[x] += type;
if (cnt[x] >= 2) res += (LL)cnt[x] * (cnt[x] - 1) / 2;
}
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
scanf("%d%d", &n, &m);
L = sqrt(n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
for (int i = 1; i <= m; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
q[i] = {l, r, (l - 1) / L + 1, i};
}
sort(q + 1, q + m + 1);
LL res = 0;
for (int i = 1, l = 1, r = 0; i <= m; i ++ )
{
while (l > q[i].l) -- l, work(w[l], 1, res);
while (r < q[i].r) ++ r, work(w[r], 1, res);
while (l < q[i].l) work(w[l], -1, res), l ++ ;
while (r > q[i].r) work(w[r], -1, res), r -- ;
if (!res) ans[q[i].id] = {0, 1};
else
{
LL a = q[i].r - q[i].l + 1;
LL k = gcd(res, a * (a - 1) / 2);
ans[q[i].id] = {res / k, a * (a - 1) / 2 / k};
}
}
for (int i = 1; i <= m; i ++ )
if (!ans[i].first) puts("0/1");
else printf("%lld/%lld\n", ans[i].first, ans[i].second);
return 0;
}
T2(斜率优化dp模板,费用提前计算思想）
814。
https://www.acwing.com/problem/content/303/
首先做出dp.dp完了优化转移
由于我们知道分了几批就是为了算启动代价，不如直接累加到值里面，把后面的提前算了！
费用提前计算:把以后启动的代价都算进来。
这样状态就变成了：f[i]，前i个物品选若干次，已经考虑当前批代价和对以后启动时间的代价的最小值。
还可以这样理解：
。这样，以c为横坐标，f为纵坐标，我们发现这是个斜率相同的直线，现在所决策应该是一个点，这个点所形成的的直线的截距最小。这是啥？直接凸包维护就好了，取的值就是遍维护凸包边算就行，最后加进来（加进来一定横坐标单调）。
扩展：t不单调（也就是t可以为负）：那就没有办法利用询问斜率的单调性了，只能维护整个凸包。（原先可以边问边删），二分就好。c不单调：那就套一层平衡树维护凸包。
QAQ
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n, s;
LL c[N], t[N];
LL f[N];
int q[N];
int main()
{
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; i ++ )
{
scanf("%lld%lld", &t[i], &c[i]);
t[i] += t[i - 1];
c[i] += c[i - 1];
}
int hh = 0, tt = 0;
q[0] = 0;
for (int i = 1; i <= n; i ++ )
{
while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh ++ ;
int j = q[hh];
f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ;
q[ ++ tt] = i;
}
printf("%lld\n", f[n]);
return 0;
}
T3（反悔式贪心及部分贪心的证明）
我的比赛思路：
U题，首先考虑dp，肯定开的状态是：前i个，时间，收益。时间当然开不下，考虑优化。发现对于每一秒，都必须打一只。这样大于i的时间就没有用了，一定不优。这样按照当前选不选就能做。不过复杂度是n^2。只能贪心。考虑留一维。必须有时间，于是留下时间t，就是每个物品看看咋选，发现d>t的没必要考虑，只需要留到后面打掉就行了。如果后面打掉不优，还可以调整。这样我排个序，开了个堆维护当前最优的。然后也是写挂了。
V题，消除一定是区间，考虑区间dp。转移就是要么中间消掉，再打两边，要么枚举断点。没错又写挂了。
W题，安排m个树上不相交路径，求最小值最大。当然二分，然后后面咋做没想好。感觉好像可以把所有路径按照根节点分类？写了45分的链和菊花分。
X题，我的想法，可能一定是删掉原图中某些冗余边？然而对于如何判断这个冗余和上述结论，都没想太好。
在做前两题的时候，u题写了个对拍，是a的。不知道怎么挂了。v题自己也是手捏了很多数据，然而也是wa。
我的思路，维护前i个老鼠的最优解。
实际上要求的其实就是最优解唯一。
两个极值点，一定能分出高下。
我们的贪心就是不断探极值的情况。
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
struct Node { int d, v;
bool operator< (const Node& W) const
{
if (d != W.d) return d < W.d;
return v > W.v;
}
} a[N];
priority_queue<int, vector<int>, greater<int> > q;
LL res;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i].d, &a[i].v);
sort(a + 1, a + n + 1);
int tim = 1;
q.push(a[1].v);
res += a[1].v; //特判，防止里面没东西，一定加进去
for (int i = 2; i <= n; i ++ )
{
if (tim < a[i].d) tim ++ , res += a[i].v, q.push(a[i].v);
else
{
int t = q.top(); //取出来的过期时间一定小于i,既然他能放进去，那i也能放进去。
if (t < a[i].v)
{
q.pop();
res = res - t + a[i].v;
q.push(a[i].v);
}
}
}
cout << res << endl;
return 0;
}
T4
区间dp。f[i][j]表示i~j最大。
决策：最后一段:f[i][j - 1]
or f[i][p]？？？与中间一段接上再一块消。
这里状态没办法描述了。我们考虑加一维。既然要加上一块消，我们就直接f[i][j][k]，k是向右延拓k个格子和最后一段一块消除。
o。
QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, cnt;
int f[N][N][N];
int a[N], c[N], w[N];
int dp(int x, int y, int k)
{
if (x > y) return -0x3f3f3f3f;
if (f[x][y][k]) return f[x][y][k];
f[x][y][k] = max(f[x][y][k], dp(x, y - 1, 0) + f[y][y][k]);
for (int i = x; i < y - 1; i ++ )
if (c[i] == c[y]) f[x][y][k] = max(f[x][y][k], dp(x, i, w[y] + k) + dp(i + 1, y - 1, 0));
return f[x][y][k];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1, j = i; i <= n; i = j)
{
j = i;
while (j <= n && a[j] == a[i]) j ++ ;
int len = j - i;
c[ ++ cnt] = a[i];
w[cnt] = len;
}
for (int i = 1; i <= cnt; i ++ )
for (int k = 0; i + k <= n; k ++ ) //有可能处理n个，这里注意
f[i][i][k] = (w[i] + k) * (w[i] + k);
cout << dp(1, cnt, 0) << endl;
return 0;
}
T5(树形dp，二分，树上不相交路径dp套路）
安排m个树上不相交路径，求最小值最大。有最优子结构：全局最优，子树就最优。
考虑二分判断+dp.
优化的关键在于只有一条边传上去。这使得我们可以一个个子树考虑。
子树最优嘛，要是不最优，那最多多向上的一条，所以子树多选一定不劣。那现在问题就是当前点最多贡献多少个答案？
答案就是处理传上来的这些边，排个序，贪心匹配。（为啥？最优子结构啊，当前最优就一定不劣），剩下的最大值再传上去。这样就最优了。o。
偷个懒，这里用multiset。
思想的本质：
其实本质还是dp套路：f[u] = f[son] + ().(son，u之间的贡献）
只不过这里的贡献不仅仅是贡献，还要上传最大的边来维护递推。其实只要知道子树传上来最大的边，son和u的问题就变成贪心匹配的问题了。
所以优化的关键在于只有一条边传上去。这使得我们可以一个个子树考虑。
子树内的路径已经考虑完了，经过根的还没考虑呢，但是经过根的路径每个子节点最多传上来一条~，当然传最大的,我们维护一下就行了。
T6(传递闭包，最优决策分析，贪心，无向图拓扑考虑）
最优解唯一，就可以不断探向最优解了，不断维护局部最优解。考虑递推。
无环图按拓扑排序考虑算是常用思路吧。
做法已经写的很明白了。看思路，首先拓扑图，这样我们就能想到，如果只维护后面的最值就可以了，这样就可以递推了。发现最优解唯一
ok，我们考虑保留u的邻边，我们可以想到，编号小的理应不选就没得选了，因此我们考虑不断取小的。
按v从小到大，如果当前过不去，后面的只能更往后，不可能走回到v来
ok，那这样递推就解决了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int res, n, m;
bool g[N][N];
bool s[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) g[i][i] = true;
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
s[a][b] = true;
}
int res = 0;
for (int i = n; i; i -- )
for (int j = i + 1; j <= n; j ++ )
if (s[i][j] && !g[i][j]) //能加
{
res ++ ;
for (int k = j; k <= n; k ++ )
g[i][k] |= g[j][k];
}
cout << res << endl;
return 0;
}
T7（树上最小支配集模板）
