题解：P14268 [ROI 2015 Day2] 路灯

给一个完全不需要吉司机线段树的单

\log

做法。

思路

我们定义一个区间是好的当且仅当该区间中所有的路灯当前或者曾经某时都是正常的。

假设区间

[l,r]

是好的（满足

l<r

），那么显然区间

[l+1,r]

也是好的，所以对于一个右端点

r

来说，能够满足区间 $[l,r]$ 是好的的 $l$ 是一段连续的位置。

我们设

pre_i

表示满足区间 $[l,i]$ 是好的最小的 $l$ 再 $-1$ ，特别的，如果不存在这样的 $l$ ，则 $pre_i=i$ 。

那么我们每次修改后的答案就是：

\frac{n(n+1)}{2}-\sum pre_i

考虑如何用线段树维护

pre

。

在我们进行区间修复路灯区间

[l,r]

时，考虑找到满足

L\le l

且

r\le R

且

[L,R]

中路灯都是正常的极长区间

[L,R]

，则对于

i\in[L,R]

，我们显然想要让

pre_i\gets \min\{pre_i,L-1\}

，可以直接用吉司机线段树维护，但是我们不会吉司机线段树，怎么办？

不难发现， $pre_i$ 关于 $i$ 在任意时刻都是单调不降的。证明是简单的，考虑如果存在

r'>r

，则必然存在某个时刻满足

[pre_{r'}+1,r']

中路灯都是好的，所以

pre_r'

必然

\ge pre_{r}

。

所以对于一次修改，一定可以等价为对一段区间进行区间赋值，则我们可以在线段树上维护

pre

的区间

\max,\min

，然后进行线段树上二分，则单次修改的复杂度就是单

\log

的。

问题只剩下怎么找到极长区间

[L,R]

。对于区间修复操作，一定有

[l,r]\subseteq[L,R]

，所以我们可以从

l

开始向前找最长连续的

1

，从

r

开始向后找最长连续的

1

，维护方法参考线段树维护最大子段和的方法，在每个节点上记录前缀极长的

1

与后缀极长的

1

。修改时区间赋值

0/1

即可。

综上，时间复杂度

O(n\log n)

。

代码

CPP

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define lc (x<<1)
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
const ll N=3e5+10;
const ll INF=2147483647;
ll sum[N<<2],maxx[N<<2],minn[N<<2],tag[N<<2],a[N];
inline void push_up(ll x){
	maxx[x]=max(maxx[lc],maxx[rc]);
	minn[x]=min(minn[lc],minn[rc]);
	sum[x]=sum[lc]+sum[rc];
}
inline void push_down(ll x,ll l,ll r){
	if(tag[x]==INF) return;
	maxx[lc]=maxx[rc]=minn[lc]=minn[rc]=tag[lc]=tag[rc]=tag[x];
	sum[lc]=tag[x]*(mid-l+1),sum[rc]=tag[x]*(r-mid);
	tag[x]=INF;
}
void build(ll x,ll l,ll r){
	tag[x]=INF;
	if(l==r){sum[x]=maxx[x]=minn[x]=a[l];return;}
	build(lc,l,mid),build(rc,mid+1,r);push_up(x);
}
void chg(ll x,ll l,ll r,ll L,ll R,ll v){
	if(maxx[x]<=v) return;
	if(L<=l&&r<=R){
		if(minn[x]>=v){
			minn[x]=maxx[x]=tag[x]=v;
			sum[x]=v*(r-l+1);
			return;
		}
		else{
			push_down(x,l,r);
			chg(lc,l,mid,L,R,v);
			chg(rc,mid+1,r,L,R,v);
			push_up(x);
		}
		return;
	}
	push_down(x,l,r);
	if(L<=mid) chg(lc,l,mid,L,R,v);
	if(R>mid) chg(rc,mid+1,r,L,R,v);
	push_up(x);
}
ll query(ll x,ll l,ll r,ll L,ll R){
	if(L<=l&&r<=R) return sum[x];
	ll ret=0;push_down(x,l,r);
	if(L<=mid) ret+=query(lc,l,mid,L,R);
	if(R>mid) ret+=query(rc,mid+1,r,L,R);
	return ret;
}
ll n,q,cnt[N<<2],fug[N<<2],r1s[N<<2],l1s[N<<2];
string s;
void PU(ll x,ll l,ll r){
	cnt[x]=cnt[lc]+cnt[rc];
	if(l1s[lc]==mid-l+1) l1s[x]=l1s[lc]+l1s[rc];
	else l1s[x]=l1s[lc];
	if(r1s[rc]==r-mid) r1s[x]=r1s[rc]+r1s[lc];
	else r1s[x]=r1s[rc];
}
void PD(ll x,ll l,ll r){
	if(fug[x]==-1) return;
	fug[lc]=fug[rc]=fug[x];
	l1s[lc]=r1s[lc]=cnt[lc]=fug[x]*(mid-l+1);
	l1s[rc]=r1s[rc]=cnt[rc]=fug[x]*(r-mid);
	fug[x]=-1;
}
void B(ll x,ll l,ll r){
	fug[x]=-1;
	if(l==r){
		cnt[x]=s[l]-'0';
		l1s[x]=r1s[x]=cnt[x];
		return;
	}
	B(lc,l,mid),B(rc,mid+1,r);PU(x,l,r);
}
void modify(ll x,ll l,ll r,ll L,ll R,ll v){
	if(L<=l&&r<=R){
		fug[x]=v;
		l1s[x]=r1s[x]=cnt[x]=(r-l+1)*v;
		return;
	}
	PD(x,l,r);
	if(L<=mid) modify(lc,l,mid,L,R,v);
	if(R>mid) modify(rc,mid+1,r,L,R,v);
	PU(x,l,r);
}
ll getl(ll x,ll l,ll r,ll pos){
	if(r<=pos) return r1s[x];
	ll ret=0;PD(x,l,r);
	if(pos<=mid) return getl(lc,l,mid,pos);
	ret=getl(rc,mid+1,r,pos);
	if(ret==pos-mid) ret+=getl(lc,l,mid,pos);
	return ret;
}
ll getr(ll x,ll l,ll r,ll pos){
	if(pos<=l) return l1s[x];
	ll ret=0;PD(x,l,r);
	if(pos>mid) return getr(rc,mid+1,r,pos);
	ret=getr(lc,l,mid,pos);
	if(ret==mid-pos+1) ret+=getr(rc,mid+1,r,pos);
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q>>s;s=' '+s;
	for(ll i=1;i<=n;i++){
		if(s[i]=='1') a[i]=a[i-1];
		else a[i]=i;
	}
	build(1,1,n);B(1,1,n);
	ll ans=n*(n+1)/2;
	while(q--){
		ll l,r,opt;cin>>l>>r>>opt;
		if(opt==1){
			modify(1,1,n,l,r,1);
			ll lenl,lenr;
			lenl=getl(1,1,n,l);
			lenr=getr(1,1,n,r);
			l=l-lenl+1;r=r+lenr-1;
			chg(1,1,n,l,r,l-1);
		}
		else modify(1,1,n,l,r,0);
	}
	return 0;
}

题解：P14268 [ROI 2015 Day2] 路灯

文章操作

思路

代码

相关推荐

评论

题解：P14268 [ROI 2015 Day2] 路灯