2 B
2.1 Description
给定一个长度为 n 的序列，每一个元素由两个整数 a、c 组成，初始化
为 a i = i，c i = 0，现在需要你支持两个操作：
一、对于区间 [l,r] 内的每个元素，c i = c i + |x − a i |，a i = x。
二、统计区间 [l,r] 内 c i 的和。
2.2 Input
第一行包含两个整数 n 和 m，表示序列长度和操作数。
接下来的 m 行每行以一个整数 type 开头，表示操作种类：
如果 type = 1，接下来有 3 个整数 l、r、x，描述操作一的参数。
如果 type = 2，接下来有 2 个整数 l、r，描述操作二的参数。
2.3 Output
对于每个操作 2，输出一行一个整数表示答案。
2.4 Example1
见./example/b1.in、b1.out。
2.5 Example2
见./example/b2.in、b2.out。
2.6 Example3
见./example/b3.in、b3.out。
2.7 Hint
对于 30% 的数据，1 ≤ n,m ≤ 10 2 。
对于 60% 的数据，1 ≤ n,m ≤ 10 4 。
对于 100% 的数据，1 ≤ n,m ≤ 10 5 ，1 ≤ x ≤ 10 8 。
下面是题解时间(你自己写过了吗？)
看到这个题目，想必很多人想到了贪心，但是注意，这并不是普通的贪心，而是 可撤销贪心
可以看看 P3045 [USACO12FEB]牛券Cow Coupons
什么是可撤销贪心呢？
通俗的说，就是已经贪心的选取的物品被更优的方案替代，也就是换掉已取过的物品。
放到这题上来说，就是我们先让一个人去洗澡，如果有必要的话，再把他 裸着 拉出来，换一个人进去
先上代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
typedef long long LL;
using namespace std;
const LL N=1e6+3;
struct node{LL a,b;}t[N];
bool cmp_for_MAXB(node x,node y){
return x.b<y.b;
}
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
priority_queue<int>Q;
LL n,used=0,tot=0;
scanf("%I64d",&n);
for(LL i=1;i<=n;++i)
scanf("%I64d%I64d",&t[i].a,&t[i].b);
sort(t+1,t+1+n,cmp_for_MAXB);
for(LL i=1;i<=n;++i){
if(used+t[i].a<=t[i].b){
Q.push(t[i].a);
++tot;
used+=t[i].a;
}else{
if(used-Q.top()+t[i].a<=t[i].b&&t[i].a<Q.top()){
used=used-Q.top()+t[i].a;
Q.pop();
Q.push(t[i].a);
}
}
}printf("%I64d",tot);
return 0;
}
其实就是几块部分
sort(t+1,t+1+n,cmp_for_MAXB);
按照T2洗完澡的时间排序 (如果T2小的在前面就连选择的余地都没有了...)，应该很好理解，按T1排序没什么用，因为洗的快的也可以靠后洗~qwq
//used是已经用掉的时间
for(LL i=1;i<=n;++i){ if(used+t[i].a<=t[i].b){ //如果时间足以让这个人洗完 ， 就洗吧 Q.push(t[i].a); ++tot; used+=t[i].a; }else{ //如果把最浪费时间的人扯出来，能让这人洗完，并且这人不比被扯出来的人耗时长，就换人 if(used-Q.top()+t[i].a<=t[i].b&&t[i].a<Q.top()){ used=used-Q.top()+t[i].a; Q.pop(); Q.push(t[i].a); } } }
一般可撤销贪心都会使用优先队列来找出替换掉哪个更优。
显然无论怎么贪心，都有一条原则： 我们一定不能亏！
总结
贪心的题目要么做出来，要么做不出而且看了题解恍然大悟自己却就是想不到。
所以要多见识各种模型，才能更好的练习思维。