hdu 5140 主席树

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

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
const int maxn = ;
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*];
int cL, cR,T[ maxn ],Ls[maxn*],Rs[maxn*],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)>>;
if( K <= mid ) insert( L, mid, K, v, Ls[per], Ls[x] );
else insert( mid+, 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 )>>;
if(cL<=mid) query( L, mid, Ls[per], Ls[cur] );
if(cR>mid ) query( mid+,R,Rs[per], Rs[cur] );
}
int main()
{
int n;
while(scanf("%d",&n)==){
for(int i=; 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[]=Ls[]=Rs[]=Len=;val[]=;
for(int i=; i<n; ++i){
int loc = lower_bound(A,A+num,P[i].A)-A+;
insert(,num,loc,P[i].S,T[i],T[i+]);
}
int m;
scanf("%d",&m);
ans=;
ll LL,LH,AL,AH;
for(int i=; 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=;
int Le=lower_bound( L, L+n, locL )-L;
int Re=upper_bound( L, L+n, locR )-L;
if(Le==Re){
puts(""); continue;
}
cL=lower_bound( A , A+num , aL )-A;
cR=upper_bound( A , A+num , aR )-A-;
if(cL>=cR||aL==aR){
if((aL<=A[cL]&&A[cL]<=aR)==false ){
puts(""); continue;
}
}
cL++; cR++;
query(,num,T[Le],T[Re]);
printf("%I64d\n",ans);
}
}
return ;
}
上一篇:小笔记(二):php数组


下一篇:C语言基础08