Bzoj[Usaco2018 Feb]5194 Snow Boots（线段树）

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define uint unsigned int
 4 #define ull unsigned long long
 5 using namespace std;
 6 const int maxn = 100010;
 7 struct enkidu {
 8     int di, si, id;
 9 }ask[maxn], a[maxn];
10 struct shiki {
11     int l, r, l_lin, r_lin;
12     int max_cnt;
13 }tree[maxn << 2];
14 //l_lin表示这个区间从左边开始连续的不能走的长度
15 //r_lin表示这个区间从右边开始连续的不能走的长度 
16 int n, m; 
17 int ans[maxn];
18 
19 inline int read() {
20     int x = 0, y = 1;
21     char ch = getchar();
22     while(!isdigit(ch)) {
23         if(ch == ‘-‘) y = -1;
24         ch = getchar();
25     }
26     while(isdigit(ch)) {
27         x = (x << 1) + (x << 3) + ch - ‘0‘;
28         ch = getchar();
29     }
30     return x * y;
31 }
32 
33 inline bool cmp(enkidu a, enkidu b) {
34     return a.si < b.si;
35 }
36 
37 inline void maintain(int pos) {
38     int ls = pos << 1, rs = pos << 1 | 1;
39     if(tree[ls].r - tree[ls].l + 1 == tree[ls].max_cnt) 
40         tree[pos].l_lin = tree[ls].max_cnt + tree[rs].l_lin;
41     else tree[pos].l_lin = tree[ls].l_lin;
42     if(tree[rs].r - tree[rs].l + 1 == tree[rs].max_cnt)
43         tree[pos].r_lin = tree[ls].r_lin + tree[rs].max_cnt;
44     else tree[pos].r_lin = tree[rs].r_lin;
45     tree[pos].max_cnt = max(tree[ls].max_cnt, tree[rs].max_cnt);
46     tree[pos].max_cnt = max(tree[pos].max_cnt, tree[ls].r_lin + tree[rs].l_lin);
47 }
48 
49 void build(int pos, int l, int r) {
50     tree[pos].l = l, tree[pos].r = r; 
51     if(l == r) {
52         tree[pos].l_lin = tree[pos].r_lin = tree[pos].max_cnt = 1;
53         return;
54     }
55     int  mid = l + r >> 1;
56     build(pos << 1, l, mid);
57     build(pos << 1 | 1, mid + 1, r);
58     maintain-(pos);
59 }
60 
61 void update(int pos, int aim, int l, int r) {
62     if(l == r && l == aim) {
63         tree[pos].max_cnt = tree[pos].l_lin = tree[pos].r_lin = 0;
64         return; 
65     }
66     int mid = l + r >> 1;
67     if(aim <= mid) update(pos << 1, aim, l, mid);
68     else update(pos << 1 | 1, aim, mid + 1, r);
69     maintain(pos);
70 }
71 
72 int main() {
73     n = read(), m = read();
74     for(int i = 1; i <= n; ++i) {
75         a[i].si = read();
76         a[i].id = i;
77     }
78     for(int i = 1; i <= m; ++i) {
79         ask[i].si = read(), ask[i].di = read();
80         ask[i].id = i;
81     }
82     sort(ask + 1, ask + m + 1, cmp);
83     sort(a + 1, a + n + 1, cmp);
84     build(1, 1, n);
85     int brick = 0;//砖，表示第几块砖
86     for(int i = 1; i <= m; ++i) {
87         while(brick < n && a[brick + 1].si <= ask[i].si) {//如果可以走 
88             brick++;
89             update(1, a[brick].id, 1, n);
90         }
91         if(tree[1].max_cnt < ask[i].di) ans[ask[i].id] = 1;
92     } 
93     for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
94     return 0;
95 }