Luogu-3527 [POI2011]MET-Meteors

题面

Luogu-3527

题解

感觉和上一那道题是一个类型的，直接二分答案，用BIT维护区间加(差分)即可

代码

#include<map>

#include<queue>

#include<cmath>

#include<ctime>

#include<stack>

#include<bitset>

#include<vector>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

inline char gc(){

//static char buf[100000],*p1,*p2;

//return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

    return getchar();

}

inline int read(){

    int ans=0,fh=1;

    char ch=gc();

    while(ch<'0'||ch>'9'){if(ch=='-') fh=-1; ch=gc();}

    while(ch>='0'&&ch<='9')	ans=(ans<<1)+(ans<<3)+ch-'0',ch=gc();

    return ans*fh;

}

const int maxn=3e5+100,inf=1e9;

int n,m,k,ql[maxn],qr[maxn],qw[maxn],b[maxn],p[maxn],ans[maxn],now;

int tmp1[maxn],tmp2[maxn];

ll tre[maxn],a[maxn];

vector<int>son[maxn];

void revise(int l,int r,int w){

    for(int i=l;i<maxn;i+=i&(-i)) tre[i]+=w;

    for(int i=r+1;i<maxn;i+=i&(-i)) tre[i]-=w;

}

void work(int x,int ms){

    int l=ql[x],r=qr[x],w=qw[x]*ms;

    if(l<=r) revise(l,r,w);

    else revise(1,r,w),revise(l,m,w);

}

ll query(int x){

    ll Ans=0;

    for(int i=x;i;i-=i&(-i)) Ans+=tre[i];

    return Ans;

}

ll check(int x){

    ll Ans=0;int lim=son[x].size();

    for(int i=0;i<lim;i++){

        Ans+=query(son[x][i]);

        if(Ans>=a[x]) return 1;

    }

    return 0;

}

void cdq(int l,int r,int L,int R){

    if(L>R) return;

    if(l==r){

        for(int i=L;i<=R;i++) ans[p[i]]=l;

        return;

    }

    int mid=l+r>>1;

    while(now<mid) work(++now,1);

    while(now>mid) work(now--,-1);

    int lc=0,rc=0,cnt=L-1;

    for(int i=L;i<=R;i++)

        if(check(p[i])) tmp1[++lc]=p[i];

        else tmp2[++rc]=p[i];

    for(int i=1;i<=lc;i++) p[++cnt]=tmp1[i];

    for(int i=1;i<=rc;i++) p[++cnt]=tmp2[i];

    cdq(l,mid,L,L+lc-1),cdq(mid+1,r,L+lc,R);

}

int main(){

//	freopen("3527.in","r",stdin);

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

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

        b[i]=read(),son[b[i]].push_back(i);

    for(int i=1;i<=n;i++) a[i]=read(),p[i]=i;

    k=read();

    for(int i=1;i<=k;i++)

        ql[i]=read(),qr[i]=read(),qw[i]=read();

    ql[++k]=1,qr[k]=m,qw[k]=inf;

    now=0,cdq(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;

}