BZOJ4631 踩气球

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4631

对序列建一棵线段树,将熊孩子的区间拆成logn个,在对应的结点上用vector记录下来,每个结点还要维护区间和

对于一次操作,查看它影响的logn个结点是否区间和变为0,维护对应的熊孩子区间

时空复杂度均为O(nlogn),

 

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node{
	long long sum;
	node(){sum=0;}
	vector<int>Q;
}t[maxn<<2];
int lans=0,ans=0;
int n,m,q;
int a[maxn];
#define ls i<<1
#define rs i<<1|1
#define lson i<<1,l,(l+r)/2
#define rson i<<1|1,(l+r)/2+1,r
int len[maxn];
void rz(int i,int l,int r){
	if(l!=r)t[i].sum=t[ls].sum+t[rs].sum;
	if(t[i].sum==0){
		for(int j=0;j<t[i].Q.size();j++){
			int id=t[i].Q[j];
			len[id]-=r-l+1;
			if(!len[id])ans++;
		}
		t[i].Q.clear();
	}
}
void build(int i,int l,int r){
	if(l==r){
		t[i].sum=a[l];
		return;
	}
	build(lson);build(rson);
	rz(i,l,r);
}
void Add(int i,int l,int r,int l0,int r0,int id){
	if(l0<=l&&r0>=r){
		t[i].Q.push_back(id);
		return ;
	}
	if(l0<=(l+r)/2)Add(lson,l0,r0,id);
	if(r0>(l+r)/2)Add(rson,l0,r0,id);
	rz(i,l,r);
}
void D(int i,int l,int r,int x){
	if(l==r){
		t[i].sum--;
		rz(i,l,r);
		return;
	}	
	if(x<=(l+r)/2)D(lson,x);
	if(x>(l+r)/2)D(rson,x);
	rz(i,l,r);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int l,r;scanf("%d%d",&l,&r);
		len[i]=r-l+1;
		Add(1,1,n,l,r,i);
	}
	scanf("%d",&q);
	while(q--){
		int x;scanf("%d",&x);
		x=(x+lans-1)%n+1;
		D(1,1,n,x);
		printf("%d\n",lans=ans);
	}
	return 0;
}