Hacker Cups and Balls Gym - 101234A 二分+線段樹
摘要：
題目:題目連結
題意:有編號從1到n的n個球和n個杯子. 每一個杯子裡有一個球, 進行m次排序操作，每次操作給出l,r. 如果l<r，將[l,r]範圍內的球按升序排序, 否則降序排, 問中間位置的數是多少.
思路:
暴力複雜度為m*nlog(n), 不能暴力排...
題目:題目連結
題意:有編號從1到n的n個球和n個杯子. 每一個杯子裡有一個球, 進行m次排序操作，每次操作給出l,r. 如果l<r，將[l,r]範圍內的球按升序排序, 否則降序排, 問中間位置的數是多少.
思路:
暴力複雜度為m*nlog(n), 不能暴力排序
二分答案, 對於當前mid, 我們將大於等於mid的數記為1, 否則記0, 則排序就是將某個區間的數改為1或0, 通過線段樹區間更新可以方便的做到, 對排序後的結果查詢判斷二分割槽間應該取左還是取右, 若中間的數是1, 則說明答案大於等於當前的數, l右移, 否則左移
AC程式碼:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <vector>
8 #include <string>
9 #include <map>
10 #include <set>
11 #include <unordered_map>
12 #include <unordered_set>
13 #include <queue>
14 #include <stack>
15 #include <list>
16
17 #define FRER() freopen("in.txt", "r", stdin)
18 #define FREW() freopen("out.txt", "w", stdout)
19
20 #define INF 0x3f3f3f3f
21 #define eps 1e-8
22
23 using namespace std;
24
25 const int maxn = 1e5 + 5;
26
27 int a[maxn], ql[maxn], qr[maxn], tree[maxn << 2], lazy[maxn << 2];
28
29 void build(int l, int r, int rt, int num) {
30lazy[rt] = 0;
31if(l == r) {
32tree[rt] = (a[l] >= num);
33return ;
34}
35int m = (l + r) >> 1;
36build(l, m, rt << 1, num);
37build(m + 1, r, rt << 1|1, num);
38tree[rt] = tree[rt << 1] + tree[rt << 1|1];
39 }
40
41 void pushdown(int l, int r, int rt) {
42int m = (l + r) >> 1;
43lazy[rt << 1] = lazy[rt << 1|1] = lazy[rt];
44if(lazy[rt] == 1) {
45tree[rt << 1|1] = min(tree[rt], r - m);
46tree[rt << 1] = tree[rt] - tree[rt << 1|1];
47}
48else if(lazy[rt] == 2){
49tree[rt << 1] = min(tree[rt], m - l + 1);
50tree[rt << 1|1] = tree[rt] - tree[rt << 1];
51}
52lazy[rt] = 0;
53 }
54
55 int querySum(int x, int y, int l, int r, int rt) {
56if(x <= l && y >= r) return tree[rt];
57if(lazy[rt]) pushdown(l, r, rt);
58int m = (l + r) >> 1, sum = 0;
59if(x <= m) sum += querySum(x, y, l, m, rt << 1);
60if(y > m) sum += querySum(x, y, m + 1, r, rt << 1|1);
61return sum;
62 }
63
64 int query(int pos, int l, int r, int rt) {
65if(l == r) return tree[rt];
66if(lazy[rt]) pushdown(l, r, rt);
67int m = (l + r) >> 1;
68if(pos <= m) return query(pos, l, m, rt << 1);
69else return query(pos, m + 1, r, rt << 1|1);
70 }
71
72 void update(int x, int y, int l, int r, int rt, int flag, int sum) {
73if(x <= l && y >= r) {
74tree[rt] = sum;
75lazy[rt] = flag;
76return ;
77}
78if(lazy[rt]) pushdown(l, r, rt);
79int m = (l + r) >> 1;
80if(y <= m) update(x, y, l, m, rt << 1, flag, sum);
81else if(x > m) update(x, y, m + 1, r, rt << 1|1, flag, sum);
82else {
83int lsum, rsum;
84if(flag== 1) {
85rsum = min(sum, y - m);
86lsum = sum - rsum;
87}
88else if(flag == 2){
89lsum = min(sum, m - x + 1);
90rsum = sum - lsum;
91}
92update(x, m, l, m, rt << 1, flag, lsum);
93update(m + 1, y, m + 1, r, rt << 1|1, flag, rsum);
94}
95tree[rt] = tree[rt << 1] + tree[rt << 1|1];
96 }
97
98 bool judge(int n, int m, int mid) {
99build(1, n, 1, mid);
100for(int i = 0; i < m; ++i) {
101int sum = querySum(min(ql[i], qr[i]), max(ql[i], qr[i]), 1, n, 1);
102if(ql[i] <= qr[i]) update(ql[i], qr[i], 1, n, 1, 1, sum);
103else update(qr[i], ql[i], 1, n, 1, 2, sum);
104}
105return query((1 + n) >> 1, 1, n, 1);
106 }
107
108 int main()
109 {
110//FRER();
111ios::sync_with_stdio(0);
112cin.tie(0);
113
114int n, m;
115cin >> n >> m;
116for(int i = 1; i <= n; ++i) cin >> a[i];
117for(int i = 0; i < m; ++i) cin >> ql[i] >> qr[i];
118int l = 1, r = n, ans;
119while(l <= r) {
120int mid = (l + r) >> 1;
121if(judge(n, m, mid))
122ans = mid, l = mid + 1;
123else r = mid - 1;
124}
125cout << ans << endl;
126return 0;
127 }