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

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

1. 题目

• BZOJ – 2527（英+汉+权限题）：传送门=￣ω￣=
• SPOJ – METEORS：传送门=￣ω￣=

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;
}