[HIHO1299]打折机票（线段树）

题目链接：http://hihocoder.com/problemset/problem/1299

线段树，按照t为下标去更新v，更新的时候要保留最大的那个。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 //kirai²»ÊÇÉ³²è£¬²»»áÍü¼ÇÐÞ¸Ämaxn
23 #define lson l, m, rt << 1
24 #define rson m + 1, r, rt << 1 | 1
25 typedef long long ll;
26 typedef struct Node {
27     int t, v;
28 }Node;
29 const int maxn = 100010;
30 int n, m;
31 int sum[maxn<<2];
32 
33 void pushUP(int rt) {
34     //modify
35     sum[rt] = max(sum[rt<<1], sum[rt<<1|1]);
36 }
37 
38 void build(int l, int r, int rt) {
39     if(l == r) {
40         sum[rt] = -1;
41         return;
42     }
43     int m = (l + r) >> 1;
44     build(lson);
45     build(rson);
46     pushUP(rt);
47 }
48 
49 void update(int p, int add, int l, int r, int rt) {
50     if(l == r) {
51         sum[rt] = max(sum[rt], add);
52         return;
53     }
54     int m = (l + r) >> 1;
55     if(p <= m) {
56         update(p, add, lson);
57     }
58     else {
59         update(p, add, rson);
60     }
61     pushUP(rt);
62 }
63 
64 int query(int L, int R, int l, int r, int rt) {
65     if(L <= l && r <= R) {
66         return sum[rt];
67     }
68     int m = (l + r) >> 1;
69     int ret = 0;
70     if(L <= m) {
71         //modify
72         ret = max(ret, query(L, R, lson));
73     }
74     if(R > m) {
75         //modify
76         ret = max(ret, query(L, R, rson));
77     }
78     return ret;
79 }
80 
81 int main() {
82     // freopen("in", "r", stdin);
83     while(~scanf("%d%d", &n, &m)) {
84         int t, v;
85         build(1, n, 1);
86         for(int i = 0; i < n; i++) {
87             scanf("%d%d", &t, &v);
88             update(t, v, 1, n, 1);
89         }
90         int a, b;
91         while(m--) {
92             scanf("%d%d", &a, &b);
93             int ans = query(a, b, 1, n, 1);
94             if(ans <= 0) printf("None
");
95             else printf("%d
", ans);
96         }
97     }
98     return 0;
99 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define lrt rt << 1
 5 #define rrt rt << 1 | 1
 6 const int maxn = 100100;
 7 typedef struct Node {
 8     int l, r;
 9     int sum;
10 }Node;
11 Node T[maxn<<2];
12 int n, m;
13 
14 void pushUP(int rt) {
15     T[rt].sum = max(T[lrt].sum, T[rrt].sum);
16 }
17 
18 void build(int rt, int l, int r) {
19     T[rt].l = l;
20     T[rt].r = r;
21     T[rt].sum = -1;
22     if(l == r) return;
23     int mid = (l + r) >> 1;
24     build(lrt, l, mid);
25     build(rrt, mid+1, r);
26     pushUP(rt);
27 }
28 
29 void update(int rt, int pos, int val) {
30     if(T[rt].l > pos || T[rt].r < pos) return;
31     if(T[rt].l <= pos && T[rt].r >= pos) T[rt].sum = max(T[rt].sum, val);
32     if(T[rt].l == T[rt].r) return;
33     update(lrt, pos, val);
34     update(rrt, pos, val);
35     pushUP(rt);
36 }
37 
38 int query(int rt, int l, int r) {
39     int ret = -1;
40     if(T[rt].l > r || T[rt].r < l) return ret;
41     if(T[rt].l >= l && T[rt].r <= r) return T[rt].sum;
42     if(T[rt].l == T[rt].r) return ret;
43     ret = max(ret, query(lrt, l, r));
44     ret = max(ret, query(rrt, l, r));
45     return ret;
46 }
47 
48 int main() {
49     // freopen("in", "r", stdin);
50     int a, b;
51     while(~scanf("%d%d",&n,&m)) {
52         build(1, 1, n);
53         for(int i = 1; i <= n; i++) {
54             scanf("%d %d", &a, &b);
55             update(1, a, b);
56         }
57         while(m--) {
58             scanf("%d %d", &a, &b);
59             int ret = query(1, a, b);
60             if(ret == -1) puts("None");
61             else printf("%d
", ret);
62         }
63     }
64     return 0;
65 }