UOJ #218. 【UNR #1】火车管理

Description

Solution

实际上添加问题就是一个线段树区间覆盖问题,打标记就好

对于弹栈操作比较难搞,实际上也就是一个历史查询,我们不需要保存栈中的每一个元素,我们通过查找历史状态就可以了

这样用主席树维护复杂度是 \(O(n*logn)\) 的

具体是这样的:

假设我们要弹出位置 \(x\) 的栈顶元素,那么在线段树中维护一个值 \(t\),表示最近的一次修改是 \(t\) 时刻

那么上上次修改就可以通过查询 \(t-1\) 时刻的 \(t\) 找出,相当于保存了一个前驱

用主席树维护这个时间就好了

注意内存有些卡,有一些技巧:

1.首先对于查询的线段树是全局的,不需要动态开点

2.对于线段树中的一个节点 \(x\) ,如果它的左右儿子都没有儿子,那么下一次做区间覆盖时,就不需要对 \(x\) 新建两个节点

#include<bits/stdc++.h>

#define lo (o<<1)

#define ro (o<<1|1)

using namespace std;

const int N=5e5+10;

int n,m,ty,rt[N],a[N],tt=0;

struct data{

	int ls,rs,lag;

	data(){lag=-1;}

}tr[N*130];

int T[N*4],la[N*4],in[N*130];

inline void pushdown(int o){

	if(tr[o].lag==-1)return ;

	int t=tr[o].lag;tr[o].lag=-1;

	if(!in[o] || in[tr[o].ls] || in[tr[o].rs]){

		tr[++tt]=tr[tr[o].ls];tr[o].ls=tt;

		tr[++tt]=tr[tr[o].rs];tr[o].rs=tt;in[o]=1;

	}

	int ls=tr[o].ls,rs=tr[o].rs;

	tr[ls].lag=t;tr[rs].lag=t;

}

inline void Push(int o,int l,int r){

	if(la[o]==-1)return ;

	int k=la[o],mid=(l+r)>>1;la[o]=-1;

	T[lo]=k*(mid-l+1);la[lo]=k;

	T[ro]=k*(r-mid);la[ro]=k;

}

inline void upd(int o){T[o]=T[lo]+T[ro];}

inline int qry(int o,int l,int r,int sa,int se){

	if(sa<=l && r<=se)return T[o];

	int mid=(l+r)>>1,ret=0;

	Push(o,l,r);

	if(se<=mid)ret=qry(lo,l,mid,sa,se);

	else if(sa>mid)ret=qry(ro,mid+1,r,sa,se);

	else ret=qry(lo,l,mid,sa,mid)+qry(ro,mid+1,r,mid+1,se);

	upd(o);

	return ret;

}

inline int qt(int x,int l,int r,int sa){

	if(l==r)return tr[x].lag;

	int mid=(l+r)>>1,ret=0;

	pushdown(x);in[x]=1;

	if(sa<=mid)ret=qt(tr[x].ls,l,mid,sa);

	else ret=qt(tr[x].rs,mid+1,r,sa);

	return ret;

}

inline void add(int o,int l,int r,int sa,int se,int t){

	if(sa<=l && r<=se){T[o]=(r-l+1)*t;la[o]=t;return ;}

	Push(o,l,r);

	int mid=(l+r)>>1;

	if(se<=mid)add(lo,l,mid,sa,se,t);

	else if(sa>mid)add(ro,mid+1,r,sa,se,t);

	else add(lo,l,mid,sa,mid,t),add(ro,mid+1,r,mid+1,se,t);

	upd(o);

}

inline void addtag(int &x,int l,int r,int sa,int se,int t){

	tr[++tt]=tr[x];x=tt;

	if(sa<=l && r<=se){tr[x].lag=t;return ;}

	pushdown(x);

	int mid=(l+r)>>1;in[x]=1;

	if(se<=mid)addtag(tr[x].ls,l,mid,sa,se,t);

	else if(sa>mid)addtag(tr[x].rs,mid+1,r,sa,se,t);

	else addtag(tr[x].ls,l,mid,sa,mid,t),addtag(tr[x].rs,mid+1,r,mid+1,se,t);

}

int main(){

	freopen("railway.in","r",stdin);

	freopen("railway.out","w",stdout);

	cin>>n>>m>>ty;

	int op,l,r,ans=0,x,y;

	memset(la,-1,sizeof(la));

	for(int i=1;i<=m;i++){

		rt[i]=rt[i-1];

		scanf("%d%d",&op,&l);

		l=(l+ans*ty)%n+1;

		if(op==1){

			scanf("%d",&r);

			r=(r+ans*ty)%n+1;

			if(l>r)swap(l,r);

			printf("%d\n",ans=qry(1,1,n,l,r));

		}

		else if(op==2){

			x=qt(rt[i],1,n,l);

			if(x){

				y=qt(rt[x-1],1,n,l);

				addtag(rt[i],1,n,l,l,y);add(1,1,n,l,l,a[y]);

			}

		}

		else if(op==3){

			scanf("%d%d",&r,&a[i]);

			r=(r+ans*ty)%n+1;

			if(l>r)swap(l,r);

			add(1,1,n,l,r,a[i]);

			addtag(rt[i],1,n,l,r,i);

		}

	}

	return 0;

}

巴特西

UOJ #218. 【UNR #1】火车管理

Description

Solution

最新文章

热门文章