[IOI Camp Judge 41]農田分配

IOI Camp Judge是暫時性的，因此我做了題目備份

由於分數只會越來越多，所以對於每位助手，在一個時間點之後，分數就永遠在標準以上

因此，我們可以考慮二分搜這個時間點，利用某種方法判斷這時這位助手(以下稱$A$)達到標準了沒
怎麼判斷呢？

我們可以把這時間點之前的每次操作都檢查看看能讓$A$加多少分
因此我們得到一個$O(NQ\log Q)$的算法
怎麼優化呢？

可以發現，如果每位助手同樣都要針對$Q$進行二分搜，那為甚麼不乾脆一起二分搜呢？
因此，我們可以遞迴二分$Q$的區間，找出哪些助手會跑進這個區間裡面
注意，這裡不是真的去二分搜，反而比較像在遍歷線段樹的每個節點
這顆「線段樹(之後稱之Q-Tree)」總共有$O(\log Q)$層，每一層都是$N$個助手(因為每位助手在同一層中只能待在一個時間區間裡面)，時間複雜度還是$O(NQ\log Q)$，沒有吃虧，但......我們還可以作些甚麼？

假設某個節點有$n$個助手，我們可以一起處理這$n$個助手的資訊！
怎麼做呢？
有兩種方式：(假設這個節點包含$q$個操作)
1. 枚舉$q$個操作，$O(\log n)$更新每位助手的分數
2. 枚舉$n$位助手，$O(\log q)$求出這位助手的得分

如果你有想到要怎麼用這兩種方式做，拜託告訴我......我不會QQ(遭踢飛

往線段樹的方向思考，我們能不能把每位助手的得分轉換成某種動態的區間和呢？
相信主要的癥結點還是「同一次加分每位助手最多加一次」XD
那我們針對每位助手$A$，不重複地把每次加分操作對應到他的每塊田就好啦(也就是每個加分操作都會剛好對應到$A$的一塊田，先不考慮這塊田有沒有在加分範圍)

我們就對應到「$_{註1}$位置$\geq$加分區間左界的第一塊田」吧，因此每位助手我們都要再送他$M+1$這塊田，才不會出狀況(看看$_{註1}$我說甚麼XD(指))

咦？那我們就枚舉這$n$位助手的田吧，可以發現，這樣的話在Q-Tree的每一層剛好都只會枚舉到$M$塊田，複雜度還是有希望的！
可以發現，每塊田，假設它的位置在$f$，它的得分就是所有左界$\leq f$且右界$\geq f$的加分操作的總分

可以考慮把這些田依照位置排序，加分操作依照左界排序，將田從左到右枚舉，這樣枚舉到位置$f$的這塊田的時候就可以把所有左界$\leq f$的操作依序作好(怎麼作請看$_{註2}$)，然後這塊田的得分就是右界在$[f,下一塊主人相同的田的位置)$這個區間內的加分操作的分數總和了！
yee~~~，所以$_{註2}$線段樹是用來詢問和維護，所有右界在$[l,r]$的加分操作的分數總合
簡單一點的話可以用BIT來實現

假設Q-tree中的這個節點包含$n$位助手、$m$塊田、$q$個加分操作，處理這個節點的複雜度就是$O((n+m+q)\log M)$(不計線段樹或BIT的初始化，事實上，透過還原操作就不用再次初始化)

處理Q-tree的每一層花的時間$O((N+M+Q)\log M)$

總時間複雜度：$O((N+M+Q)\log M\log Q)$

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
struct ModifyType
{
    int l,r;
    LL cost;
    ModifyType(){}
    ModifyType(const int _l,const int _r,const int _cost):l(_l),r(_r),cost(_cost){}
    bool operator<(const ModifyType &m)const{return l<m.l;}
};
int N,M,MANAGER[100001],ANS[100000];
struct Bit
{
    LL data[100001];
    void clear(){for(int i=1;i<=M;i++)data[i]=0LL;}
    void Add(int i,const LL &v){while(i<=M)data[i]+=v,i+=(i&(-i));}
    LL Query(int i){LL a=0LL;while(i)a+=data[i],i-=(i&(-i));return a;} 
};
LL STD[100000],SCORE[100000];
vector<ModifyType>MODIFY;
set<int>FARMS[100000];
void AddScore(const int assistant,ModifyType &modify,LL sign)
{
    auto it=FARMS[assistant].upper_bound(modify.r);
    if(it==FARMS[assistant].begin()||(*--it)<modify.l)return;
    SCORE[assistant]+=sign*modify.cost;
}
void Query(const vector<int>&assistants,const int l,const int r,Bit &bit)
{
    if(l==r){for(const int a:assistants)ANS[a]=r;return;}
    vector<pair<int,int> >farms;
    for(const int p:assistants)
    {
        for(auto it=FARMS[p].begin();it!=FARMS[p].end();)
        {
            const int a=*it++;
            const int b=(it==FARMS[p].end()?M+1:*it);
            farms.push_back(make_pair(a,b));
        }
    }
    vector<ModifyType>modifys;
    const int mid=(l+r)/2;
    for(int i=l;i<=mid;i++)modifys.push_back(MODIFY[i]);
    sort(farms.begin(),farms.end());
    sort(modifys.begin(),modifys.end());
    vector<int>left_assist,right_assist;
    if(true)
    {
        int i=-1;
        vector<pair<int,LL> >changes;
        for(const auto farm:farms)
        {
            while(i+1<(int)modifys.size()&&modifys[i+1].l<=farm.first)i++,bit.Add(modifys[i].r,modifys[i].cost);
            const auto &change=make_pair(MANAGER[farm.first],bit.Query(farm.second-1)-bit.Query(farm.first-1));
            SCORE[change.first]+=change.second;
            changes.push_back(change);
        }
        set<int>except;
        for(const int p:assistants)
        {
            if(SCORE[p]>=STD[p])left_assist.push_back(p);
            else right_assist.push_back(p),except.insert(p);
        }
        while(i>=0)bit.Add(modifys[i].r,-modifys[i].cost),i--;
        for(const auto &change:changes)if(except.find(change.first)==except.end())SCORE[change.first]-=change.second;
    }
    Query(left_assist,l,mid,bit);
    Query(right_assist,mid+1,r,bit);
}
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d%d",&N,&M);
        for(int i=0;i<N;i++)FARMS[i].clear();
        for(int i=0;i<N;i++)scanf("%lld",&STD[i]);
        for(int i=1;i<=M;i++)scanf("%d",&MANAGER[i]),FARMS[--MANAGER[i]].insert(i);
        MODIFY.clear();
        int querycount;scanf("%d",&querycount);
        for(int l,r,cost;querycount--;)
        {
            scanf("%d%d%d",&l,&r,&cost);
            MODIFY.push_back(ModifyType(l,r,cost));
        }
        vector<int>assistants;
        for(int i=0;i<N;i++)assistants.push_back(i),SCORE[i]=0LL;
        static Bit bit;bit.clear();
        Query(assistants,0,MODIFY.size(),bit);
        for(int i=0;i<N;i++)
        {
            if(i)putchar(' ');
            printf("%d",ANS[i]==(int)MODIFY.size()?-1:ANS[i]+1);
        }
        puts("");
    }
    return 0;
}