区间合并

1 HDU 3308 LCIS

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <stack>
 9 #include <map>
10 #include <set>
11 #include <cmath>
12 #include <cctype>
13 #include <ctime>
14 #include <bitset>
15 
16 using namespace std;
17 
18 #define REP(i, n) for (int i = 0; i < (n); ++i)
19 #define eps 1e-9
20 #define lc id << 1
21 #define rc id << 1 | 1
22 #define lson low, mid, lc
23 #define rson mid + 1, high, rc
24 
25 typedef long long ll;
26 typedef pair<int, int> pii;
27 
28 const int INF = 0x7fffffff;
29 const int maxn = 5e5;
30 struct Node { int ans, lans, rans; };
31 int n, q, T;
32 int ans[maxn], a[maxn], lans[maxn], rans[maxn];
33 char opt[5];
34 
35 void push_up(int id, int low, int mid, int high) {
36     lans[id] = lans[lc]; rans[id] = rans[rc];
37     ans[id] = max(ans[lc], ans[rc]);
38     if (a[mid] < a[mid + 1]) {
39         if (lans[lc] == mid - low + 1) { lans[id] += lans[rc]; }
40         if (rans[rc] == high - mid) { rans[id] += rans[lc]; }
41         ans[id] = max(ans[id], rans[lc] + lans[rc]);
42     }
43 }
44 void build(int low, int high, int id) {
45     if (low == high) {
46         scanf("%d", &a[low]); ans[id] = lans[id] = rans[id] = 1; return;
47     }
48     int mid = (low + high) / 2; build(lson); build(rson);
49     push_up(id, low, mid, high);
50 }
51 void update(int p, int k, int low, int high, int id) {
52     if (low == high) { a[low] = k; return; }
53     int mid = (low + high) / 2;
54     if (p <= mid) { update(p, k, lson); }
55     else { update(p, k, rson); } push_up(id, low, mid, high);
56 }
57 Node query(int l, int r, int low, int high, int id) {
58     if (l == low && r == high) {
59         return Node{ans[id], lans[id], rans[id]};
60     }
61     int mid = (low + high) / 2;
62     if (r <= mid) { return query(l, r, lson); }
63     else if (l >= mid + 1) { return query(l, r, rson); }
64     else {
65         Node t1 = query(l, mid, lson), t2 = query(mid + 1, r, rson), ret;
66         ret.lans = t1.lans; ret.rans = t2.rans;
67         ret.ans = max(t1.ans, t2.ans);
68         if (a[mid] < a[mid + 1]) {
69             if (t1.lans == mid - l + 1) { ret.lans += t2.lans; }
70             if (t2.rans == r - mid) { ret.rans += t1.rans; }
71             ret.ans = max(ret.ans, t1.rans + t2.lans);
72         }
73         return ret;
74     }
75 }
76 
77 int main() {
78 #ifdef __AiR_H
79     freopen("in.txt", "r", stdin);
80 //    freopen("out.txt", "w", stdout);
81 #endif // __AiR_H
82     scanf("%d", &T); int a, b;
83     while (T--) {
84         scanf("%d %d", &n, &q); build(1, n, 1);
85         while (q--) {
86             scanf("%s %d %d", opt, &a, &b);
87             if (opt[0] == 'U') { update(a + 1, b, 1, n, 1); }
88             else { printf("%d
", query(a + 1, b + 1, 1, n, 1).ans); }
89         }
90     }
91     return 0;
92 }
View Code

2 HDU 5316 Magician 

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <queue>
  7 #include <vector>
  8 #include <stack>
  9 #include <map>
 10 #include <set>
 11 #include <cmath>
 12 #include <cctype>
 13 #include <ctime>
 14 
 15 using namespace std;
 16 
 17 #define REP(i, n) for (int i = 0; i < (n); ++i)
 18 #define eps 1e-9
 19 #define SZ(x) ((int)x.size())
 20 #define PI acos(-1.0)
 21 #define lc id << 1
 22 #define rc id << 1 | 1
 23 #define lson low, mid, lc
 24 #define rson mid + 1, high, rc
 25 
 26 typedef long long ll;
 27 typedef unsigned long long ull;
 28 typedef pair<int, int> pii;
 29 const int maxn = 1e6;
 30 const ll INF = 1e18;
 31 struct Node { ll Max[4]; };
 32 int T, n, q, opt, a, b;
 33 ll Max[4][maxn];
 34 
 35 int check(int x, int y, int z) {
 36     if (((x & 2) | (y & 1)) != z) { return false; }
 37     if ((x & 1) && (y & 2)) { return false; }
 38     if (!(x & 1) && !(y & 2)) { return false; }
 39     return true;
 40 }
 41 ll add(ll x, ll y) {
 42     if (x == -INF || y == -INF) { return -INF; }
 43     return x + y;
 44 }
 45 void push_up(int id) {
 46     for (int i = 0; i < 4; ++i) {
 47         Max[i][id] = max(Max[i][lc], Max[i][rc]);
 48         for (int j = 0; j < 4; ++j) {
 49             for (int k = 0; k < 4; ++k) {
 50                 if (!check(j, k, i)) { continue; }
 51                 Max[i][id] = max(Max[i][id], add(Max[j][lc], Max[k][rc]));
 52             }
 53         }
 54     }
 55 }
 56 void build(int low, int high, int id) {
 57     if (low == high) {
 58         for (int i = 0; i < 4; ++i) { Max[i][id] = -INF; }
 59         if (low % 2 == 0) { scanf("%lld", &Max[0][id]); }
 60         else { scanf("%lld", &Max[3][id]); } return;
 61     }
 62     int mid = (low + high) / 2; build(lson); build(rson); push_up(id);
 63 }
 64 void update(int p, ll k, int low, int high, int id) {
 65     if (low == high) {
 66         if (low % 2 == 0) { Max[0][id] = k; }
 67         else { Max[3][id] = k; } return;
 68     }
 69     int mid = (low + high) / 2;
 70     if (p <= mid) { update(p, k, lson); }
 71     else { update(p, k, rson); } push_up(id);
 72 }
 73 Node query(int l, int r, int low, int high, int id) {
 74     if (l == low && r == high) {
 75         return Node{Max[0][id], Max[1][id], Max[2][id], Max[3][id]};
 76     }
 77     int mid = (low + high) / 2;
 78     if (r <= mid) { return query(l, r, lson); }
 79     else if (l >= mid + 1) { return query(l, r, rson); }
 80     else {
 81         Node t1 = query(l, mid, lson), t2 = query(mid + 1, r, rson), ret;
 82         for (int i = 0; i < 4; ++i) {
 83             ret.Max[i] = max(t1.Max[i], t2.Max[i]);
 84             for (int j = 0; j < 4; ++j) {
 85                 for (int k = 0; k < 4; ++k) {
 86                     if (!check(j, k, i)) { continue; }
 87                     ret.Max[i] = max(ret.Max[i], add(t1.Max[j], t2.Max[k]));
 88                 }
 89             }
 90         }
 91         return ret;
 92     }
 93 }
 94 
 95 int main() {
 96 #ifdef __AiR_H
 97     freopen("in.txt", "r", stdin);
 98 //    freopen("out.txt", "w", stdout);
 99 #endif // __AiR_H
100     scanf("%d", &T); Node t; ll ans;
101     while (T--) {
102         scanf("%d %d", &n, &q); build(1, n, 1);
103         while (q--) {
104             scanf("%d %d %d", &opt, &a, &b);
105             if (opt == 0) {
106                 t = query(a, b, 1, n, 1); ans = -INF;
107                 for (int i = 0; i < 4; ++i) {
108                     ans = max(ans, t.Max[i]);
109                 }
110                 printf("%lld
", ans);
111             } else { update(a, b, 1, n, 1); }
112         }
113     }
114     return 0;
115 }
View Code

1 POJ 3667 Hotel

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <stack>
 9 #include <map>
10 #include <set>
11 #include <cmath>
12 #include <cctype>
13 #include <ctime>
14 #include <bitset>
15 
16 using namespace std;
17 
18 #define REP(i, n) for (int i = 0; i < (n); ++i)
19 #define eps 1e-9
20 #define lc id << 1
21 #define rc id << 1 | 1
22 #define lson low, mid, lc
23 #define rson mid + 1, high, rc
24 
25 typedef long long ll;
26 typedef pair<int, int> pii;
27 
28 const int INF = 0x7fffffff;
29 const int maxn = 2e5 + 10;
30 int n, q, opt, x, d;
31 int sum[maxn], lsum[maxn], rsum[maxn], lazy[maxn];
32 
33 void build(int low, int high, int id) {
34     sum[id] = lsum[id] = rsum[id] = high - low + 1;
35     lazy[id] = -1; if (low == high) { return; }
36     int mid = (low + high) / 2; build(lson); build(rson);
37 }
38 void push_down(int id, int low, int mid, int high) {
39     if (lazy[id] == -1) { return; }
40     lazy[lc] = lazy[rc] = lazy[id];
41     sum[lc] = lsum[lc] = rsum[lc] = !lazy[id] ? mid - low + 1 : 0;
42     sum[rc] = lsum[rc] = rsum[rc] = !lazy[id] ? high - mid : 0;
43     lazy[id] = -1;
44 }
45 void push_up(int id, int low, int mid, int high) {
46     lsum[id] = lsum[lc]; rsum[id] = rsum[rc];
47     if (lsum[lc] == mid - low + 1) { lsum[id] += lsum[rc]; }
48     if (rsum[rc] == high - mid) { rsum[id] += rsum[lc]; }
49     sum[id] = max(max(sum[lc], sum[rc]), rsum[lc] + lsum[rc]);
50 }
51 void update(int l, int r, int k, int low, int high, int id) {
52     if (l == low && r == high) {
53         sum[id] = lsum[id] = rsum[id] = !k ? high - low + 1 : 0;
54         lazy[id] = k; return;
55     }
56     int mid = (low + high) / 2; push_down(id, low, mid, high);
57     if (r <= mid) { update(l, r, k, lson); }
58     else if (l >= mid + 1) { update(l, r, k, rson); }
59     else { update(l, mid, k, lson); update(mid + 1, r, k, rson); }
60     push_up(id, low, mid, high);
61 }
62 int query(int k, int low, int high, int id) {
63     if (low == high) { return low; }
64     int mid = (low + high) / 2; push_down(id, low, mid, high);
65     if (sum[lc] >= k) { return query(k, lson); }
66     else if (rsum[lc] + lsum[rc] >= k) { return mid - rsum[lc] + 1; }
67     else { return query(k, rson); }
68 }
69 
70 int main() {
71 #ifdef __AiR_H
72     freopen("in.txt", "r", stdin);
73 //    freopen("out.txt", "w", stdout);
74 #endif // __AiR_H
75     scanf("%d %d", &n, &q); int ans; build(1, n, 1);
76     while (q--) {
77         scanf("%d", &opt);
78         if (opt == 1) {
79             scanf("%d", &d);
80             if (sum[1] < d) { printf("0
"); continue; }
81             ans = query(d, 1, n, 1); printf("%d
", ans);
82             update(ans, ans + d - 1, 1, 1, n, 1);
83         } else {
84             scanf("%d %d", &x, &d);
85             update(x, x + d - 1, 0, 1, n, 1);
86         }
87     }
88     return 0;
89 }
View Code

1 Codeforces 46D Parking Lot

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <stack>
 9 #include <map>
10 #include <set>
11 #include <cmath>
12 #include <cctype>
13 #include <ctime>
14 #include <bitset>
15 
16 using namespace std;
17 
18 #define REP(i, n) for (int i = 0; i < (n); ++i)
19 #define eps 1e-9
20 #define lc id << 1
21 #define rc id << 1 | 1
22 #define lson low, mid, lc
23 #define rson mid + 1, high, rc
24 
25 typedef long long ll;
26 typedef pair<int, int> pii;
27 
28 const int INF = 0x7fffffff;
29 const int maxn = 1.1e5;
30 int n, a, b, q;
31 int l[maxn], r[maxn];
32 int sum[maxn * 4], lsum[maxn * 4], rsum[maxn * 4], lazy[maxn * 4];
33 
34 void build(int low, int high, int id) {
35     sum[id] = lsum[id] = rsum[id] = high - low + 1;
36     lazy[id] = -1; if (low == high) { return; }
37     int mid = (low + high) / 2; build(lson); build(rson);
38 }
39 void push_down(int id, int low, int mid, int high) {
40     if (lazy[id] == -1) { return; }
41     lazy[lc] = lazy[rc] = lazy[id];
42     sum[lc] = lsum[lc] = rsum[lc] = !lazy[id] ? mid - low + 1 : 0;
43     sum[rc] = lsum[rc] = rsum[rc] = !lazy[id] ? high - mid : 0;
44     lazy[id] = -1;
45 }
46 void push_up(int id, int low, int mid, int high) {
47     lsum[id] = lsum[lc]; rsum[id] = rsum[rc];
48     if (lsum[lc] == mid - low + 1) { lsum[id] += lsum[rc]; }
49     if (rsum[rc] == high - mid) { rsum[id] += rsum[lc]; }
50     sum[id] = max(max(sum[lc], sum[rc]), rsum[lc] + lsum[rc]);
51 }
52 void update(int l, int r, int k, int low, int high, int id) {
53     if (l == low && r == high) {
54         sum[id] = lsum[id] = rsum[id] = !k ? high - low + 1 : 0;
55         lazy[id] = k; return;
56     }
57     int mid = (low + high) / 2; push_down(id, low, mid, high);
58     if (r <= mid) { update(l, r, k, lson); }
59     else if (l >= mid + 1) { update(l, r, k, rson); }
60     else { update(l, mid, k, lson); update(mid + 1, r, k, rson); }
61     push_up(id, low, mid, high);
62 }
63 int query(int k, int low, int high, int id) {
64     if (low == high) { return low; }
65     int mid = (low + high) / 2; push_down(id, low, mid, high);
66     if (sum[lc] >= k) { return query(k, lson); }
67     else if (rsum[lc] + lsum[rc] >= k) { return mid - rsum[lc] + 1; }
68     else { return query(k, rson); }
69 }
70 
71 int main() {
72 #ifdef __AiR_H
73     freopen("in.txt", "r", stdin);
74 //    freopen("out.txt", "w", stdout);
75 #endif // __AiR_H
76     scanf("%d %d %d %d", &n, &a, &b, &q);
77     int n_t = n + a + b; build(1, n_t, 1); int ans, opt, x, t;
78     for (int i = 1; i <= q; ++i) {
79         scanf("%d %d", &opt, &x);
80         if (opt == 1) {
81             t = x + a + b;
82             if (sum[1] < t) { printf("-1
"); continue; }
83             ans = query(t, 1, n_t, 1);
84             l[i] = ans + a; r[i] = l[i] + x - 1;
85             update(l[i], r[i], 1, 1, n_t, 1);
86             printf("%d
", ans - 1);
87         } else {
88             update(l[x], r[x], 0, 1, n_t, 1);
89         }
90     }
91     return 0;
92 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zhaoyz/p/7675456.html