[POI XVIII][整體二分] Meteors

原題連結

整體二分這個科技在不想寫複雜資料結構(Persistent,Copy on write......)時還是挺好用的

首先觀察到每位助手在經過某個時間點之後就會保持達成要求的狀態(因為擁有數量不會減少)
所以可以考慮二分搜每位助手完成目標的時間點，用BIT維護操作，複雜度O((K+C_i)logK) for people_i，總時間O((NK+M)logK)
用可持久化線段樹紀錄每個時間點完成後的總資源量，這樣複雜度會變O((C_i)logMlogK) for people_i，總時間O((N+M)logKlogM)
但是持久化線段樹code量大又難debug，而且空間複雜度變成O((M+K)logM)，送你一個大大的MLE
採用持久化BIT的話時間複雜度又會多一個log

這時候就可以啟用整體二分這個offline技巧，讓空間和時間降低。
網路上有很多關於整體二分的資源，而且還有一個常被放在一起講的技巧：操作分治(CDQ分治)，可以一起學習。

核心思想就是與其每個人分別二分搜，不如大家一起二分搜。
對於時間區間(0,K-1)直接二分，將在mid時已經滿足的人遞迴丟進(0,mid)中，其他放入(mid+1,K-1)
容易知道最多只有logK層遞迴，如果每層的時間複雜度能作到線性或是多一個log（像本題)，那麼總體時間複雜度就是可以忍受的。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<string.h>
#include<assert.h>
#define LL long long
using namespace std;
const LL maxn=300000+5;
const LL maxm=300000+5;
const LL maxk=300000+5;
const LL INF=1LL<<60;
LL n,m;
LL add[maxm*8];
LL ml,mr,mv;
void modify(LL id,LL L,LL R)
{
    if(ml<=L && R<=mr) {add[id]+=mv;return;}
    LL M=L+(R-L)/2;
    if(ml<=M) modify(id*2,L,M);
    if(mr >M) modify(id*2+1,M+1,R);
}
LL qx,qv;
void query(LL id,LL L,LL R)
{
    assert(add[id]>=0);
    qv+=add[id];
    if(L==R) return;
    LL M=L+(R-L)/2;
    if(qx<=M) query(id*2,L,M);
    else query(id*2+1,M+1,R);
}
struct OP
{
    LL L,R,x;
}op[maxk];
void operate(LL tl,LL tr,LL plus)
{
    for(LL i=tl;i<=tr;i++)
    {
        ml=op[i].L,mr=op[i].R,mv=op[i].x*(plus);
        if(ml>mr) {ml=1;mr=op[i].R;modify(1,1,m);ml=op[i].L;mr=m;}
        modify(1,1,m);
    }
}
LL ans[maxn],target[maxn];
vector<LL> land[maxn];
void split(LL M,vector<LL>& vec,vector<LL>& ok,vector<LL>& notok)
{
    for(LL i=0;i<vec.size();i++)
    {
        LL man=vec[i];
        qv=0;
        for(LL j=0;j<land[man].size();j++)
        {
            qx=land[man][j];
            query(1,1,m);
            if(qv>=target[man])break;
        }
        if(qv>=target[man]) {ans[man]=min(ans[man],M);ok.push_back(man);}
        else {target[man]-=qv;notok.push_back(man);}
    }
    vector<LL> ().swap(vec);
}
void totBS(LL L,LL R,vector<LL> vec)
{
    if(L==R) {for(int i=0;i<vec.size();i++)ans[vec[i]]=R;return;}
    if(vec.size()==0) return;
    LL M=L+(R-L)/2;

    operate(L,M,1); 
    vector<LL> ok,notok;
    split(M,vec,ok,notok);// split
    
    operate(L,M,-1);
    totBS(L,M,ok);
    
   // operate(L,M,1);
    totBS(M+1,R,notok);
}
int main()
{
    vector<LL> vec;
    scanf("%lld%lld",&n,&m);
    LL k;
    for(LL i=1,x;i<=m;i++) {scanf("%lld",&x);land[x].push_back(i);}
    for(LL i=1;i<=n;i++) {scanf("%lld",target+i);vec.push_back(i);}
    scanf("%lld",&k);
    for(LL i=0;i<k;i++){scanf("%lld%lld%lld",&op[i].L,&op[i].R,&op[i].x);}
    
    totBS(0,k,vec);
    for(LL i=1;i<=n;i++) if(ans[i]!=k) printf("%lld\n",ans[i]+1); else printf("NIE\n");
    
}