[BZOJ2527/Luogu3527][POI2011]Meteors(整体二分)

发布于 2018-04-17  87 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2527/Luogu3527][POI2011]Meteors(整体二分)

Description

Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站。
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。

Tag

整体二分

解决思路

对于每一个国家,二分答案。每一次算到当前二分时间的mid,然后将已经满足的国家归到左边处理,还未满足的国家归到右边处理。
为了方便处理最后收集不满的国家,可以在最后面再加一个为inf的陨石雨,方便所有国家都收集满。
至于每一次陨石雨的计算,可以用树状数组来维护。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lowbit(x) ((x)&(-(x)))

const int maxN=300100;
const int inf=2147483647;

int n,m,K;
int P[maxN],O[maxN];
int L[maxN],R[maxN],A[maxN];
int edgecnt=0,Head[maxN],Next[maxN],V[maxN];
int Ans[maxN],Last[maxN];
ll BIT[maxN],Sum[maxN];
int histcnt=0,Hist[maxN];
int Id[maxN],Bp[maxN];

void Add_Edge(int u,int v);
void Solve(int tl,int tr,int il,int ir);
void Add(int pos,int key);
ll Query(int pos);

int main()
{
    mem(Head,-1);

    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int o;scanf("%d",&o);
        Add_Edge(o,i);
    }
    for (int i=1;i<=n;i++) scanf("%d",&P[i]);
    cin>>K;
    for (int i=1;i<=K;i++) scanf("%d%d%d",&L[i],&R[i],&A[i]);
    K++;L[K]=1;R[K]=m;A[K]=inf;

    for (int i=1;i<=n;i++) Id[i]=i;
    Solve(1,K,1,n);

    for (int i=1;i<=n;i++)
        if (Ans[i]==K) printf("NIE\n");
        else printf("%d\n",Ans[i]);
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void Solve(int tl,int tr,int il,int ir)
{
    if (il>ir) return;
    if (tl==tr)//得到对应区间答案
    {
        for (int i=il;i<=ir;i++) Ans[Id[i]]=tl;
        return;
    }
    histcnt++;
    int mid=(tl+tr)>>1;
    for (int t=tl;t<=mid;t++)//进行所有mid之前的陨石雨
        if (L[t]<=R[t]) Add(L[t],A[t]),Add(R[t]+1,-A[t]);
        else Add(L[t],A[t]),Add(1,A[t]),Add(R[t]+1,-A[t]);
    int l=il,r=ir;
    for (int i=il;i<=ir;i++)//统计每一个国家收集到的陨石雨
    {
        Sum[Id[i]]=0;
        for (int e=Head[Id[i]];e!=-1;e=Next[e])
        {
            Sum[Id[i]]+=Query(V[e]);
            if (Sum[Id[i]]+Last[Id[i]]>P[Id[i]]) break;
        }
        //按照要求分为两类
        if (Sum[Id[i]]+Last[Id[i]]>=P[Id[i]])  Bp[l++]=Id[i];
        else Bp[r--]=Id[i],Last[Id[i]]+=Sum[Id[i]];
    }
    for (int i=il;i<=ir;i++) Id[i]=Bp[i];
    Solve(tl,mid,il,l-1);Solve(mid+1,tr,r+1,ir);//左右分治
    return;
}

void Add(int pos,int key)
{
    while (pos<=m)
    {
        if (Hist[pos]!=histcnt) BIT[pos]=key,Hist[pos]=histcnt;
        else BIT[pos]+=key;
        pos+=lowbit(pos);
    }
    return;
}

ll Query(int pos)
{
    ll Ret=0;
    while (pos)
    {
        if (Hist[pos]==histcnt) Ret+=BIT[pos];
        pos-=lowbit(pos);
    }
    return Ret;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2527/Luogu3527][POI2011]Meteors(整体二分)


HNCJ OIer