【BZOJ2527】[Poi2011]Meteors
Description
这个星球经常会下陨石雨。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。
数据范围:
Input
Output
Sample Input
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
Sample Output
NIE
1
题解:“整体二分就是对答案的cdq分治”
我们在cdq分治的过程中,不断将询问分成两个部分,在mid前能完成的放在左边,不能完成的放在右边,然后继续递归处理询问,直到递归结束,就能得出答案。
整体二分的核心部分在于保存一个指针(或数组),记录当前的状态,然后向当前的状态中不断添加(或删除)操作,从而得到另一个状态(说的不太具体,详见代码第42-43行)
当然不是所有的整体二分都可以做到这一点(比如只能添加不能删除)
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,now,K;
const int maxn=300010;
typedef long long ll;
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int next[maxn],head[maxn];
ll s[maxn],P[maxn],qa[maxn],cur[maxn];
int p[maxn],q[maxn],ql[maxn],qr[maxn],ans[maxn];
void updata(int x,ll v)
{
for(int i=x;i<=m;i+=i&-i) s[i]+=v;
}
ll query(int x)
{
ll ret=0;
for(int i=x;i;i-=i&-i) ret+=s[i];
return ret;
}
void modify(int x,int f)
{
if(ql[x]<=qr[x]) updata(ql[x],qa[x]*f),updata(qr[x]+1,-qa[x]*f);
else updata(1,qa[x]*f),updata(qr[x]+1,-qa[x]*f),updata(ql[x],qa[x]*f);
}
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[p[i]]=L;
return ;
}
int i,j,mid=l-1,MID=L+R>>1;
while(now<MID) modify(++now,1);
while(now>MID) modify(now--,-1);
for(i=l;i<=r;i++)
{
cur[p[i]]=0;
for(j=head[p[i]];j&&cur[p[i]]<P[p[i]];j=next[j]) cur[p[i]]+=query(j);
if(cur[p[i]]>=P[p[i]]) mid++;
}
int l1=l,l2=mid+1;
for(i=l;i<=r;i++)
{
if(cur[p[i]]>=P[p[i]]) q[l1++]=p[i];
else q[l2++]=p[i];
}
for(i=l;i<=r;i++) p[i]=q[i];
solve(l,mid,L,MID),solve(mid+1,r,MID+1,R);
}
int main()
{
n=rd(),m=rd();
int i,j,a;
for(i=1;i<=m;i++) a=rd(),next[i]=head[a],head[a]=i;
for(i=1;i<=n;i++) P[i]=rd(),p[i]=i;
K=rd();
for(i=1;i<=K;i++) ql[i]=rd(),qr[i]=rd(),qa[i]=rd();
K++;
ql[K]=1,qr[K]=m,qa[K]=1<<30;
solve(1,n,1,K);
for(i=1;i<=n;i++)
{
if(ans[i]<K) printf("%d\n",ans[i]);
else printf("NIE\n");
}
return 0;
}
【BZOJ2527】[Poi2011]Meteors 整体二分的更多相关文章
-
BZOJ2527 [Poi2011]Meteors 整体二分 树状数组
原文链接http://www.cnblogs.com/zhouzhendong/p/8686460.html 题目传送门 - BZOJ2527 题意 有$n$个国家. 太空里有$m$个太空站排成一个圆 ...
-
BZOJ2527[Poi2011]Meteors——整体二分+树状数组
题目描述 Byteotian Interstellar Union (BIU) has recently discovered a new planet in a nearby galaxy. The ...
-
BZOJ2527: [Poi2011]Meteors(整体二分)
Description Byteotian Interstellar Union (BIU) has recently discovered a new planet in a nearby gala ...
-
【bzoj2527】[Poi2011]Meteors 整体二分+树状数组
题目描述 有N个成员国.现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站. 这个星球经常会下陨石雨.BIU已经预测了接下来K场陨石雨的情况.BI ...
-
[bzoj2527][Poi2011]Meteors_整体二分_树状数组
Meteors bzoj-2527 Poi-2011 题目大意:题目链接. 注释:略. 想法: 首先答案可以离线,且具有单调性. 这里的单调性就是随着时间的推移,每个国家收集的陨石数增加. 不难想到整 ...
-
【BZOJ-2527】Meteors 整体二分 + 树状数组
2527: [Poi2011]Meteors Time Limit: 60 Sec Memory Limit: 128 MBSubmit: 831 Solved: 306[Submit][Stat ...
-
2527: [Poi2011]Meteors[整体二分]
2527: [Poi2011]Meteors Time Limit: 60 Sec Memory Limit: 128 MB Submit: 1528 Solved: 556 [Submit][S ...
-
bzoj 2527: [Poi2011]Meteors 整体二分
给每个国家建一个链表,这样分治过程中的复杂度就和序列长度线形相关了,无脑套整体二分就可以. (最坑的地方是如果所有位置都是一个国家,那么它的样本个数会爆longlong!!被这个坑了一次,大于p[i] ...
-
Luogu3527 POI2011 Meteors 整体二分、树状数组、差分
传送门 比较板子的整体二分题目,时限有点紧注意常数 整体二分的过程中将时间在\([l,mid]\)之间的流星使用树状数组+差分进行维护,然后对所有国家查看一遍并分好类,递归下去,记得消除答案在\([m ...
随机推荐
-
apache指定的网络名不再可用
如果Apache的error.log还是出现大量的:Sat Dec 24 17:21:28 2006] [warn] (OS 64)指定的网络名不再可 用. : winnt_accept: Async ...
-
SSH无密码登录配置小结
ssh-keygen -t rsa //-t指定算法 将公钥复制到被管理机器上面 ssh-copy-id -i ~/.ssh/id_rsa.pub 172.29.0.89 ssh-copy-id -i ...
-
Java——FIle:
1.读取文件夹中的文件 /** * 读取图片文件 * @param imgPath 文件所在的文件夹绝对路径 * @return * @throws FileNotFoundException */ ...
-
Application使用示例
MainActivity如下: package cn.testapplication; import android.os.Bundle; import android.view.View; impo ...
-
Flask学习记录之Flask-Login
Flask-Loging 可以方便的管理用户会话,保护路由只让认证用户访问 http://flask-login.readthedocs.org/en/latest/ 一.初始化Flask-Login ...
-
Python Tensorflow下的Word2Vec代码解释
前言: 作为一个深度学习的重度*者,在学习了各项理论后一直想通过项目练手来学习深度学习的框架以及结构用在实战中的知识.心愿是好的,但机会却不好找.最近刚好有个项目,借此机会练手的过程中,我发现其实各 ...
-
kindeditor修改图片上传路径-使用webapi上传图片到图片服务器
kindeditor是一个非常好用的富文本编辑器,它的简单使用我就不再介绍了. 在这里我着重介绍一些使用kindeditor修改图片上传路径并通过webapi上传图片到图片服务器的方案. 因为我使用的 ...
-
MVC设置启动页
设置启动页需要在路由中添加一段代码: public static void RegisterRoutes(RouteCollection routes) { rou ...
-
Ubuntu自带截图工具screenshoot
-
NEERC Southern Subregional 2012
NEERC Southern Subregional 2012 Problem B. Chess Championship 题目描述:有两个序列\(a, b\),两个序列都有\(n\)个数,并且这\( ...