专栏文章

社论：P14348 [JOISC 2019] 穿越时空 Bitaro / Bitaro, who Leaps through Time

JJordan_Pan
P14348题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min13bxh
此快照首次捕获于
2025/12/01 18:50
3 个月前
此快照最后确认于
2025/12/01 18:50
3 个月前
查看原文

0

被神秘双半群构造吓哭了，我怎么只会汤包了的无脑做法。（但是本质相同？）
qoj 代码长度倒四，但是两个 log⁡\log 最优解 hyw？

1

感性理解一下，走回头路一定是不优的。
然后就可以 O(qn)O(qn) 的贪心，每次如果不在合法区间内，就走到更近的那个区间端点。
不妨把询问分成 l<rl<r 和 l>rl>r 两种，后者只需要把前者反过来做就好了。于是只考虑从左往右走。
令 Li←Li−i+1,Ri←Ri−iL_i\leftarrow L_i-i+1,R_i\leftarrow R_i-i 以忽略从 ii 到 i+1i+1 需要的 11 单位时间，并且给 RiR_i 额外减了 11 这样只有在区间内的位置才能走过去。
手动模拟以下这个过程，发现把整个值域从 ll 到 rr 的过程，一定是左右端点不断被缩减，中间的位于当前所有经过的区间交集内的位置不变；直到交集为空，整个值域被压缩成一个点。
如图，竖线为题目给的区间，横线为路径，其中红色的需要代价。在第四条竖线处，所有起点都被压缩到了一个点上。
于是可以考虑弹飞绵羊，对序列分块，修改时整块倒过来做区间加等差数列计算代价，复杂度大概是根号 log。
然后我们发现，在这个压成一个点的分界点之前的代价是好算的，就是走到区间交集；压成一个点之后的代价可以直接算这个点的走的代价。
于是我们在线段树上模拟这个过程。

2

具体地，对于节点 [L,R][L,R]，记 pospos 为使得值域被压缩成一个点的位置（即区间区间 [L,pos−1][L,pos-1] 的交集不为空，而 [L,pos][L,pos] 的交集为空），[l,r][l,r] 为区间区间 [L,pos−1][L,pos-1] 的交集，还有从 pospos 走到 RR 的代价，以及走完后的位置。
我们设计一个函数 calc(p,x)calc(p,x) 为位置 pp 走过 xx 需要的代价，可以拆成三个部分：压缩前，从 pos−1pos-1 到 pospos，压缩后，加在一起。
线段树拆出来 O(log⁡n)O(\log n) 个区间分别做这个函数，位置的变化是简单的。
于是现在只需要写出来 Pushup() 就做完这个题了。
这里我分了三类讨论：左子结点的区间交集为空（即已经能够压缩），左子结点的区间交集不为空并且左右子结点的 [l,r][l,r] 有交，左子结点的区间交集不为空并且左右子结点的 [l,r][l,r] 无交。
对于最后一种情况需要求出新的 pospos，我使用了二分解决。可能有更牛的求法但是能过。
所以复杂度为 O(nlog⁡2n)O(n\log^2n)。

3

反过来的部分把整个线段树复制了一遍，代码长度 4k。
代码CPP
#include<bits/stdc++.h>
constexpr int rSiz=1<<21;
char rBuf[rSiz],*p1=rBuf,*p2=rBuf;
#define gc() (p1==p2&&(p2=(p1=rBuf)+fread(rBuf,1,rSiz,stdin),p1==p2)?EOF:*p1++)
template<class T>void rd(T&x){
	char ch=gc();
	for(;ch<'0'||ch>'9';ch=gc());
	for(x=0;ch>='0'&&ch<='9';ch=gc())
		x=(x<<1)+(x<<3)+(ch^48);
}
constexpr int _=3e5+5,inf=2e9;
int n,q;
int C(int x,int l,int r){
	if(x>r)return r;
	else if(x<l)return l;
	else return x;
}
#define mid ((l+r)>>1)
struct D1{
	int a[_],b[_];
	struct node{int l,r,pos,y;long long val;}t[_<<2];
	long long calc(int p,node x){
		return std::max(p-x.r,0)+(x.pos?std::max(C(p,x.l,x.r)-b[x.pos],0):0)+x.val;
	}
	void Pup(int x,int l,int r){
		node ls=t[x<<1],rs=t[x<<1|1];
		if(ls.pos){
			t[x].l=ls.l;t[x].r=ls.r;t[x].pos=ls.pos;
			if(rs.pos)t[x].y=rs.y;
			else t[x].y=C(ls.y,rs.l,rs.r);
			t[x].val=ls.val+calc(ls.y,rs);
		}
		else if(ls.r<rs.l||ls.l>rs.r){
			t[x].l=ls.l;t[x].r=ls.r;
			for(int y=(x<<1|1),L=mid+1,R=r;;){
				if(L==R){t[x].pos=L;break;}
				if(t[y<<1].r<ls.l||t[y<<1].l>ls.r)R=(L+R)>>1,y<<=1;
				else{
					t[x].l=std::max(t[x].l,t[y<<1].l);
					t[x].r=std::min(t[x].r,t[y<<1].r);
					L=((L+R)>>1)+1,y=y<<1|1;
				}
			}
			int w=C(t[x].l,a[t[x].pos],b[t[x].pos]);
			t[x].val=calc(w,rs);
			if(rs.pos)t[x].y=rs.y;
			else t[x].y=C(w,rs.l,rs.r);
		}
		else{
			t[x].l=std::max(ls.l,rs.l);
			t[x].r=std::min(ls.r,rs.r);
			t[x].pos=rs.pos;t[x].y=rs.y;t[x].val=rs.val;
		}
	}
	void Chg(int x,int l,int r,int w){
		if(l==r)return t[x]={a[w],b[w],0,0,0},void();
		if(w<=mid)Chg(x<<1,l,mid,w);
		else Chg(x<<1|1,mid+1,r,w);
		Pup(x,l,r);
	}
	int pos;long long ans;
	void Qry(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R){
			ans+=calc(pos,t[x]);
			if(t[x].pos)pos=t[x].y;
			else pos=C(pos,t[x].l,t[x].r);
			return;
		}
		if(L<=mid)Qry(x<<1,l,mid,L,R);
		if(R>mid)Qry(x<<1|1,mid+1,r,L,R);
	}
	void Upd(int x,int l,int r){
		a[x]=l+n-x+1,b[x]=r+n-x;
		Chg(1,1,n,x);
	}
	long long Ask(int l,int r,int x,int y){
		x=x+n-l+1;y=y+n-r+1;
		pos=x;ans=0;
		Qry(1,1,n,l,r-1);
		return ans+std::max(pos-y,0);
	}
}D1;
struct D2{
	int a[_],b[_];
	struct node{int l,r,pos,y;long long val;}t[_<<2];
	long long calc(int p,node x){
		return std::max(p-x.r,0)+(x.pos?std::max(C(p,x.l,x.r)-b[x.pos],0):0)+x.val;
	}
	void Pup(int x,int l,int r){
		node ls=t[x<<1],rs=t[x<<1|1];
		if(ls.pos){
			t[x].l=ls.l;t[x].r=ls.r;t[x].pos=ls.pos;
			if(rs.pos)t[x].y=rs.y;
			else t[x].y=C(ls.y,rs.l,rs.r);
			t[x].val=ls.val+calc(ls.y,rs);
		}
		else if(ls.r<rs.l||ls.l>rs.r){
			t[x].l=ls.l;t[x].r=ls.r;
			for(int y=(x<<1|1),L=mid+1,R=r;;){
				if(L==R){t[x].pos=L;break;}
				if(t[y<<1].r<ls.l||t[y<<1].l>ls.r)R=(L+R)>>1,y<<=1;
				else{
					t[x].l=std::max(t[x].l,t[y<<1].l);
					t[x].r=std::min(t[x].r,t[y<<1].r);
					L=((L+R)>>1)+1,y=y<<1|1;
				}
			}
			int w=C(t[x].l,a[t[x].pos],b[t[x].pos]);
			t[x].val=calc(w,rs);
			if(rs.pos)t[x].y=rs.y;
			else t[x].y=C(w,rs.l,rs.r);
		}
		else{
			t[x].l=std::max(ls.l,rs.l);
			t[x].r=std::min(ls.r,rs.r);
			t[x].pos=rs.pos;t[x].y=rs.y;t[x].val=rs.val;
		}
	}
	void Chg(int x,int l,int r,int w){
		if(l==r)return t[x]={a[w],b[w],0,0,0},void();
		if(w<=mid)Chg(x<<1,l,mid,w);
		else Chg(x<<1|1,mid+1,r,w);
		Pup(x,l,r);
	}
	int pos;long long ans;
	void Qry(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R){
			ans+=calc(pos,t[x]);
			if(t[x].pos)pos=t[x].y;
			else pos=C(pos,t[x].l,t[x].r);
			return;
		}
		if(L<=mid)Qry(x<<1,l,mid,L,R);
		if(R>mid)Qry(x<<1|1,mid+1,r,L,R);
	}
	void Upd(int x,int l,int r){
		a[x]=l+n-x+1,b[x]=r+n-x;
		Chg(1,1,n,x);
	}
	long long Ask(int l,int r,int x,int y){
		x=x+n-l+1;y=y+n-r+1;
		pos=x;ans=0;
		Qry(1,1,n,l,r-1);
		return ans+std::max(pos-y,0);
	}
}D2;
int main(){
	rd(n),rd(q);
	for(int i=1,l,r;i<n;++i){
		rd(l),rd(r);
		D1.Upd(i,l,r);
		D2.Upd(n-i,l,r);
	}
	for(int op,x,y,l,r;q;--q){
		rd(op);
		if(op&1){
			rd(x),rd(l),rd(r);
			D1.Upd(x,l,r);
			D2.Upd(n-x,l,r);
		}
		else{
			rd(l),rd(x),rd(r),rd(y);
			long long ans;
			if(l==r)ans=std::max(x-y,0);
			else if(l<r)ans=D1.Ask(l,r,x,y);
			else ans=D2.Ask(n-l+1,n-r+1,x,y);
			printf("%lld\n",ans);
		}
	}
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...