【题解】「MSTOI-R1」超速检测II

这里是验题人的超级复杂 tj。这个题我的评价是

不带修的问题：

结论：答案等于最大的 $\sum_{u\in S} V_u$ $\sum_{u \in S} V_{u}$ ，其中 $S$ $S$ 满足：
- $S$ 是速度限制组成的集合。
- $S$ 中的限制两两 $[l,r]$ 不交。

于是我们可以有一个很显然的 dp，

f_i

表示当前考虑到点

i

，最大的

\sum S

是多少。转移是

f_{i}=\max (f_{i-1},f_{l}+v)

，其中

l,v

是以

i

为

r

的一个速度限制。复杂度

O(d(m+n))

。

对结论的证明：
按照右端点大小顺序考虑每个限制。每次新考虑一个限制，然后我们只需要满足当前考虑过的限制是合法的即可。
不妨令 $T$ 为与当前加入的这个限制 $[l,r]$ 有交的限制集合。
如果转移取的是 $f_l+v$ ，那说明 $v$ 可以满足 $T$ 中的限制，而 $f_l$ 满足了前面的限制。
如果转移取的是 $f_{i-1}$ ，那说明当前限制被 $T$ 中的满足了。

考虑原问题：

对于一个询问，发现我们不能选

[l,r]

。所以如果询问的

V

比原来的大，那么就好搞。否则我们需要特殊处理。考虑我们再做一个反着 dp 的数组

g_i

，那么分讨：

$[l,r]$ 没有被 $S$ 中的一个限制完全覆盖，这里的可能答案为 $\max_{i=l+1\sim r-1} f_i+g_i$ ，st 表处理。
$[l,r]$ 被 $S$ 中的一个限制完全覆盖。这部分有点麻烦。我们在下面考虑这部分内容。

先离线，然后对点扫描线。以

i

结尾的可能有询问或原本的限制。把询问按照左端点大小排序，把以

i

结尾的询问加入线段树。对于原本的限制

[l,i,V]

，我们把左端点在

[l+1,i]

内的询问用

f_l+g_i+V

进行更新。

然后我们按此操作，将整个序列反过来再做一边，于是对于一个原本的限制

[l,r,V]

，我们对于

l\le u\le v\le r

，且满足

u\neq l \mathrm{\ or\ } v\neq r

的询问进行了更新。

于是我们完成了这个题目。复杂度

O(n\log n)

。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL N=1e5+10;
LL n,m,d,f[N],g[N],st[N][17],lg[N],ans[N],zsw[N];
vector<PII> L[N],R[N];
LL query(LL l,LL r)
{
	LL t=lg[r-l+1];
	return l>r?0:max(st[l][t],st[r-(1<<t)+1][t]);
}

namespace SegT
{
	struct node { LL l,r,val,tag; }t[N<<2];
	struct zxz { LL l,r,id; }a[N];
	vector<LL> ad[N];
	#define ls (k<<1)
	#define rs (k<<1|1)
	#define mid (l+r>>1)
	bool cmp(zxz a,zxz b) { return a.l<b.l; }
	void addtag(LL k,LL v)
	{
		t[k].tag=max(t[k].tag,v);
		t[k].val=max(t[k].val,v);
	}
	void pushdown(LL k)
	{
		addtag(ls,t[k].tag);
		addtag(rs,t[k].tag);
		t[k].tag=0;
	}
	void modify(LL k,LL l,LL r,LL L,LL R,LL mx)
	{
		if(l>R||L>r) return;
		if(L<=l&&r<=R) return addtag(k,mx);
		pushdown(k);
		modify(ls,l,mid,L,R,mx);
		modify(rs,mid+1,r,L,R,mx);
	}
	void miku(LL k,LL l,LL r,LL x)
	{
		if(l>x||r<x) return;
		if(l==r) return t[k].val=0,void();
		pushdown(k);
		miku(ls,l,mid,x);
		miku(rs,mid+1,r,x);
	}
	LL query(LL k,LL l,LL r,LL x)
	{
		if(l>x||r<x) return 0;
		if(l==r) return t[k].val;
		pushdown(k);
		return max(query(ls,l,mid,x),query(rs,mid+1,r,x));
	}
	void solve()
	{
		for(int i=1;i<=n;i++) zsw[i]=0,ad[i].clear();
		for(int i=1;i<=d;i++) miku(1,1,d,i);
		sort(a+1,a+d+1,cmp);
		for(LL i=1;i<=d;i++) zsw[a[i].l]=max(zsw[a[i].l],i);
		for(int i=1;i<=n;i++) zsw[i]=max(zsw[i],zsw[i-1]);
		for(int i=1;i<=d;i++) ad[a[i].r].push_back(i);
		for(int i=1;i<=n;i++)
		{
			for(auto j:ad[i]) miku(1,1,d,j);
			for(auto j:L[i]) 
				modify(1,1,d,zsw[j.first]+1,zsw[i],f[j.first]+j.second+g[i]);
		}
		for(int i=1;i<=d;i++)
			ans[a[i].id]=max(ans[a[i].id],query(1,1,d,i));
	}
}
using namespace SegT;
int main()
{
	scanf("%lld%lld%lld",&n,&m,&d);
	for(int i=1;i<=m;i++)
	{
		LL l,r,v;
		scanf("%lld%lld%lld",&l,&r,&v);
		L[r].push_back({l,v});
		R[l].push_back({r,v});
	}
	for(int i=1;i<=n;i++,f[i]=f[i-1])
		for(auto j:L[i]) f[i]=max(f[i],f[j.first]+j.second);
	for(int i=n;i>=1;i--,g[i]=g[i+1])
		for(auto j:R[i]) g[i]=max(g[i],g[j.first]+j.second);
	for(int i=1;i<=n;i++) st[i][0]=f[i]+g[i];
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);
	for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=d;i++)
	{
		LL l,r,v;
		scanf("%lld%lld%lld",&l,&r,&v);
		a[i]=(zxz){l,r,i};
		ans[i]=max(f[l]+v+g[r],query(l+1,r-1));
	}
	solve();
	reverse(f+1,f+n+1);
	reverse(g+1,g+n+1);
	swap(f,g);
	for(int i=1;i<=n;i++) L[i].clear();
	for(int i=1;i<=n;i++)
		for(auto j:R[i])
			L[n-i+1].push_back({n-j.first+1,j.second});
	for(int i=1;i<=d;i++) a[i]=(zxz){n-a[i].r+1,n-a[i].l+1,a[i].id};
	solve();
	for(int i=1;i<=d;i++) printf("%lld\n",ans[i]);
	return 0;
}

【题解】「MSTOI-R1」超速检测II

文章操作

相关推荐

评论

【题解】「MSTOI-R1」超速检测II