BZOJ2527 & 洛谷3527:[Poi2011]Meteors——题解

时间:2023-03-09 00:38:08
BZOJ2527 & 洛谷3527:[Poi2011]Meteors——题解

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

https://www.luogu.org/problemnew/show/3527

http://www.lydsy.com/JudgeOnline/problem.php?id=2527

(事先说明,本人是开O2过的洛谷,如果不开的话请用数组模拟STL)

(代码和题解参考洛谷的题解第一篇)

(采用BZOJ翻译)

Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站。这个星球经常会下陨石雨。
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<=n,m,k<=3*10^5 1<=Pi<=10^9 1<=Ai<10^9

显然是一道维护区间的题,如果不考虑用什么奇葩难写的数据结构的话,还是整体二分+树状数组好些。

……但是一旦会了整体二分之后不就是水题了吗……

我们二分每个成员国最少需要多少波操作会到达他们的预定值,剩下的就是套路了。

不过需要注意这题可能爆longlong,开longlong的同时记的判断并及时跳出。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=;
inline ll read(){
ll X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct question{
int l,r,op,id;
ll k;
}q[N],tmp1[N],tmp2[N];
vector<int>g[N];
int ans[N],aim[N];
ll tree[N];
int n,m,p;
inline int lowbit(int t){return t&(-t);}
inline void add(int x,ll y){//将a[x]+y
for(int i=x;i<=m;i+=lowbit(i))tree[i]+=y;
}
inline ll query(int x){//1-x区间和
ll res=;
for(int i=x;i>;i-=lowbit(i))res+=tree[i];
return res;
}
inline void modify(ll x,ll y,ll z){
add(x,z);add(y+,-z);
}
void solve(int L,int R,int l,int r){
if(L>R)return;
if(l==r){
for(int i=L;i<=R;i++){
if(q[i].op==)ans[q[i].id]=l;
}
return;
}
int idx1=,idx2=,mid=(l+r)>>;
for(int i=L;i<=R;i++){
if(q[i].op==){
ll tmp=;
for(int j=;j<g[q[i].id].size();j++){
tmp+=query(g[q[i].id][j]);
if(tmp>q[i].k)break;
}
if(tmp>=q[i].k)tmp1[idx1++]=q[i];
else{q[i].k-=tmp;tmp2[idx2++]=q[i];}
}else{
if(q[i].id<=mid){
if(q[i].op==)modify(q[i].l,q[i].r,q[i].k);
else modify(q[i].l,m,q[i].k),modify(,q[i].r,q[i].k);
tmp1[idx1++]=q[i];
}else tmp2[idx2++]=q[i];
}
}
for(int i=;i<idx1;i++){
question k=tmp1[i];
if(k.op==)modify(k.l,k.r,-k.k);
else if(k.op==)modify(k.l,m,-k.k),modify(,k.r,-k.k);
}
bool ok1=,ok2=;
int MID=L+idx1;
for(int i=L;i<MID;i++)q[i]=tmp1[i-L],ok1=;
for(int i=MID;i<=R;i++)q[i]=tmp2[i-MID],ok2=;
if(ok1)solve(L,MID-,l,mid);
if(ok2)solve(MID,R,mid+,r);
return;
}
int main(){
n=read(),m=read();
for(int i=;i<=m;i++)g[read()].push_back(i);
for(int i=;i<=n;i++)aim[i]=read();
p=read();
for(int i=;i<=p;i++){
q[i].l=read();q[i].r=read();q[i].k=read();
if(q[i].r>=q[i].l)q[i].op=;
else q[i].op=;
q[i].id=i;
}
for(int i=;i<=n;i++){
q[i+p].k=aim[i];q[i+p].op=;q[i+p].id=i;
}
solve(,n+p,,p+);
for(int i=;i<=n;i++){
if(ans[i]!=p+)printf("%d\n",ans[i]);
else puts("NIE");
}
return ;
}