题解：
没打。。。
ab题满世界都过了应该没什么意思
c题是个比较有意思的思维题（先看了题解才会的。。。）
我们考虑这么一件事情
没钥匙的人出门后
门一定是开着的
他进来的时候，门一定是开着的
其他时候，一定门能关着比较好
但是这个东西并不是很好维护，因为可能重复算
我们考虑重新排个序
我们把a[]在b[]前面的那个排在他前面
这样我们只需要记录一下上一个取了没有就可以了
感觉说出来不是很好理解这个东西。。。
d题还是个有点难度的数据结构题
一件比较显然的事情是我们对a的操作等价于是要
找当前x修改后是不是前缀最大值，以及他能延伸到哪（这个权值线段树显然可以维护）
然后就变成了区间覆盖成一个值了
然后 刚开始就想错了。。。
刚开始想的是去考虑这一段的值是怎么通过原先值变化的
其实这样反而不好做
直接去暴力统计现在的值
那么我们要知道的其实就是 当前区间>k的数的个数以及<k的数的乘积
这玩意我好像只会树套树或者cdq分治+排序+线段树。。。(写起来挺烦的啊）
于是复杂度就是nlog^2n了
不知道正解是怎么玩的。。。
代码：
c:
#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) const int N=3000; const int INF=1e9; struct re{ int a,b,c,pos; }a[N],b[N],c1[N],c2[N],p[N]; int pre[N],pos[N],x1[N],x2[N],f[N][N][2]; bool tt[N]; bool cmp(re x,re y) { return x.b<y.b; } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); ios::sync_with_stdio(false); int n,m; cin>>n>>m; rep(i,1,n) { cin>>a[i].a>>a[i].b; a[i].pos=i; b[i*2-1].a=i*2-1; b[i*2-1].b=a[i].a; b[i*2].a=i*2; b[i*2].b=a[i].b; } sort(a+1,a+n+1,cmp); sort(b+1,b+2*n+1,cmp); rep(i,1,n) pos[a[i].pos]=i; rep(i,1,n*2) { if (b[i].a%2==0&&b[i-1].a%2==1) pre[b[i].a/2]=(b[i-1].a+1)/2; if (b[i].a%2==0) x2[b[i].a/2]=b[i].b-b[i-1].b; if (b[i].a%2==1) x1[(b[i].a+1)/2]=b[i+1].b-b[i].b; } int cnt=0; rep(i,1,n) if (!tt[i]) { int x=i; p[++cnt].a=a[x].a; p[cnt].b=a[x].b; p[cnt].c=0; tt[i]=1; if (pos[pre[a[x].pos]]!=x) c1[cnt].a=x1[a[x].pos],c1[cnt].b=x2[a[x].pos]; else c1[cnt].a=x1[a[x].pos],c1[cnt].b=0; while (pos[pre[a[x].pos]]&&pos[pre[a[x].pos]]!=x) { x=pos[pre[a[x].pos]]; tt[x]=1; p[++cnt].a=a[x].a; p[cnt].b=a[x].b; p[cnt].c=1; c1[cnt].a=x1[a[x].pos]; c1[cnt].b=x2[a[x].pos]; } } rep(i,1,n) rep(j,0,m) { f[i][j][0]=f[i][j][1]=INF; if (p[i].c) { if (j) f[i][j][1]=min(f[i][j][1],min(f[i-1][j-1][1],f[i-1][j-1][0])); f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+c1[i].b); f[i][j][0]=min(f[i][j][0],f[i-1][j][1]+c1[i].b+c1[i].a); } else { if (j) f[i][j][1]=min(f[i][j][1],min(f[i-1][j-1][1],f[i-1][j-1][0])); f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+c1[i].b+c1[i].a); f[i][j][0]=min(f[i][j][0],f[i-1][j][1]+c1[i].b+c1[i].a); } } cout<<min(f[n][m][1],f[n][m][0]); return 0; }