BZOJ 2527 Meteors

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

思路:整体二分

#include<cstdio>

#include<cmath>

#include<iostream>

#include<cstring>

#include<algorithm>

#define ll long long

#define inf 1000000010

int n,m,a[],first[],next[],tot;

int tol[],tor[],ans[],id[],K;

ll cur[],tmp[],h[],go[];

struct node{

    int id,l,r,w;

}q[];

int read(){

    int t=,f=;char ch=getchar();

    while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

    return t*f;

}

ll sum(int x){

    ll res=;

    while (x){

      res+=h[x];

      x-=(x)&(-x);

    }

    return res;

}

void add(int x,ll v){

   for (int i=x;i<=m;i+=(i)&(-i))

        h[i]+=v;

}

void add(int x,int y,ll v){

    add(x,v);add(y+,-v);

}

void solve(int l,int r,int x,int y){

    if (x>y) return;

    if (l==r){

        for (int i=x;i<=y;i++)

         ans[id[i]]=l;

        return;

    }

    int lnum=,rnum=;

    int mid=(l+r)>>;

    for (int i=l;i<=mid;i++)

     if (q[i].l<=q[i].r) add(q[i].l,q[i].r,q[i].w);

     else add(q[i].l,m,q[i].w),add(,q[i].r,q[i].w);

    for (int i=x;i<=y;i++){

        tmp[id[i]]=;

        for (int j=first[id[i]];j;j=next[j]){

            int pur=go[j];

            tmp[id[i]]+=sum(pur);

            if (tmp[id[i]]+cur[id[i]]>=a[id[i]]) break;

        }

        if (tmp[id[i]]+cur[id[i]]>=a[id[i]]) tol[++lnum]=id[i];

        else tor[++rnum]=id[i],cur[id[i]]+=tmp[id[i]];

    }

    for (int i=l;i<=mid;i++)

     if (q[i].l<=q[i].r) add(q[i].l,q[i].r,-q[i].w);

     else add(q[i].l,m,-q[i].w),add(,q[i].r,-q[i].w);

    for (int i=;i<lnum;i++)

     id[x+i]=tol[i+];

    for (int i=;i<rnum;i++)

     id[x+lnum+i]=tor[i+];

    solve(l,mid,x,x+lnum-);

    solve(mid+,r,x+lnum,y);

}

int main(){

    n=read();m=read();

    for (int i=;i<=m;i++){

        int x=read();

        tot++;

        next[tot]=first[x];

        first[x]=tot;

        go[tot]=i;

    }

    for (int i=;i<=n;i++)

     a[i]=read();

    K=read();

    for (int i=;i<=K;i++){

        q[i].l=read();q[i].r=read();q[i].w=read();

        q[i].id=i;

    }

    K++;

    q[K].l=;q[K].r=m;q[K].w=inf;

    q[K].id=K;

    for (int i=;i<=n;i++)

     id[i]=i;

    solve(,K,,n);

    for (int i=;i<=n;i++){

        if (ans[i]!=K) printf("%d\n",ans[i]);

        else puts("NIE");

    }

    return ;

}