Description 方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。 这排玉米一共有N株，它们的高度参差不齐。 方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。 方伯伯可以选择一个区间，把这个区间的玉米全部拔高1单位高度，他可以进行最多K次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。 问能

Description 方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。 这排玉米一共有N株，它们的高度参差不齐。 方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。 方伯伯可以选择一个区间，把这个区间的玉米全部拔高1单位高度，他可以进行最多K次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。

传送门 跟NOIP2017有点像 由于n<=10^8 , 我们不能记录每个数的位置, 于是我们可以开一棵权值线段树, 记录序列中取走的位置 同时, 还要维护前后两头... 很明显也要用一种数据结构, 我们先来看看要干什么   操作1: 将x的编号变成y, 并输出x的排名 对于第一个, 我们可以开两个map, 一个记录y原来是x变来的, x现在已经变成y了 对于第二个, 我们讨论一下x

[BZOJ3594] [Scoi2014]方伯伯的玉米田 题目大意 给定长度为 n n的一个序列,可以找出kk个区间使这 k k个区间的元素同时+1+1,询问最后最长不下降子序列的大小 n≤104,k≤500,ai≤5000 n\le10^4,k\le 500,a_i\le5000 题解 一个结论:找出的区间的右端点一定是 n n dp[i,j]=max{dp[k,l]}+1

嘟嘟嘟   01分数规划思维题。 题中要求交通总量不减少，那么如果总量增加的话，总费用就会增加，所以一定不是更优的解。那么总量守恒。 这是不是就想到了网络流？对于每一个节点流入量等于流出量。然后就是很有思维的一个转化了：把压缩看成退流，把扩容看成增广。 边(x, y)一次压缩，就建一条y -> x，容量为a - d的边。 边(x, y)一次增广，就建一条x -> y，容量为b + d的边。也就是

题面 　　Bzoj3595 解析 　　wys讲到用Splay， 但我又一次写成了Spaly 　　考虑到n的范围巨大而m的范围是正常的1e5， 显然要动态开点，一个点代表一个区间。但这道题只用一棵平衡树可能不太好做，于是有dalao就写了两棵平衡树， 显然我这种一棵平衡树都要写挂的人是不可能去完成两棵平衡树的，于是可以用map代替其中一棵树。其中map第一关键字为区间的右端点，第二关键字为节点编号