首页 > 代码库 > BZOJ 4631: 踩气球

BZOJ 4631: 踩气球

2024-09-08 09:53:44   214人阅读

4631: 踩气球

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 275  Solved: 140
[Submit][Status][Discuss]

Description

六一儿童节到了， SHUXK 被迫陪着M个熊孩子玩一个无聊的游戏：有N个盒子从左到右排成一排，第i个盒子里装着Ai个气球。
SHUXK 要进行Q次操作，每次从某一个盒子里拿出一个没被踩爆的气球，然后熊孩子们就会立刻把它踩爆。
这M个熊孩子每个人都指定了一个盒子区间[Li, Ri]。 如果某一个时刻，一个熊孩子发现自己选定的盒子区间[Li, Ri]中的所
有气球都已经被踩爆了，他就会非常高兴（显然之后他一直会很高兴）。
为了不辜负将自己的任务强行塞给 SHUXK 的那个人的期望， SHUXK 想向你询问： 
他每次操作过后会有多少个熊孩子很高兴。

Input

第一行包含两个正整数N和M，分别表示盒子和熊孩子的个数。
第二行包含N个正整数Ai（ 1 < = Ai < = 10^5），表示每个盒子里气球的数量。
以下M行每行包含两个正整数Li, Ri（ 1 < = Li < = Ri < = N），分别表示每一个熊孩子指定的区间。
以下一行包含一个正整数Q，表示 SHUXK 操作的次数。
以下Q行每行包含一个正整数X，表示这次操作是从第X个盒子里拿气球。为
了体现在线，我们对输入的X进行了加密。
假设输入的正整数是x‘，那么真正的X = (x‘ + Lastans − 1)Mod N + 1。其
中Lastans为上一次询问的答案。对于第一个询问， Lastans = 0。
输入数据保证1 < = x‘ < = 10^9， 且第X个盒子中有尚未被踩爆的气球。
N < = 10^5 ,M < = 10^5 ?,Q < = 10^5

Output

包含Q行，每行输出一个整数，表示 SHUXK 一次操作后询问的
答案。答案的顺序应与输入数据的顺序保持一致。

Sample Input

5 3
1 1 1 1 1
5 5
2 2
1 3
5
4
2
5
2
3

Sample Output

0
1
1
2
3
【样例说明】
实际上每次操作的盒子是： 4 2 1 3 5
在第二次操作后，第二个熊孩子会高兴 （区间[2,2]中的气球已经全部被踩爆）。
在第四次操作后，第三个熊孩子会高兴（区间[1,3]中的气球已经全部被踩爆）。
在第五次操作后，第一个熊孩子会高兴（区间[5,5]中的气球已经全部被踩爆）。

HINT

Source

分析：

我一开始看成离线的了...然后这不是水水嘛，就开始写，发现是在线QwQ~~~

既然我们必须每一次去查询当前区间全部为0的区间个数有多少个，我们不妨计算每次新增了多少个区间，考虑每一次把一个盒子变为空，就会合并前后两个全0区间，那么当前的点对新增答案的贡献就是左端点位于[包含当前点的极大0区间左端点，当前点]并且右端点位于[当前点，包含当前点的极大子区间的右端点]的区间个数，那么我们维护一个可持久化线段树，每个可持久化线段树中维护右端点位于某个点的区间个数，然后每一次二分合法左端点区间的可持久化线段树，然后查询合法右端点区间个数，更新答案就好了...

代码：

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThornusing namespace std;const int maxn=100000+5,maxm=7000000+5;int n,m,Q,ans,tot,a[maxn],ls[maxm],rs[maxm],sum[maxm],root[maxn],fapre[maxn],fanxt[maxn];struct M{		int l,r;		friend bool operator < (M a,M b){		if(a.l!=b.l)			return a.l<b.l;		return a.r<b.r;	}	}q[maxn];inline int findpre(int x){	return fapre[x]==x?x:fapre[x]=findpre(fapre[x]);}inline int findnxt(int x){	return fanxt[x]==x?x:fanxt[x]=findnxt(fanxt[x]);}inline void change(int l,int r,int pos,int x,int &y){	y=++tot;sum[y]=sum[x]+1;	if(l==r)		return;	int mid=(l+r)>>1;ls[y]=ls[x];rs[y]=rs[x];	if(pos<=mid)		change(l,mid,pos,ls[x],ls[y]);	else		change(mid+1,r,pos,rs[x],rs[y]);}inline int query(int l,int r,int L,int R,int x,int y){	if(l==L&&r==R)		return sum[y]-sum[x];	int mid=(l+r)>>1;	if(R<=mid)		return query(l,mid,L,R,ls[x],ls[y]);	else if(L>mid)		return query(mid+1,r,L,R,rs[x],rs[y]);	else		return query(l,mid,L,mid,ls[x],ls[y])+query(mid+1,r,mid+1,R,rs[x],rs[y]);}inline int findgreater(int x){	int l=1,r=m,res=n+1;	while(l<=r){		int mid=(l+r)>>1;		if(q[mid].l>=x)			res=mid,r=mid-1;		else			l=mid+1;	}	return res;}inline int findlower(int x){	int l=1,r=m,res=0;	while(l<=r){		int mid=(l+r)>>1;		if(q[mid].l<=x)			res=mid,l=mid+1;		else			r=mid-1;	}	return res;}signed main(void){	scanf("%d%d",&n,&m);fanxt[n+1]=n+1;	for(int i=1;i<=n;i++)		scanf("%d",&a[i]),fapre[i]=i,fanxt[i]=i;	for(int i=1;i<=m;i++)		scanf("%d%d",&q[i].l,&q[i].r);	sort(q+1,q+m+1);scanf("%d",&Q);ans=0;	for(int i=1;i<=m;i++)		change(1,n,q[i].r,root[i-1],root[i]);	for(int i=1,pos,x,y,l,r;i<=Q;i++){		scanf("%d",&pos);pos=(pos+ans-1)%n+1;		a[pos]--;		if(a[pos]!=0) {printf("%d\n",ans);continue;}		x=findpre(pos-1)+1;		y=findnxt(pos+1)-1;		fapre[pos]=pos-1;		fanxt[pos]=pos+1;		l=findgreater(x);		r=findlower(pos);		if(l<=r)			ans+=query(1,n,pos,y,root[l-1],root[r]);		printf("%d\n",ans);	}	return 0;}

　　

By NeighThorn

BZOJ 4631: 踩气球


联系
我们