题目描述
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。
输入:
第一行是两个数N,M。
第二行有M个数,第i个数Oi表示第i段轨道上有第Oi个国家的太空站。
第三行有N个数,第i个数Pi表示第i个国家希望收集的陨石数量。
第四行有一个数K,表示BIU预测了接下来的K场陨石雨。
接下来K行,每行有三个数Li,Ri,Ai,表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中(如果Li<=Ri,就是Li,Li+1,...,Ri,否则就是Ri,Ri+1,...,m-1,m,1,...,Li),向区间中的每个太空站提供Ai单位的陨石样本。
输出:
N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到,输出NIE。
数据范围:
输入
输出
样例输入
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
样例输出
NIE
1
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
vector<int>q[300010];
int n,m,k,x;
ll v[300010];
int ans[300010];
int s[300010];
struct lty
{
int l,r,val;
}a[300010];
int c[300010];
int b[300010];
int now;
void add(int x,int val)
{
for(int i=x;i<=m;i+=i&-i)
{
v[i]+=1ll*val;
}
}
ll ask(int x)
{
ll res=0;
for(int i=x;i;i-=i&-i)
{
res+=v[i];
}
return res;
}
void change(int id,int opt)
{
if(a[id].l<=a[id].r)
{
add(a[id].l,opt*a[id].val);
add(a[id].r+1,-1*opt*a[id].val);
}
else
{
add(1,opt*a[id].val);
add(a[id].r+1,-1*opt*a[id].val);
add(a[id].l,opt*a[id].val);
}
}
void solve(int l,int r,int L,int R)
{
if(L>R)
{
return ;
}
if(l==r)
{
for(int i=L;i<=R;i++)
{
ans[c[i]]=l;
}
return ;
}
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++)
{
change(i,1);
}
int ql=L,qr=R;
for(int i=L;i<=R;i++)
{
ll res=0;
int len=q[c[i]].size();
for(int j=0;j<len;j++)
{
res+=ask(q[c[i]][j]);
if(res>=s[c[i]])
{
break;
}
}
if(res>=s[c[i]])
{
b[ql++]=c[i];
}
else
{
b[qr--]=c[i];
s[c[i]]-=res;
}
}
for(int i=L;i<=R;i++)
{
c[i]=b[i];
}
for(int i=l;i<=mid;i++)
{
change(i,-1);
}
solve(l,mid,L,ql-1),solve(mid+1,r,ql,R);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
q[x].push_back(i);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i]);
c[i]=i;
}
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
}
solve(1,k+1,1,n);
for(int i=1;i<=n;i++)
{
printf(ans[i]>k?"NIE\n":"%d\n",ans[i]);
}
}
还有一种写法就是维护一个指针$now$表示当前加入了第$[1,now]$场的陨石雨,每次二分时移动$now$指针即可,但这样做的话被放在右区间的国家的$k$就不能减掉当次询问的答案了。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
vector<int>q[300010];
int n,m,k,x;
ll v[300010];
int ans[300010];
int s[300010];
struct lty
{
int l,r,val;
}a[300010];
int c[300010];
int b[300010];
int now;
void add(int x,int val)
{
for(int i=x;i<=m;i+=i&-i)
{
v[i]+=1ll*val;
}
}
ll ask(int x)
{
ll res=0;
for(int i=x;i;i-=i&-i)
{
res+=v[i];
}
return res;
}
void change(int id,int opt)
{
if(a[id].l<=a[id].r)
{
add(a[id].l,opt*a[id].val);
add(a[id].r+1,-1*opt*a[id].val);
}
else
{
add(1,opt*a[id].val);
add(a[id].r+1,-1*opt*a[id].val);
add(a[id].l,opt*a[id].val);
}
}
void solve(int l,int r,int L,int R)
{
if(L>R)
{
return ;
}
if(l==r)
{
for(int i=L;i<=R;i++)
{
ans[c[i]]=l;
}
return ;
}
int mid=(l+r)>>1;
while(now<mid)
{
now++;
change(now,1);
}
while(now>mid)
{
change(now,-1);
now--;
}
int ql=L,qr=R;
for(int i=L;i<=R;i++)
{
ll res=0;
int len=q[c[i]].size();
for(int j=0;j<len;j++)
{
res+=ask(q[c[i]][j]);
if(res>=s[c[i]])
{
break;
}
}
if(res>=s[c[i]])
{
b[ql++]=c[i];
}
else
{
b[qr--]=c[i];
}
}
for(int i=L;i<=R;i++)
{
c[i]=b[i];
}
solve(l,mid,L,ql-1),solve(mid+1,r,ql,R);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
q[x].push_back(i);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i]);
c[i]=i;
}
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
}
solve(1,k+1,1,n);
for(int i=1;i<=n;i++)
{
printf(ans[i]>k?"NIE\n":"%d\n",ans[i]);
}
}
BZOJ2527[Poi2011]Meteors——整体二分+树状数组的更多相关文章
-
BZOJ2527 [Poi2011]Meteors 整体二分 树状数组
原文链接http://www.cnblogs.com/zhouzhendong/p/8686460.html 题目传送门 - BZOJ2527 题意 有$n$个国家. 太空里有$m$个太空站排成一个圆 ...
-
【bzoj2527】[Poi2011]Meteors 整体二分+树状数组
题目描述 有N个成员国.现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站. 这个星球经常会下陨石雨.BIU已经预测了接下来K场陨石雨的情况.BI ...
-
【BZOJ-2527】Meteors 整体二分 + 树状数组
2527: [Poi2011]Meteors Time Limit: 60 Sec Memory Limit: 128 MBSubmit: 831 Solved: 306[Submit][Stat ...
-
BZOJ 2527 [Poi2011]Meteors (整体二分+树状数组)
整体二分板题,没啥好讲的-注意是个环-还有所有贡献会爆longlong,那么只要在加之前判断一下有没有达到需要的值就行了- CODE #include <set> #include < ...
-
bzoj 2527 Meteors - 整体二分 - 树状数组
Description Byteotian Interstellar Union (BIU) has recently discovered a new planet in a nearby gala ...
-
BZOJ 2527 [POI2011]MET-Meteors (整体二分+树状数组)
题目大意:略 洛谷传送门 整体二分裸题 考虑只有一个国家的情况如何处理 对询问数量二分答案,暴力$O(m)$打差分,求前缀和验证,时间是$O(mlogK)$ 如果有$n$个国家,就是$O(nmlogK ...
-
【BZOJ3110】【整体二分+树状数组区间修改/线段树】K大数查询
Description 有N个位置,M个操作.操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位 ...
-
BZOJ_3110_[Zjoi2013]K大数查询_整体二分+树状数组
BZOJ_3110_[Zjoi2013]K大数查询_整体二分+树状数组 Description 有N个位置,M个操作.操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位 ...
-
【bzoj3110】[Zjoi2013]K大数查询 整体二分+树状数组区间修改
题目描述 有N个位置,M个操作.操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c.如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数 ...
随机推荐
-
checkBox控件的CheckedChanged与CheckedStateChanged区别
Checked属性为bool类型,CheckState属性为枚举类型(CheckState.Checked.CheckState.Unchecked和CheckState.Indeterminate) ...
-
linux sort 用法
sort命令是帮我们依据不同的数据类型进行排序,其语法及常用参数格式: sort [-bcfMnrtk][源文件][-o 输出文件]补充说明:sort可针对文本文件的内容,以行为单位来排序. 参 数: ...
-
使用response实现文件下载注意点
创建web工程,使用response实现文件的下载. 在webRoot下创建download文件,里面包含要下载的文件,现在把源码贴上来,然后再说我遇到的问题 public class DownLoa ...
-
端口扫描命令nmap
转:http://www.osyunwei.com/archives/2004.html 下面教大家在CentOS中用nmap查看主机端口: 一.安装nmap yum install nmap -y ...
-
设计模式系列之装饰模式(Decorator Pattern)
装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其结构.这种类型的设计模式属于结构型模式,它是作为现有的类的一个包装.这种模式创建了一个装饰类,用来包装原 ...
-
在MyEclipse中使用spring-boot+mybatis+freemarker实现基本的增删改查
一.基本环境 二.创建实体类 1.User.java package bjredcross.rainbowplans.model; import bjredcross.rainbowplans.com ...
-
通过Pdf预览Excel或者word或者Powerpoint (C#将Office转换为PDF)
下面代码是Excel转换为PDF using System; using System.Collections.Generic; using System.Linq; using System.Web ...
-
mysql批量插入
有多种方式 其中效率高 要求低的方式 是 把sql拼接出来 后一次性commit: eg: public int insertBatch(List<PeccDetailModel> lis ...
-
(转)Fur Shader
转自:http://qiankanglai.me/misc/2014/11/15/fur-shader/ 花时间看了下毛发效果,苦于囊中羞涩没能买QuickFur.furFX等插件,最后找到了Fur ...
-
Conda / Miniconda——软件包管理系统使用
conda是一个非常好的python包管理软件,但是它的Minicoda是一个非常好的生信软件包管理软件,更多conda介绍多google. Miniconda简直就是生信人的福音,尤其是像我这种传统 ...