[POI 18 Stage 3] Meteors

作法：

這題是整體二分的經典題。具體作法是：我們使用BIT作區間加減值和單點查詢的操作，這樣可以在 O( A_i * logm ) 的時間中求出一個人目錢賺到的錢有多少。並且我們遞回處理的問題是：對於 [ L , R ] ，已知有一個 vector 裡面放的人們的答案都落在 [ L , R ] 裡面，求出這些人的確切答案。當 L = R 的時候當然 vector 裡面的人們的答案都是 L ，而如果不是的話，令 mid = ( L + R ) / 2 ，這時後把 BIT 調整到已經進行的操作只有第 1 ~ mid 個，然後把這時候已經達到目標的人丟進一個 vector ，因為他們的答案區間就會是 [ L , mid ] ，而還沒達到目標的就丟進另一個，他們的答案區間會是 [ mid+1 , R ] ，遞回下去處理即可。

另外，要記得開 unsigned long long =ㄦ= 真是太陰險了。
感覺我沒講的很清楚，還是看看 code 吧，應該蠻好懂的。

code :

#include<bits/stdc++.h>
#define LL unsigned long long
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=300000+10 ;
 
LL bit[maxn] ;
void add(int l,int r,LL val)
{
    r++ ;
    while(l<maxn) bit[l]+=val , l+=lowbit(l) ;
    while(r<maxn) bit[r]-=val , r+=lowbit(r) ;
}
 
LL query(int x)
{
    LL ret=0LL ;
    while(x) ret+=bit[x] , x-=lowbit(x) ;
    return ret ;
}
 
LL query(const vector<int> &v)
{
    LL ret=0LL ;
    for(int i=0;i<v.size();i++) ret+=query(v[i]) ;
    return ret ;
}
 
struct P{ int l,r ; LL val; }q[maxn] ;
int n,m,nowq=0 ;
void adjust(int newq)
{
    while(nowq < newq)
    {
        int x=++nowq ;
        if(q[x].l <= q[x].r) add(q[x].l,q[x].r,q[x].val) ;
        else add(q[x].l,m,q[x].val) , add(1,q[x].r,q[x].val) ;
    }
    while(nowq > newq)
    {
        int x=nowq-- ;
        if(q[x].l <= q[x].r) add(q[x].l,q[x].r,-q[x].val) ;
        else add(q[x].l,m,-q[x].val) , add(1,q[x].r,-q[x].val) ;
    }
}
 
vector<int> peo[maxn],G[4*maxn] ;
int gid ;
int ans[maxn] ;
LL goal[maxn] ;
 
void solve(const vector<int> &v,int l,int r)
{
    if(l==r)
    {
        for(int i=0;i<v.size();i++)
            ans[v[i]]=l ;
        return ;
    }
 
    if(v.empty()) return ;
    int mid=(l+r)/2 ;
    adjust(mid) ;
    for(int i=0;i<v.size();i++)
    {
        if( query(peo[v[i]]) >= goal[v[i]] )
            G[gid].push_back(v[i]) ;
        else G[gid+1].push_back(v[i]) ;
    }
    int tmp=gid ; gid+=2 ;
    solve(G[tmp],l,mid) ;
    solve(G[tmp+1],mid+1,r) ;
}
 
main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=1;i<=m;i++)
    {
        int x ; scanf("%d",&x) ;
        peo[x].push_back(i) ;
    }
    for(int i=1;i<=n;i++) scanf("%llu",&goal[i]) ;
    int Q ; scanf("%d",&Q) ;
    for(int i=1;i<=Q;i++) scanf("%d%d%llu",&q[i].l,&q[i].r,&q[i].val) ;
    for(int i=1;i<=n;i++) G[0].push_back(i) ; gid=1 ;
    solve(G[0],1,Q+1) ;
    for(int i=1;i<=n;i++)
    {
        if(ans[i]==Q+1) printf("NIE\n") ;
        else printf("%d\n",ans[i]) ;
    }
}