BZOJ2527:[Poi2011]Meteors 整体二分

思路:

对于所有的国家整体二分最小的次数即可.

真心没有什么好说的.

值得一提的是,我们每次暴力移动版本的时间复杂度是有保证的.

这事实上是在一棵树上按照dfs序遍历.因此总的移动长度等于边权和的2倍.显然是\(O(n)\)级别的.因此在移动上面的复杂度为\(O(nlogn)\).

另外这题没必要线段树吧.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';
        while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    template<typename T>inline void Get(T&x,T&y){
        Get(x),Get(y);
    }
    char buf[1500010],*o=buf;
    inline void NIE(){*o++='N',*o++='I',*o++='E',*o++='\n';}
    template<typename T>inline void Print(T x){
        static int s[100];int t=0;
        if(!x)*o++=48;else{for(;x;x/=10)s[++t]=x%10;for(int i=t;i>=1;--i)*o++=48+s[i];}
        *o++='\n';
    }
    inline void Final(){fwrite(buf,1,o-buf,stdout);}
}
 
typedef double f2;
 
#define N 300010
int n,m;
 
f2 A[N];
inline void modify(int x,f2 add){for(;x<=m+1;x+=x&-x)A[x]+=add;}
inline f2 ask(int x){f2 r=0;for(;x;x-=x&-x)r+=A[x];return r;}
 
int head[N],next[N],end[N];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
 
int s[N],l[N],r[N],d[N];
 
inline void _upd(int L,int R,int d){
    modify(L,d),modify(R+1,-d);
}
inline void upd(int L,int R,int d,int rev){
    if(L<=R)_upd(L,R,rev*d);
    else _upd(L,m,rev*d),_upd(1,R,rev*d);
}
int q[N],q1[N],q2[N],cnt1,cnt2,now,ans[N];
void Solve(int insl,int insr,int lans,int rans){
    if(insl>insr)return;
    if(lans==rans){
        for(int i=insl;i<=insr;++i)ans[q[i]]=lans;
        return;
    }
    int mid=(lans+rans)/2;
    while(now<mid)upd(l[now+1],r[now+1],d[now+1],1),++now;
    while(now>mid)upd(l[now],r[now],d[now],-1),--now;
    cnt1=cnt2=0;
    for(int i=insl;i<=insr;++i){
        f2 add=0;
        for(int j=head[q[i]];j;j=next[j])add+=ask(end[j]);
        if(add<s[q[i]])q2[++cnt2]=q[i];else q1[++cnt1]=q[i];
    }
    int k=insl;
    for(int i=1;i<=cnt1;++i)q[k++]=q1[i];for(int i=1;i<=cnt2;++i)q[k++]=q2[i];
    int t=cnt1;
    Solve(insl,insl+t-1,lans,mid);
    Solve(insl+t,insr,mid+1,rans);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    Fio::Get(n,m);
    register int i,j;int x;for(i=1;i<=m;++i)Fio::Get(x),addedge(x,i);
    for(i=1;i<=n;++i)Fio::Get(s[i]);
    int Q;Fio::Get(Q);
    for(i=1;i<=Q;++i)Fio::Get(l[i],r[i]),Fio::Get(d[i]);
    for(i=1;i<=n;++i)q[i]=i;
    l[Q+1]=r[Q+1]=1,d[Q+1]=0,Solve(1,n,1,Q+1);
    for(i=1;i<=n;++i)if(ans[i]==Q+1)Fio::NIE();else Fio::Print(ans[i]);
    return Fio::Final(),0;
    return 0;
}