当前位置: 代码迷 >> 综合 >> BZOJ 4631 踩气球
  详细解决方案

BZOJ 4631 踩气球

热度:33   发布时间:2024-01-19 02:08:21.0

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

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

线段树+链表~

说是链表,其实就是加边操作里面常用的那种记录fi和ne的方法。

用线段树维护区间和,同时记录在该节点所代表的区间的熊孩子数,当区间变为0时就判断目前是否要+1,这里用链表记录,更新起来很方便~

注意:

1.%n+1不是%(n+1);

2.数组要开大,线段树*4,链表*50;

3.RE的话很可能是线段树l和1弄混了。


#include<cstdio>
#include<iostream>
using namespace std;int n,m,l,r,a[100010],c[400040],num[100010],fi[400040],cnt,ans,x;struct node{int v,ne;
}d[5000001];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void build(int l,int r,int k)
{if(l==r){c[k]=a[l];return;}int mid=l+r>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);c[k]=c[k<<1]+c[k<<1|1];
}void add(int l,int r,int k,int u,int v,int z)
{if(l>=u && r<=v){d[++cnt]=(node){z,fi[k]};fi[k]=cnt;num[z]++;return;}int mid=l+r>>1;if(u<=mid) add(l,mid,k<<1,u,v,z);if(v>mid) add(mid+1,r,k<<1|1,u,v,z);
}void chan(int l,int r,int k,int u)
{c[k]--;if(!c[k]) for(int i=fi[k];i;i=d[i].ne) if(!(--num[d[i].v])) ans++;if(l==r) return;int mid=l+r>>1;if(u<=mid) chan(l,mid,k<<1,u);else chan(mid+1,r,k<<1|1,u);
}int main()
{n=read();m=read();for(int i=1;i<=n;i++) a[i]=read();build(1,n,1);for(int i=1;i<=m;i++) l=read(),r=read(),add(1,n,1,l,r,i);m=read();for(int i=1;i<=m;i++){x=read(),x=(x+ans-1)%n+1;chan(1,n,1,x);printf("%d\n",ans);}return 0;
}