P4215求助!!
查看原帖
P4215求助!!
365110
xuanyuan_Niubi楼主2021/2/3 21:46

这题一看我觉得就是一个单点修改和区间查询,但是为什么不对呢

#include<cstdio>
using namespace std;
const int M=1000005;
struct tree{
	int l,r,v;
}t[M<<2];
struct question{
	int l,r;
}qu[M];//把熊孩子的区间存起来
int n,m,q,last,a[M];
bool vis[M];//是标记这个熊孩子快乐吗
inline int read(){
	char c=getchar();int x=0;
	for(;c<'0'||c>'9';c=getchar());
	for(;c<='9'&&c>='0';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return x;
}
inline void push_up(int k){
	t[k].v=t[k<<1].v+t[k<<1|1].v;
}
inline void build(int l,int r,int k){
	t[k].l=l;
	t[k].r=r;
	if(l==r){
		t[k].v=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(1,mid,k<<1);
	build(mid+1,r,k<<1|1);
	push_up(k);
}
inline void update(int k,int x){//单点修改
	if(t[k].r<x||t[k].l>x)return ;
	if(t[k].l==t[k].r&&t[k].l==x){
		t[k].v--;
		return ;
	}
	int mid=t[k].l+t[k].r>>1;
	if(x<=mid)update(k<<1,x);
	else update(k<<1|1,x);
	push_up(k);
}
inline bool query(int l,int r,int k){//查询此区间里是否还有气球
	if(l<=t[k].l&&t[k].r<=r){
		return t[k].v;
	}
	int mid=t[k].l+t[k].r>>1;
	bool fl=false;
	if(l<=mid)fl=query(l,mid,k<<1);
	if(r>mid)fl=query(mid+1,r,k<<1|1);
	return fl;
}
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++){
		qu[i].l=read();
		qu[i].r=read();
	}
	q=read();
	for(int i=1;i<=q;i++){
		int x=read(),ans=0;
		x=(x+last-1)%n+1;
		for(int j=1;j<=m;j++){//枚举熊孩子
			if(!vis[j]){//如果他之前还不快乐
				if(!query(qu[j].l,qu[j].r,1)){//如果这个区间里面没有气球他快乐了
					ans++;
					vis[j]=true;
				}
			}
			else{//如果之前就快乐了
				ans++;
			}
		}
		last=ans;
		printf("%d\n",ans);
	}
	return 0;
}
2021/2/3 21:46
加载中...