首页 > 代码库 > hdu 5140 主席树

hdu 5140 主席树

2024-08-07 10:03:31   224人阅读

这题说的是每个员工有工资 水平 在公司待的年限这几个属性，有大量的查询 查的是在一定的水平和工作年限的工人总工资是多少 这个思路是比较简单的我们按照他们的水平排序，排完后，使用主席树不断地往里面插，然后查询即可

但是有一个问题就是 可能有些点不存在 因为这题不能讲所有的点全部离散

#include <iostream>#include <cstdio>#include <algorithm>#include <string.h>#include <vector>using namespace std;const int maxn = 100005;typedef long long ll;struct person{     ll S,L,A; int id;     bool operator <(const person Aa)const{       return L < Aa.L || ( L==Aa.L && id < Aa.id );     }}P[maxn];ll A[ maxn ],ans,L[maxn],val[maxn*20];int cL, cR,T[ maxn ],Ls[maxn*20],Rs[maxn*20],Len;void insert(int L, int R, int K,ll v, int per, int &x){         x=++Len;         Ls[x]=Ls[per];         Rs[x]=Rs[per];         val[x]=val[per]+v;         if(L==R) return;         int mid = (L+R)>>1;         if( K <= mid ) insert( L, mid, K, v, Ls[per], Ls[x] );         else insert( mid+1, R, K, v, Rs[per], Rs[x] );}void query(int L, int R,int per,int cur){            if(cL<=L&&R<=cR){                 ans+=val[cur]-val[per]; return ;            }            int mid=( L + R )>>1;            if(cL<=mid) query( L, mid, Ls[per], Ls[cur] );            if(cR>mid ) query( mid+1,R,Rs[per], Rs[cur] );}int main(){    int n;    while(scanf("%d",&n)==1){         for(int i=0; i<n; ++i){            scanf("%I64d%I64d%I64d",&P[i].S,&P[i].L,&P[i].A);            A[i]=P[i].A;            L[i]=P[i].L;            P[i].id=i;         }         sort(P,P+n);         sort(A,A+n);         sort(L,L+n);         int num=unique(A,A+n)-A;         T[0]=Ls[0]=Rs[0]=Len=0;val[0]=0;         for(int i=0; i<n; ++i){             int loc = lower_bound(A,A+num,P[i].A)-A+1;             insert(1,num,loc,P[i].S,T[i],T[i+1]);         }        int m;        scanf("%d",&m);        ans=0;        ll LL,LH,AL,AH;        for(int i=0; i<m; ++i){             scanf("%I64d%I64d%I64d%I64d",&LL,&LH,&AL,&AH);             ll locL=min(LL+ans,LH-ans);             ll locR=max(LL+ans,LH-ans);             ll aL=min(AL+ans,AH-ans);             ll aR=max(AL+ans,AH-ans);             ans=0;             int Le=lower_bound( L, L+n, locL )-L;             int Re=upper_bound( L, L+n, locR )-L;             if(Le==Re){                puts("0"); continue;             }             cL=lower_bound( A , A+num , aL )-A;             cR=upper_bound( A , A+num , aR )-A-1;             if(cL>=cR||aL==aR){                 if((aL<=A[cL]&&A[cL]<=aR)==false ){                    puts("0"); continue;                 }             }             cL++; cR++;             query(1,num,T[Le],T[Re]);            printf("%I64d\n",ans);        }    }    return 0;}
View Code

 

hdu 5140 主席树


联系
我们