首页 > 代码库 > HDU5140---Hun Gui Wei Company （主席树）
HDU5140---Hun Gui Wei Company （主席树）
主席树太强大了，，如果仅仅用来求第k大就太屈才了。。貌似和HDU4605差不多，那个是在图上根据点的顺序建立主席树，这个是根据年龄大小 或者等级高低建立主席树。
题意 大致就是一个二维区间的求和，但是数量级很大，显然不能直接求。
一个想法是可以二维线段树，但是这样显然会MLE。
另外一个还是主席树，以age或者level顺序建立主席树，我是以age建立的。
然后对应的查找就是 查找 tree[LA-1] 、tree[HA]之间的线段树 等级在LL HL之间的salary的和。
题目强制要求在线算，只需要把 k更新后询问的LL HL LA HA 离散化就可以了。
1 #include <cstdio> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cstring> 6 #include <algorithm> 7 using namespace std; 8 typedef unsigned long long ull; 9 typedef long long ll; 10 const int inf = 0x3f3f3f3f; 11 const double eps = 1e-8; 12 const int maxn = 1e5+10; 13 int tot,tree[maxn],c[maxn*20],lson[maxn*20],rson[maxn*20]; 14 ll sum[maxn*20]; 15 int build (int l, int r) 16 { 17 int root = tot++; 18 c[root] = sum[root] = 0; 19 if (l != r) 20 { 21 int mid = (l + r) >> 1; 22 lson[root] = build(l,mid); 23 rson[root] = build(mid+1,r); 24 } 25 return root; 26 } 27 int MAX; 28 int update (int root,int pos,int val,ll sa) 29 { 30 int newroot = tot++; 31 int tmp = newroot; 32 int l = 1, r = MAX; 33 c[newroot] = c[root] + val; 34 sum[newroot] = sum[root] + sa; 35 while (l < r) 36 { 37 int mid = (l + r) >> 1; 38 if (pos <= mid) 39 { 40 r = mid; 41 rson[newroot] = rson[root]; 42 root = lson[root]; 43 lson[newroot] = tot++; 44 newroot = lson[newroot]; 45 } 46 else 47 { 48 l = mid + 1; 49 lson[newroot] = lson[root]; 50 root = rson[root]; 51 rson[newroot] = tot++; 52 newroot = rson[newroot]; 53 } 54 c[newroot] = c[root] + val; 55 sum[newroot] = sum[root] + sa; 56 } 57 return tmp; 58 } 59 ll query(int root1,int root2,int l,int r,int ua,int ub) 60 { 61 if (ua > ub) 62 return 0; 63 if (ua <= l && ub >= r) 64 { 65 return sum[root2] - sum[root1]; 66 } 67 int mid = (l + r) >> 1; 68 ll t1 = 0, t2 = 0; 69 if (ua <= mid) 70 t1 = query(lson[root1],lson[root2],l,mid,ua,ub); 71 if (ub > mid) 72 t2 = query(rson[root1],rson[root2],mid+1,r,ua,ub); 73 return t1 + t2; 74 } 75 int lev[maxn],idx1,idx2,age[maxn]; 76 77 struct worker 78 { 79 int s,l,a; 80 bool operator < (const worker &rhs)const 81 { 82 return a < rhs.a; 83 } 84 } per[maxn]; 85 int main(void) 86 { 87 #ifndef ONLINE_JUDGE 88 freopen("in.txt","r",stdin); 89 #endif 90 int n; 91 while (~scanf ("%d",&n)) 92 { 93 tot = 0; 94 memset(sum,0,sizeof(sum)); 95 MAX = n; 96 int max_age = 0,min_age = inf; 97 for (int i = 1; i <= n; i++) 98 { 99 scanf ("%d%d%d",&per[i].s, &per[i].l, &per[i].a);100 age[i-1] = per[i].a;101 lev[i-1] = per[i].l;102 max_age = max(max_age,age[i-1]);103 min_age = min(min_age,age[i-1]);104 }105 sort(per+1, per+1+n);106 sort(age, age+n);107 sort(lev, lev+n);108 idx1 = n;109 idx2 = unique(lev,lev+n) - lev;110 111 tree[0] = build(1,n);112 for (int i = 1; i <= n; i++)113 {114 int tmp = lower_bound(lev,lev+idx2,per[i].l) - lev + 1;115 tree[i] = update(tree[i-1], tmp, 1, (ll)per[i].s);116 }117 int Q;118 ll k = 0;119 scanf ("%d",&Q);120 for (int i = 0; i < Q; i++)121 {122 ll LL,HL,LA,HA;123 scanf ("%I64d%I64d%I64d%I64d",&LL,&HL,&LA,&HA);124 LL += k, HL -= k;125 LA += k, HA -= k;126 if (LL > HL)127 swap(LL, HL);128 if (LA > HA)129 swap(LA, HA);130 LA = max(LA, (ll)0);131 HA = min(HA, (ll)1000000000);132 int idx_la = lower_bound(age,age+idx1,LA) - age + 1;133 int idx_ha = lower_bound(age,age+idx1,HA) - age + 1;134 if (age[idx_ha-1] == HA)135 {136 while (age[idx_ha-1] == HA && idx_ha <= n)137 idx_ha ++;138 idx_ha--;139 }140 else141 idx_ha--;142 LL = max(LL,(ll)0);143 HL = min(HL,(ll)1000000000);144 int i1 = lower_bound(lev,lev+idx2,LL) - lev + 1;145 int i2 = lower_bound(lev,lev+idx2,HL) - lev + 1;146 if (lev[i2-1] > HL)147 i2--;148 k = query(tree[idx_la-1],tree[idx_ha],1,MAX,i1,i2);149 printf("%I64d\n",k);150 }151 }152 return 0;153 }154 155 /*156 5157 1 2 2158 2 3 3159 3 4 4160 4 5 6161 6 5 8162 1163 2 3 2 8164 165 3166 5 6 4167 2 8 6168 4 8 6169 1170 6 8 4 6171 */
HDU5140---Hun Gui Wei Company （主席树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。