[POI2015]LOG
维护一个长度为n的序列，一开始都是0，支持以下两种操作：1.U k a 将序列中第k个数修改为a。2.Z c s 在这个序列上，每次选出c个正数，并将它们都减去1，询问能否进行s次操作。每次询问独立，即每次询问不会对序列进行修改。
n<=1e6
修改数值不好掌握。我们离线读入询问，把所有的s，a离散化下来。
发现，对于一个Z c s，我们只要判断能不能操作。所以只关心大小关系。
大于等于s的数可以在s次中都参与贡献，小于s的数只能部分参与贡献。
设cnt为不小于s的数的出现次数，sum为小于s的数的出现次数。
可以操作的当且仅当：
sum>=s*(c-cnt)
意即，cnt个数每次都贡献之后，每次还剩(c-cnt)个要贡献，有s次。这些都要由小于s的数贡献。
所以如果sum>=s*(c-cnt)，那么必然可以，否则必然不行。
权值线段树维护即可。
[POI2015]PUS
线段树优化建图。
[POI2015]PUS
[POI2015]KIN
题目描述
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
注意题意：一个电影看的多于一次，贡献就变成0了。
肯定要nxt
枚举左端点l。
线段树维护答案。每个位置p的值的意义是，当左端点是当前的l时，右端点是p的答案是多少。
从右往左枚举左端点。
枚举到i，就把i~nxt[i]-1加上w[i]，nxt[i]~nxt[nxt[i]]-1减去w[i]即可。
取后缀[i,n]的mx作为本次的答案即可。
这样每个点会第一次出现的时候把贡献加上，又一次出现的时候，就把之前的贡献减去了。
突破口：枚举一个端点，考虑最新加入的点对右端点取哪些点的答案会造成影响。
一个 思想是：
一般考虑：枚举右端点是哪个，然后计算答案。
这个是：直接保存右端点是某个位置的话，答案是多少。只要动态更新答案，那么直接取max即可。
然后转化为每个点的贡献。