CF1890 E1. Doremy‘s Drying Plan (Easy Version)

Drying Plan (Easy Version)"/>

CF1890 E1. Doremy‘s Drying Plan (Easy Version)

传送门:CF

[前题提要]:题目很简单,就是给你 n n n个区间,然后你可以删除两个区间,然后问如何删最后能获得最小覆盖,VP时感觉是一道数据结构,但是又感觉不好维护,又感觉是一道dp,但是复杂度又爆炸

结果 e a s y easy easy确实是一道数据结构,但是 h a r d hard hard确实一道 s t st st表优化的 d p dp dp

先来讲讲 e a s y easy easy.果然还是得从那个2进行入手.

考虑我们的两个区间,我们会发现一共也就只有两种情况,一种是两个区间相交的,一种是两个区间不相交.

先分析一下两个区间不相交的情况.稍微分析一下就会发现这种情况每个区间的贡献就是区间内覆盖次数为1的点.所以我们只要维护出每个区间内覆盖次数为1的点,然后排个序就行.

这样的想法带来了两个问题,首先是如何维护出每一个区间内覆盖次数为1的点.刚开始我的想法是用线段树来维护,但是线段树维护这个似乎有点麻烦.然后想到了差分,诶,因为不是在线修改的原因,所以差分就十分方便了.考虑使用差分来维护区间覆盖,那么我们对差分数组的前缀和就维护出了每一个点的区间覆盖次数.然后我们对每一个点的区间覆盖次数再一次进行前缀和,这样我们就轻易的维护出了区间覆盖次数为1或者2或者0的点的个数.
第二个问题就是如何找出两个不相交的区间.其实事实上我们根本不需要管两个区间是否相交.因为此时的情况我们是在不相交的前提下进行考虑的.所以假设我们选了两个相交的区间.但是此时我们并没有考虑相交部分,所以此时我们的贡献一定是比我们下面相交的情况要小的.所以此时的区间贡献一定会被覆盖,所以我们根本不需要对他们进行考虑.

然后考虑两个区间相交的情况.显然此时多出来的贡献就是覆盖次数为2的点.可以枚举这个点,将区间按左端点排序后用优先队列维护,算出是哪两个区间包括这个点
那此时的答案即为同时被两个区间所包含的点中被覆盖2次的点的个数加上两个区间中所有被覆盖一次的点的个数，在所有被覆盖次的点中取最大值即可。
至于怎样求一个区间内被覆盖1或2次的点的个数,还是可以用前缀和和差分维护。

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Line{int l,r;bool operator < (const Line &rhs) const {if(l!=rhs.l) return l<rhs.l;else return r<rhs.r;}
}line[maxn];
struct heapnode{int l,r;bool operator < (const heapnode &rhs) const {return r>rhs.r;}
};
int sum[maxn];int sum1[maxn],sum2[maxn];int cnt1[maxn];
signed main() {int T=read();int cnt=0;while(T--) {cnt++;int n=read();int m=read();int k=read();for(int i=1;i<=m;i++) {line[i].l=read();line[i].r=read();}sort(line+1,line+m+1);for(int i=1;i<=m;i++) {sum[line[i].l]++;sum[line[i].r+1]--;}for(int i=1;i<=n;i++) sum[i]=sum[i-1]+sum[i];int SUM=0;for(int i=1;i<=n;i++) {SUM+=(sum[i]==0);sum1[i]=sum1[i-1]+(sum[i]==1);//前缀覆盖1的点个数sum2[i]=sum2[i-1]+(sum[i]==2);//前缀覆盖2的点的个数}for(int i=1;i<=m;i++) {cnt1[i]=sum1[line[i].r]-sum1[line[i].l-1];}sort(cnt1+1,cnt1+m+1);reverse(cnt1+1,cnt1+m+1);int ans=SUM+cnt1[1]+cnt1[2];priority_queue<heapnode>q;int pos=0;for(int i=1;i<=n;i++) {while(pos+1<=m&&line[pos+1].l<=i) {pos++;q.push({line[pos].l,line[pos].r});}while(!q.empty()&&q.top().r<i) {q.pop();}if(sum[i]==2) {heapnode f1=q.top();q.pop();heapnode f2=q.top();q.pop();ans=max(ans,sum1[f2.r]-sum1[min(f1.l-1,f2.l-1)]+SUM+sum2[f1.r]-sum2[max(f1.l-1,f2.l-1)]);q.push(f1);q.push(f2);}}cout<<ans<<endl;for(int i=1;i<=n+10;i++) {sum[i]=sum1[i]=sum2[i]=0;}for(int i=1;i<=m;i++) cnt1[i]=0;}return 0;
}