Codeforces Round #775 (Div. 1)

等到 \(E\) 有中文题解了我再去补吧，所以这篇博客只有一道题的题解。

D. Serious Business

题目描述

有一个 \(3\times n\) 的矩阵，我们要从 \((1,1)\) 走到 \((3,n)\)，每经过一个格子就会获得对应的权值。初始时第二行时不能经过的，有 \(m\) 个活动，第 \(i\) 个活动可以花费 \(k_i\) 的代价把 \([L_i,R_i]\) 的格子解封，你可以选择多个活动，问最后获得的最大权值。

\(n,q\leq 5\cdot 10^5\)

解法

首先考虑只开放一个活动的情况，设 \(sl[i]\) 表示在 \(i\) 点进入第 \(2\) 行的权值，\(sr[i]\) 表示在 \(i\) 点退出第 \(2\) 行的权值，我们想让 \(sl[l]+sr[r]\) 表示经过第 \(2\) 行的 \([l,r]\) 的总经过点权，这个很容易通过前缀和算出来。

那么现在的问题是把左右端点限制在了一段区间内，即 \(L\leq l\leq r\leq R\)，这个可以平凡地用线段树维护，上传的时候用右子树的右端点和左子树的左端点匹配即可。

考虑多个活动的情况，我们枚举 \(R_i\) 最大的那个活动，那么右端点的范围一定在 \([L_i,R_i]\) 中，我们确定左端点即可。那么剩下活动的功能就是拓展左端点的选取范围，我们把所有活动按照 \(R_i\) 排序，对于每个活动我们找出 \(\max_{L_i\leq x\leq R_i} sl[x]\)，然后用它来更新 \(sl[R_i+1]\) 即可（但是有 \(k_i\) 的花费），我们求出新的 \(sl\) 之后就用一个活动的方法做即可。

时间复杂度 \(O(n\log n)\)

#include 
#include 
#include 
using namespace std;
const int M = 500005;
#define int long long
const int inf = 1e18;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,ans,a[3][M],s[M][3],sl[M],sr[M],id[M];
namespace A
{
	int mx[M<<2];
	void build(int i,int l,int r)
	{
		if(l==r) {mx[i]=sl[l];return ;}
		int mid=(l+r)>>1;
		build(i<<1,l,mid);
		build(i<<1|1,mid+1,r);
		mx[i]=max(mx[i<<1],mx[i<<1|1]);
	}
	void ins(int i,int l,int r,int id)
	{
		if(l==r) {mx[i]=sl[l];return ;}
		int mid=(l+r)>>1;
		if(mid>=id) ins(i<<1,l,mid,id);
		else ins(i<<1|1,mid+1,r,id);
		mx[i]=max(mx[i<<1],mx[i<<1|1]);
	}
	int ask(int i,int l,int r,int L,int R)
	{
		if(L>r || l>R) return -inf;
		if(L<=l && r<=R) return mx[i];
		int mid=(l+r)>>1;
		return max(ask(i<<1,l,mid,L,R),
		ask(i<<1|1,mid+1,r,L,R));
	}
}
namespace B
{
	struct node
	{
		int lx,rx,mx;
		node operator + (const node &b) const
		{
			node r;
			r.lx=max(lx,b.lx);
			r.rx=max(rx,b.rx);
			r.mx=max(lx+b.rx,max(mx,b.mx));
			return r;
		}
	}t[M<<2];
	void build(int i,int l,int r)
	{
		if(l==r)
		{
			t[i]={sl[l],sr[l],sl[l]+sr[l]};
			return ; 
		}
		int mid=(l+r)>>1;
		build(i<<1,l,mid);
		build(i<<1|1,mid+1,r);
		t[i]=t[i<<1]+t[i<<1|1];
	}
	node ask(int i,int l,int r,int L,int R)
	{
		if(L<=l && r<=R) return t[i];
		int mid=(l+r)>>1;
		if(mid>=R) return ask(i<<1,l,mid,L,R);
		if(mid