首页 > 代码库 > BZOJ 2527 [Poi2011]Meteors（整体二分）
BZOJ 2527 [Poi2011]Meteors（整体二分）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2527
【题目大意】
有N个成员国。现在它发现了一颗新的星球，
这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第Ai个国家的太空站。
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。
你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。
【题解】
如果枚举每场陨石雨，树状数组查询每个国家是否完成收集，复杂度O(Kmlogm),难以接受
因此我们对答案整体二分，不同位置的答案不断划分到对应的陨石时段计算。
将完成任务的国家放到左边区间，未达成的放到右边区间。复杂度O(mlogmlogK).
【代码】
#include <cstdio>#include <cstring>#include <vector> using namespace std;const int N=300010;typedef long long LL;int x,n,m,T,K,l[N],r[N],val[N],id[N],p[N],tmp[N],ans[N],mark[N];LL c[N];vector<int> v[N];LL query(int x){LL s=0;while(x)s+=c[x],x-=x&-x;return s;}void add(int x,int val){while(x<=m)c[x]+=val,x+=x&-x;}void update(int x,int k){ if(l[x]<=r[x])add(l[x],k*val[x]),add(r[x]+1,-k*val[x]); else{ add(1,k*val[x]),add(r[x]+1,-k*val[x]); add(l[x],k*val[x]); }}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[id[i]]=L;return;} int mid=(L+R)>>1; while(T<=mid)update(++T,1); while(T>mid)update(T--,-1); int cnt=0,x; LL tot; for(int i=l;i<=r;i++){ tot=0; x=id[i]; for(int j=0;j<v[x].size();j++){ tot+=query(v[x][j]); if(tot>=p[x])break; }if(tot>=p[x])mark[x]=1,cnt++; else mark[x]=0; }int l1=l,l2=l+cnt; for(int i=l;i<=r;i++){ if(mark[id[i]])tmp[l1++]=id[i]; else tmp[l2++]=id[i]; }for(int i=l;i<=r;i++)id[i]=tmp[i]; solve(l,l1-1,L,mid); solve(l1,l2-1,mid+1,R);}int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=m;i++)scanf("%d",&x),v[x].push_back(i); for(int i=1;i<=n;i++)scanf("%d",&p[i]); scanf("%d",&K); for(int i=1;i<=K;i++)scanf("%d%d%d",&l[i],&r[i],&val[i]); l[++K]=1;r[K]=m;val[K]=0x3f3f3f3f; for(int i=1;i<=n;i++)id[i]=i; solve(1,n,1,K); for(int i=1;i<=n;i++){ if(ans[i]==K)puts("NIE"); else printf("%d\n",ans[i]); } }return 0;}BZOJ 2527 [Poi2011]Meteors（整体二分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。