[HDU 5140]Hun Gui Wei Company

簡單來說，這題就是先給你一堆點 $(x,y)=(level,age)$ 和各自的權重 ($salary$)，然後開始問你一個矩形內所有點的權重總和

可能很多人直覺是二維線段樹
但其實這題不用那麼複雜 (如果你熟悉持久化結構的話)

哈我已經把答案講出來了 (持久化線段樹)

由於這題$x$和$y$的範圍很大，我們可以先把一開始給的點離散化
然後對於每個$x$，維護所有$\leq x$的點的資訊，也就是它們的區間權重總和
這會需要用到持久化線段樹，從左到右慢慢加點，才不會TLE或MLE

因此，我們已經有能力求出所有形如$(x_{left},x_{right},y_{down},y_{up})=(-INF,x,y_{1},y_{2})$的矩形，裡面點的權重總和了
方法是對$x座標\leq x$ ($x座標$最大) 的那棵線段樹查詢$[y_{1},y_{2}]$離散化後的等價區間

那對於形如$(x_{left},x_{right},y_{down},y_{up})=(x_{1},x_{2},y_{1},y_{2})$的矩形要怎麼辦呢？
可以發現，答案就是$Sum((-INF,x_{2},y_{1},y_{2}))-Sum((-INF,x_{1}-1,y_{1},y_{2}))$
($Sum(矩形)$代表查詢對應矩形得到的答案)

我的code考慮了詢問時的$int$溢位
沒考慮會怎樣？我沒試過XD

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

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF=2147483647;
struct Staff
{
    int salary,level,age;
    bool operator<(const Staff &s)const{return level<s.level;}
}STAFF[100000];
struct Node
{
    Node *ch[2];
    LL sum;
    Node(const LL _sum):ch{NULL,NULL},sum(_sum){}
    Node(Node *o):ch{o->ch[0],o->ch[1]},sum(o->sum){}
}*S[100001];
Node *Build(const int l,const int r)
{
    Node *ans=new Node(0LL);
    if(l<r)
    {
        const int mid=(l+r)/2;
        ans->ch[0]=Build(l,mid),ans->ch[1]=Build(mid+1,r);
    }
    return ans;
}
Node *Add(Node *o,const int l,const int r,const int loc,const LL &val)
{
    Node *ans=new Node((o->sum)+val);
    if(l<r)
    {
        const int mid=(l+r)/2;
        if(loc<=mid)ans->ch[0]=Add(o->ch[0],l,mid,loc,val),ans->ch[1]=o->ch[1];
        else ans->ch[0]=o->ch[0],ans->ch[1]=Add(o->ch[1],mid+1,r,loc,val);
    }
    return ans;
}
LL Query(Node *o,const int l,const int r,const int bl,const int br)
{
    if(r<bl||br<l)return 0LL;
    if(bl<=l&&r<=br)return o->sum;
    const int mid=(l+r)/2;
    return Query(o->ch[0],l,mid,bl,br)+Query(o->ch[1],mid+1,r,bl,br);
}
vector<int>LRANGE,ARANGE;
int N,M;
void Unique(vector<int>&s){sort(s.begin(),s.end()),s.resize(unique(s.begin(),s.end())-s.begin());}
void Idize(const vector<int>&s,int &val){val=lower_bound(s.begin(),s.end(),val)-s.begin();}
void Discretize()
{
    vector<int>&lv=LRANGE,&av=ARANGE;
    lv.clear(),av.clear(),lv.push_back(-INF);
    for(int i=0;i<N;i++)lv.push_back(STAFF[i].level),av.push_back(STAFF[i].age);
    Unique(lv),Unique(av);
    for(int i=0;i<N;i++)Idize(lv,STAFF[i].level),Idize(av,STAFF[i].age);
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)
        {
            Staff &s=STAFF[i];
            scanf("%d%d%d",&s.salary,&s.level,&s.age);
        }
        sort(STAFF,STAFF+N);
        Discretize(),M=ARANGE.size();
        S[0]=Build(0,M-1);
        for(int i=1,j=0;j<N;i++)
        {
            S[i]=S[i-1];
            for(;j<N&&STAFF[j].level==i;j++)S[i]=Add(S[i],0,M-1,STAFF[j].age,STAFF[j].salary);
            if(j==N)assert(i==(int)LRANGE.size()-1);
        }
        int querycount;scanf("%d",&querycount);
        const vector<int>&lv=LRANGE,&av=ARANGE;
        for(LL l1,l2,a1,a2,k=0LL;querycount--;)
        {
            scanf("%lld%lld%lld%lld",&l1,&l2,&a1,&a2);
            l1+=k,l2-=k,a1+=k,a2-=k;
            if(l1>l2)swap(l1,l2);
            if(a1>a2)swap(a1,a2);
            const int sL=(l1<=(LL)*lv.begin()?lv.begin()+1:lower_bound(lv.begin(),lv.end(),(int)l1))-lv.begin();
            const int sR=(l2>=(LL)*lv.rbegin()?lv.end():upper_bound(lv.begin(),lv.end(),(int)l2))-lv.begin()-1;
            const int aL=(a1<=(LL)*av.begin()?av.begin():lower_bound(av.begin(),av.end(),(int)a1))-av.begin();
            const int aR=(a2>=(LL)*av.rbegin()?av.end():upper_bound(av.begin(),av.end(),(int)a2))-av.begin()-1;
            printf("%lld\n",k=Query(S[sR],0,M-1,aL,aR)-Query(S[sL-1],0,M-1,aL,aR));
        }
    }
    return 0;
}