BZOJ上内存小了会WA。。。。
线段树上挂链表。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 200500
using namespace std;
int n,m,a[maxn],x,y,now,root,d[maxn],ans=,q,r;
int ls[maxn<<],rs[maxn<<],g[maxn*],nxt[maxn*],go[maxn*],sum[maxn<<],cnt=,tot=;
void build(int &now,int left,int right)
{
now=++tot;
if (left==right)
{
sum[now]=;
return;
}
int mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
sum[now]=sum[ls[now]]+sum[rs[now]];
}
void modify(int now,int left,int right,int l,int r,int num)
{
if ((left==l) && (right==r))
{
d[num]++;
go[++cnt]=num;
nxt[cnt]=g[now];
g[now]=cnt;
return;
}
int mid=(left+right)>>;
if (r<=mid) modify(ls[now],left,mid,l,r,num);
else if (l>=mid+) modify(rs[now],mid+,right,l,r,num);
else
{
modify(ls[now],left,mid,l,mid,num);
modify(rs[now],mid+,right,mid+,r,num);
}
}
void change(int now,int left,int right,int pos)
{
sum[now]--;
if (!sum[now])
{
int t=g[now];
while (t)
{
d[go[t]]--;
if (!d[go[t]]) ans++;
t=nxt[t];
}
}
if (left==right) return;
int mid=(left+right)>>;
if (pos<=mid) change(ls[now],left,mid,pos);
else change(rs[now],mid+,right,pos);
}
int main()
{
memset(d,,sizeof(d));
memset(g,,sizeof(g));
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
scanf("%d",&a[i]);
build(root,,n);
for (int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
modify(root,,n,x,y,i);
}
scanf("%d",&q);
for (int i=;i<=q;i++)
{
scanf("%d",&r);
r=(r+ans-)%n+;
a[r]--;
if (!a[r]) change(root,,n,r);
printf("%d\n",ans);
}
return ;
}
BZOJ 4631 踩气球的更多相关文章
-
bzoj 4631: 踩气球 线段树合并
4631: 踩气球 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 265 Solved: 136[Submit][Status][Discuss] ...
-
bzoj 4631: 踩气球 线段树
题目: Description 六一儿童节到了, SHUXK *陪着M个熊孩子玩一个无聊的游戏:有N个盒子从左到右排成一排,第i个盒子里装着Ai个气球. SHUXK 要进行Q次操作,每次从某一个盒子 ...
-
【BZOJ 4631】4631: 踩气球 (线段树)
4631: 踩气球 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 316 Solved: 153 Description 六一儿童节到了, SHUX ...
-
【BZOJ-4631】踩气球 线段树 + STL
4631: 踩气球 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 224 Solved: 114[Submit][Status][Discuss] ...
-
noj算法 踩气球 回溯法
描述: 六一儿童节,小朋友们做踩气球游戏,气球的编号是1-100,两位小朋友各踩了一些气球,要求他们报出自己所踩气球的编号的乘积.现在需要你编一个程序来判断他们的胜负,判断的规则是这样的:如果两人都说 ...
-
【BZOJ4631】踩气球 链表+线段树+堆
[BZOJ4631]踩气球 Description 六一儿童节到了, SHUXK *陪着M个熊孩子玩一个无聊的游戏:有N个盒子从左到右排成一排,第i个盒子里装着Ai个气球. SHUXK 要进行Q次操 ...
-
bzoj4631踩气球
bzoj4631踩气球 题意: 有一个序列和一个区间集合,每次将序列中的一个数-1,求此时集合里有多少个区间和为0.序列大小≤100000,区间数≤100000,操作数≤100000. 题解: 此题解 ...
-
[Luogu P4215] 踩气球 (线段树)
题面 传送门:https://www.luogu.org/problemnew/show/P4215 Solution 这题十分有意思. 首先,我们可以先想想离线做法,因为在线做法可以从离线做法推出. ...
-
BZOJ4631 : 踩气球
将所有盒子插入链表,每当一个盒子变空时,从链表里删去它. 查一下它的前驱后继$pre,nxt$,那么$[pre+1,nxt-1]$都是空的. 每次对于$[A,B]$这段都为空,对小朋友按$R$维护线段 ...
随机推荐
-
BaaS API 设计规范
上个月写了一个团队中的 BaaS API 的设计规范,给大家分享下: 目录 1. 引言... 4 1.1. 概要... 4 1.2. 参考资料... 4 1.3. 阅读对象... 4 1.4. 术语解 ...
-
HTTP Session原理
深入理解HTTP Session session在web开发中是一个非常重要的概念,这个概念很抽象,很难定义,也是最让人迷惑的一个名词,也是最多被滥用的名字之一,在不同的场合,session一次的 ...
-
mybatils多次查询问题
@Options(flushCache = true, timeout = 20000)
-
iOS 平台开发OpenGL ES程序注意事项
本人最近从Android平台的OpenGL ES开发转到iOS平台的OpenGL ES开发,由于平台不同,所以开发中会有一些区别,再次列出需要注意的几点. 1.首先需要了解iOS主要开发框架,再次仅介 ...
-
Git与GitHub学习笔记(五)一次提交失败的记录
代码已经跟踪了,添加注释说明,但是总是添加不了 error: pathspec 'live-page'' did not match any file(s) known to git. 重复了好多遍, ...
-
OneNET麒麟座应用开发之七:控制采样电机
气体采样采用主动抽取气体的方式保证充足而平稳的气流,所以我们采用气泵抽取气体来完成. 1.设计概述 客户对这部分要求能够设定电机的速度,但并不需要动态调节.对电机的控制有很多方式,我们采用比较简单的方 ...
-
漫谈 C++ 虚函数 的 实现原理
文中讲述的原理是推理和探讨 , 和现实中的实现不一定完全相同 . C++ 的 虚函数 , 编译器 会 生成一个 虚函数表 . 虚函数表, 实际上是 编译器 在 内存 中 划定 的 一块 区域, 用于存 ...
-
基于ngx_lua的动态服务路由方案
基于ngx_lua的动态服务路由方案 http://geek.csdn.net/news/detail/131497
-
【Java基础】System的arraycopy方法拷贝数组
一.在System类中查看方法的定义 二.示例 public class SystemArrayCopyTest { /** * @Description: System的arrayCopy方法测试 ...
-
Python数据类型-列表(list)增删改查
1.添加元素 添加单个元素:使用append(object)函数可以为列表添加单个元素,参数object为对象:也就是说所有Python的对象都可以添加到列表中. 添加多个元素(合并列表):使用ext ...