首页 > 其他 > 详细

2018牛客网暑假ACM多校训练赛(第六场)I Team Rocket 线段树

时间:2018-08-04 23:57:49      阅读:301      评论:0      收藏:0      [点我收藏+]

原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round6-I.html

题目传送门 - https://www.nowcoder.com/acm/contest/144/I

题意

  给定 $n$ 条线段,第 $i$ 条线段覆盖区间 $[L_i,R_i]$ 。

  接下来 $m$ 次操作,每次操作给出一个坐标 $x$ ,使得所有覆盖到坐标 $x$ 的区间都消失。(如果之前已经消失了,那么现在就不能让他再消失一次了)

  对于每一次操作,输出这次操作使得多少线段消失了。

  接下来对于每一个线段,输出它是在第几次操作消失的。如果它没有消失,那么输出 $0$ 。

  强制在线。方式:对于每一次操作,输入的是一个数 $y$ ,$x = y\ {\rm XOR} \ lastans$ 。其中 $lastans$ 表示上一次操作时消失的线段的编号的乘积对于 $998244353$ 取模后的值;如果上一次没有使任何线段消失或者当前这次操作是第一次,则 $lastans=0$ 。

  多组数据。共 $T$ 组。

  $1\leq T\leq 5,1\leq n,m\leq 2\times 10^5,-10^9\leq L_i,R_i,x\leq 10^9 $

题解

  线段树。

  首先对于坐标离散化一下。然后,在线段树上面覆盖每一条线段,于是每一条线段会被拆成 $\log n$ 条,覆盖在线段树上。

  具体地,在线段树上的操作就是对于每一个线段树节点开一个 vector , 然后把当前线段的编号扔进去。这个相当于线段树标记永久化。

  我们还要支持快速查找覆盖一个点的所有线段。这个就相当于线段树单点查询。可以见得,在单点查询的时候,每遇到一个代表的区间包含当前位置的线段树节点,这个节点的 vector 的元素都会消失。但是一个线段被拆成了 log 个,当他消失的时候,我们似乎需要修改所有的 log 个。这样显然是不行的。解决的办法:我们只需要对于每一个线段,打一个标记,记录这条线段是否已经消失。于是,如果我们在单点查询的时候遇到了已经被标记删除的线段,那么我们就不将他加入当前的答案序列中。

  再具体的看代码吧。

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

  我比较懒,离散化的时候用了比较懒的办法。于是常数不大好。注意一下,在清空 vector 的时候从后往前访问并 pop_back 会快一下。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=200005,mod=998244353;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)&&ch!=‘-‘)
		ch=getchar();
	if (ch==‘-‘)
		f=-1,ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+ch-48,ch=getchar();
	return x*f;
}
int n,m;
int vis[N],L[N],R[N],ans[N];
int Ha[N*4],hs;
vector <int> t[N*4*4];
void build(int rt,int L,int R){
	t[rt].clear();
	if (L==R)
		return;
	int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
	build(ls,L,mid);
	build(rs,mid+1,R);
}
void cover(int rt,int L,int R,int xL,int xR,int id){
	if (xL>R||xR<L)
		return;
	if (xL<=L&&R<=xR){
		t[rt].push_back(id);
		return;
	}
	int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
	cover(ls,L,mid,xL,xR,id);
	cover(rs,mid+1,R,xL,xR,id);
}
vector <int> res;
void Delete(int rt,int L,int R,int x){
	while (!t[rt].empty()){
		int id=t[rt].back();
		t[rt].pop_back();
		if (!vis[id])
			vis[id]=1,res.push_back(id);
	}
	if (L==R)
		return;
	int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;
	if (x<=mid)
		Delete(ls,L,mid,x);
	else
		Delete(rs,mid+1,R,x);
}
void solve(int Case){
	n=read(),m=read();
	hs=0;
	for (int i=1;i<=n;i++){
		L[i]=read(),R[i]=read();
		Ha[++hs]=L[i],Ha[++hs]=L[i]-1;
		Ha[++hs]=R[i],Ha[++hs]=R[i]-1;
	}
	Ha[++hs]=1e9+1;
	sort(Ha+1,Ha+hs+1);
	hs=unique(Ha+1,Ha+hs+1)-Ha-1;
	build(1,1,hs);
	for (int i=1;i<=n;i++){
		vis[i]=ans[i]=0;
		L[i]=lower_bound(Ha+1,Ha+hs+1,L[i])-Ha;
		R[i]=lower_bound(Ha+1,Ha+hs+1,R[i])-Ha;
		cover(1,1,hs,L[i],R[i],i);
	}
	printf("Case #%d:\n",Case);
	int last_ans=0;
	for (int k=1;k<=m;k++){
		int x=read()^last_ans;
		int p=lower_bound(Ha+1,Ha+hs+1,x)-Ha;
		res.clear();
		Delete(1,1,hs,p);
		if (res.size()>0){
			last_ans=1;
			for (int i=0;i<res.size();i++){
				int id=res[i];
				ans[id]=k;
				last_ans=1LL*last_ans*id%mod;
			}
		}
		else
			last_ans=0;
		printf("%d\n",(int)res.size());
	}
	for (int i=1;i<n;i++)
		printf("%d ",ans[i]);
	printf("%d\n",ans[n]);
}
int main(){
	for (int T=read(),Case=1;T;T--,Case++)
		solve(Case);
	return 0;
}

  

2018牛客网暑假ACM多校训练赛(第六场)I Team Rocket 线段树

原文:https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round6-I.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!