cjb-poi2011meteors

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
const int N=300010;
struct query
{
    int l,r,a;
    void scan(){scanf("%d%d%d",&l,&r,&a);}
}q[N];
vector<int>g[N];
int need[N],n,m,k;
int ans[N],p[N],tmp1[N],tmp2[N];
long long c[N];
void modify(int x,int y){for(;x<=m;x+=x&(-x))c[x]+=y;}
long long get(int x){long long s=0;for(;x;x-=x&(-x))s+=c[x];return s;}
void clear(int x){for(;x<=m;x+=x&(-x))c[x]=0;}
void modi(const query&a)
{
    if(a.l<=a.r)
    {
        modify(a.l,a.a);
        modify(a.r+1,-a.a);
    }
    else
    {
        modify(1,a.a);
        modify(a.r+1,-a.a);
        modify(a.l,a.a);
    }
}
void cle(const query&a)
{
    if(a.l<=a.r)
    {
        clear(a.l);
        clear(a.r+1);
    }
    else
    {
        clear(1);
        clear(a.r+1);
        clear(a.l);
    }
}
void work(int a,int b,int l,int r)
{
    if(l==r)
    {
        for(int i=a;i<=b;i++)ans[p[i]]=l;
        return;
    }
    int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++)modi(q[i]);
    int cnt1=0,cnt2=0;
    for(int i=a;i<=b;i++)
    {
        long long now=need[p[i]];
        for(auto j:g[p[i]])
        {
            if(now<=0)break;
            now-=get(j);
        }
        if(now<=0)tmp1[++cnt1]=p[i];else tmp2[++cnt2]=p[i],need[p[i]]=now;
    }
    for(int i=a;i<=b;i++)if(i-a+1<=cnt1)p[i]=tmp1[i-a+1];else p[i]=tmp2[i-a+1-cnt1];
    for(int i=l;i<=mid;i++)cle(q[i]);
    work(a,a+cnt1-1,l,mid);
    work(a+cnt1,b,mid+1,r);
}
int main()
{
    freopen("meteors.in","r",stdin);
    freopen("meteors.out","w",stdout);
    scanf("%d%d",&n,&m);
    rep(i,m)
    {
        int x;
        scanf("%d",&x);
        g[x].pb(i);
    }
    rep(i,n)scanf("%d",&need[i]);
    scanf("%d",&k);
    rep(i,k)q[i].scan();
    rep(i,n)p[i]=i;
    work(1,n,1,k+1);
    rep(i,n)if(ans[i]<=k)printf("%d\n",ans[i]);else puts("NIE");
    return 0;
}
}}}

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;++i)
#define mp make_pair
#define pb push_back
#define x0 gtmsub
#define y0 gtmshb
#define x1 gtmjtjl
#define y1 gtmsf
const int N=300010;
struct query
{
    int l,r,a;
    void scan(){scanf("%d%d%d",&l,&r,&a);}
}q[N];
vector<int>g[N];
int need[N],n,m,k;
int ans[N],p[N],tmp1[N],tmp2[N];
long long c[N];
void modify(int x,int y){for(;x<=m;x+=x&(-x))c[x]+=y;}
long long get(int x){long long s=0;for(;x;x-=x&(-x))s+=c[x];return s;}
void clear(int x){for(;x<=m;x+=x&(-x))c[x]=0;}
void modi(const query&a)
{
    if(a.l<=a.r)
    {
        modify(a.l,a.a);
        modify(a.r+1,-a.a);
    }
    else
    {
        modify(1,a.a);
        modify(a.r+1,-a.a);
        modify(a.l,a.a);
    }
}
void cle(const query&a)
{
    if(a.l<=a.r)
    {
        clear(a.l);
        clear(a.r+1);
    }
    else
    {
        clear(1);
        clear(a.r+1);
        clear(a.l);
    }
}
void work(int a,int b,int l,int r)
{
    if(l==r)
    {
        for(int i=a;i<=b;i++)ans[p[i]]=l;
        return;
    }
    int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++)modi(q[i]);
    int cnt1=0,cnt2=0;
    for(int i=a;i<=b;i++)
    {
        long long now=need[p[i]];
        for(auto j:g[p[i]])
        {
            if(now<=0)break;
            now-=get(j);
        }
        if(now<=0)tmp1[++cnt1]=p[i];else tmp2[++cnt2]=p[i],need[p[i]]=now;
    }
    for(int i=a;i<=b;i++)if(i-a+1<=cnt1)p[i]=tmp1[i-a+1];else p[i]=tmp2[i-a+1-cnt1];
    for(int i=l;i<=mid;i++)cle(q[i]);
    work(a,a+cnt1-1,l,mid);
    work(a+cnt1,b,mid+1,r);
}
int main()
{
    freopen("meteors.in","r",stdin);
    freopen("meteors.out","w",stdout);
    scanf("%d%d",&n,&m);
    rep(i,m)
    {
        int x;
        scanf("%d",&x);
        g[x].pb(i);
    }
    rep(i,n)scanf("%d",&need[i]);
    scanf("%d",&k);
    rep(i,k)q[i].scan();
    rep(i,n)p[i]=i;
    work(1,n,1,k+1);
    rep(i,n)if(ans[i]<=k)printf("%d\n",ans[i]);else puts("NIE");
    return 0;
}