【CF833E】Caramel Clouds（线段树）
题面
题解
首先把区间一段一段分出来，那么只有四种情况。
要么没有被任何一朵云被覆盖，那么直接就会产生这一段的贡献。
要么被一朵云覆盖，要么被两朵云覆盖。
要么被三朵及以上的云所覆盖，那么这段的贡献永远取不到。
对于每朵云预处理出只被其覆盖的区间长度\(len[i]\)，这样子就能处理只选择一朵云的贡献了。
现在考虑如何处理选择两朵云。
这里有两种情况。
第一种是两朵云无交，那么贡献就是\(len[i]+len[j]\)。
否则的话有交，并且交的部分只被这两朵云所覆盖，不能发现这样子的情况不会超过\(n\)个，这个东西可以拿出来暴力更新。
这样子我们可以预处理一个前缀的值，代表在这个位置之前选择云能够得到的最大空出来的时间。
对于第一种情况，可以按照价格大小构建一棵线段树，这样子每次就是区间查最大值。
对于第二种情况，找到这个区间然后把两个的贡献算在一起就好了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define MAX 300300
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Cloud{int l,r,c;}c[MAX];
bool operator<(Cloud a,Cloud b){return a.c<b.c;}
struct Node{int t,opt,id;}a[MAX<<1];
bool operator<(Node a,Node b){return a.t<b.t;}
struct Qry{int k,id;}q[MAX];
bool operator<(Qry a,Qry b){return a.k<b.k;}
int n,m,C,cnt,ans[MAX],len[MAX],cho[MAX];
namespace SegmentTree
{
#define lson (now<<1)
#define rson (now<<1|1)
int t[MAX<<2];
void Modify(int now,int l,int r,int p,int w)
{
if(l==r){t[now]=w;return;}
int mid=(l+r)>>1;
if(p<=mid)Modify(lson,l,mid,p,w);
else Modify(rson,mid+1,r,p,w);
t[now]=max(t[lson],t[rson]);
}
int Getmax(int now,int l,int r)
{
if(l==r)return l;
int mid=(l+r)>>1;
if(t[lson]>t[rson])return Getmax(lson,l,mid);
else return Getmax(rson,mid+1,r);
}
int Query(int now,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return Getmax(now,l,r);
int mid=(l+r)>>1,ret=0;
if(L<=mid)ret=Query(lson,l,mid,L,R);
if(R>mid)
{
int x=Query(rson,mid+1,r,L,R);
if(len[x]>len[ret])ret=x;
}
return ret;
}
}
using namespace SegmentTree;
set<int> S;
map<int,int> M[MAX];
int Calc(int i,int j){if(i>j)swap(i,j);return len[i]+len[j]+M[i][j];}
int main()
{
n=read();C=read();
for(int i=1;i<=n;++i)c[i].l=read(),c[i].r=read(),c[i].c=read();
sort(&c[1],&c[n+1]);c[n+1]=(Cloud){0,0,2000000000};
for(int i=1;i<=n;++i)a[++cnt]=(Node){c[i].l,1,i},a[++cnt]=(Node){c[i].r,-1,i};
sort(&a[1],&a[cnt+1]);a[++cnt]=(Node){2000000010,1,n+1};
m=read();for(int i=1;i<=m;++i)q[i].k=read(),q[i].id=i;
sort(&q[1],&q[m+1]);
int Sum=0,Del=0;
for(int i=1,tim=0,pos=1;i<=cnt;++i)
{
int l=a[i].t-tim;tim=a[i].t;
if(!S.size())Sum+=l;
else if(S.size()==1)
{
int x=*S.begin();
len[x]+=l;cho[x]+=l;Modify(1,1,n,x,len[x]);
if(c[x].c<=C)
{
int l=1,r=upper_bound(&c[1],&c[n+1],(Cloud){0,0,C-c[x].c})-c-1,val=len[x];
if(l<=x&&x<=r)
{
if(l<=x-1)val=max(val,Calc(x,Query(1,1,n,l,x-1)));
if(x+1<=r)val=max(val,Calc(x,Query(1,1,n,x+1,r)));
}
else if(l<=r)val=max(val,Calc(x,Query(1,1,n,l,r)));
cho[x]=max(cho[x],val);
Del=max(Del,cho[x]);
}
}
else if(S.size()==2)
{
int x=*S.begin(),y=*S.rbegin();M[x][y]+=l;
if(c[x].c+c[y].c<=C)
{
cho[x]=max(cho[x],Calc(x,y));
cho[y]=max(cho[y],Calc(x,y));
Del=max(Del,max(cho[x],cho[y]));
}
}
while(pos<=m&&Del+Sum>=q[pos].k)ans[q[pos].id]=tim-(Del+Sum-q[pos].k),++pos;
if(a[i].opt==1)S.insert(a[i].id);
else S.erase(a[i].id);
}
for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
return 0;
}