谁都知道,流星是美丽的,会给自己带来幸福和幸运,可是,有谁知道,流星也是孤独的呢?

谁都知道,流星确实是孤独的。可是,又有谁知道,我写不出树状数组的时候,也是孤独的呢?<(=┘ ̄Д ̄)┘╧═╧

1. 题目

2. 题解

QvQ显然是个整体(Tchǐ)二分の题

但是我居然写了辣么辣么久QvQ

最后发现是树状数组写错了(其实是不会写)

Orz

先考虑,对于每一个国家,我们可以对其二分答案(需要几颗流星),每次二分以后可以暴力检测($O(Nlog_2M)$)答案是否满足来判断这个国家的答案所在区间(左还是右区间)。

那么类比一下,我们可以整体二分所有的国家。

每次二分一个答案$mid$,然后执行$[1,mid]$上的修改。再判断需要判断的每个国家的答案所在的区间是$[l,mid]$还是$[mid+1,r]$。

依次类推。

代码:

#include <bits/stdc++.h>
#define NS (300005)
#define lowbit(a) (a&-a)
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct query{LL id,w;}Q[NS],Q1[NS],Q2[NS];
LL n,m,k,cl[NS],cr[NS],cnum[NS],ans[NS],t[NS];
vector<LL> g[NS];
void update(LL a,LL d){while(a<=m)t[a]+=d,a+=lowbit(a);}
LL query(LL a){LL tot=0;while(a)tot+=t[a],a-=lowbit(a);return tot;}
void add(LL l,LL r,LL d)
{
    if(l<=r)update(l,d),update(r+1,-d);
    else update(l,d),update(1,d),update(r+1,-d);
}
void binary(LL QL,LL QR,LL l,LL r)
{
    if(QL>QR)return;
    if(l==r){for(LL i=QL;i<=QR;i++)ans[Q[i].id]=l;return;}
    LL mid=(l+r)>>1,x1=0,x2=0;
    for(LL i=l;i<=mid;i++)add(cl[i],cr[i],cnum[i]);
    for(LL i=QL,tot;i<=QR;i++)
    {
        tot=0;
        for(LL j=0;j<g[Q[i].id].size();j++)
            if(tot+=query(g[Q[i].id][j]),tot>=Q[i].w)break;
        if(tot>=Q[i].w)Q1[++x1]=Q[i];
        else Q2[++x2]=Q[i],Q2[x2].w-=tot;
    }
    for(LL i=l;i<=mid;i++)add(cl[i],cr[i],-cnum[i]);
    for(LL i=1;i<=x1;i++)Q[QL+i-1]=Q1[i];
    for(LL i=1;i<=x2;i++)Q[QL+x1-1+i]=Q2[i];
    binary(QL,QL+x1-1,l,mid),binary(QL+x1,QR,mid+1,r);
}
int main()
{
    IN(n),IN(m);
    for(LL i=1,j;i<=m;i++)IN(j),g[j].push_back(i);
    for(LL i=1;i<=n;i++)IN(Q[i].w),Q[i].id=i;
    IN(k);
    for(LL i=1;i<=k;i++)IN(cl[i]),IN(cr[i]),IN(cnum[i]);
    k++,cl[k]=1,cr[k]=m,cnum[k]=1e9;
    binary(1,n,1,k);
    for(LL i=1;i<=n;i++)
        if(ans[i]<k)printf("%lld\n",ans[i]);
        else puts("NIE");
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *