您的位置: 首页  >  IT文章  >  线段树(2)

线段树(2)

分类: IT文章 • 2024-06-27 13:41:37

hdu 4366 Successor

做法：对每个人按照ability由大到小排序，把loyalty插入到线段树里面，dfs处理出每个点所在的区间，然后区间查询，单点更新。（这里学到了查询区间最大值所在id的方法）。。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <queue>
  7 #include <stack>
  8 
  9 using namespace std;
 10 
 11 #define LL long long
 12 #define eps 1e-6
 13 #define inf 0x3f3f3f3f
 14 #define MP make_pair
 15 #define N 250020
 16 #define M 1000020
 17 #pragma comment(linker, "/STACK:1024000000,1024000000")
 18 #define Pi acos(-1.0)
 19 #define ls (i << 1)
 20 #define rs (ls | 1)
 21 #define md ((ll + rr) >> 1)
 22 #define lson ll, md, ls
 23 #define rson md + 1, rr, rs
 24 
 25 int fst[N], vv[N], nxt[N], e;
 26 void init(){
 27     memset(fst, -1, sizeof fst); e = 0;
 28 }
 29 void add(int u, int v){
 30     vv[e] = v, nxt[e] = fst[u], fst[u] = e++;
 31 }
 32 int in[N], out[N], lab[N], dc;
 33 void dfs(int u){
 34     in[u] = ++dc;
 35     lab[dc] = u;
 36     for(int i = fst[u]; ~i; i = nxt[i]){
 37         int v = vv[i];
 38         dfs(v);
 39     }
 40     out[u] = dc;
 41 }
 42 struct node{
 43     int id, val, loy;
 44     node(){}
 45     node(int _loy, int _val, int _id){
 46         loy = _loy, val = _val, id = _id;
 47     }
 48     bool operator < (const node &b) const{
 49         return val > b.val;
 50     }
 51 }b[N];
 52 
 53 int mx[N<<2], val[N];
 54 void build(int ll, int rr, int i){
 55     mx[i] = -1;
 56     if(ll == rr) return ;
 57     build(lson), build(rson);
 58 }
 59 void push_up(int i){
 60     if(val[mx[ls]] > val[mx[rs]])
 61         mx[i] = mx[ls];
 62     else mx[i] = mx[rs];
 63 }
 64 void update(int p, int v, int ll, int rr, int i){
 65     if(ll == rr){
 66         val[ll] = v;
 67         mx[i] = ll;
 68         return ;
 69     }
 70     if(p <= md) update(p, v, lson);
 71     else update(p, v, rson);
 72     push_up(i);
 73 }
 74 int query(int l, int r, int ll, int rr, int i){
 75     if(l > r) return -1;
 76     if(ll == l && r == rr)
 77         return mx[i];
 78     if(r <= md) return query(l, r, lson);
 79     else if(l > md) return query(l, r, rson);
 80     else{
 81         int ret1 = query(l, md, lson);
 82         int ret2 = query(md + 1, r, rson);
 83         if(ret1 == -1) return ret2;
 84         if(ret2 == -1) return ret1;
 85         return val[ret1] >= val[ret2] ? ret1 : ret2;
 86     }
 87 }
 88 
 89 int ans[N];
 90 int main(){
 91     int cas;
 92     scanf("%d", &cas);
 93     while(cas--){
 94         int n, m;
 95         scanf("%d%d", &n, &m);
 96         init();
 97         for(int i = 1; i < n; ++i){
 98             int u, val, loy;
 99             scanf("%d%d%d", &u, &loy, &val);
100             add(u, i);
101             b[i] = node(loy, val, i);
102         }
103         dc = 0;
104         dfs(0);
105         sort(b + 1, b + n);
106         build(1, n, 1);
107         memset(val, -1, sizeof val);
108         for(int i = 1, j; i < n; i = j){
109             j = i;
110             while(j < n && b[i].val == b[j].val){
111                 int k = b[j].id;
112                 int t = query(in[k] + 1, out[k], 1, n, 1);
113                 if(t == -1) ans[k] = -1;
114                 else ans[k] = lab[t];
115                 j++;
116             }
117             j = i;
118             while(j < n && b[i].val == b[j].val){
119                 update(in[b[j].id], b[j].loy, 1, n, 1);
120                 j++;
121             }
122         }
123         while(m--){
124             int i;
125             scanf("%d", &i);
126             printf("%d
", ans[i]);
127         }
128     }
129     return 0;
130 }
View Code

 hdu 3397 Sequence operation

区间赋值，异或。记录左边连续最大，右边连续最大，总的连续最大，区间1和0的个数。（询问的时候返回连续最大的1的个数那里老是写挫了！！！）

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <queue>
  7 using namespace std;
  8 
  9 #define LL long long
 10 #define eps 1e-8
 11 #define inf 0x3f3f3f3f
 12 #define MP make_pair
 13 #define N 100020
 14 #define M 200020
 15 #pragma comment(linker, "/STACK:1024000000,1024000000")
 16 #define Pi acos(-1.0)
 17 #define mod 1000000007
 18 #define ls (i << 1)
 19 #define rs (ls | 1)
 20 #define md ((ll + rr) >> 1)
 21 #define lson ll, md, ls
 22 #define rson md + 1, rr, rs
 23 
 24 int mxL[2][N<<2], mxR[2][N<<2], mx[2][N<<2];
 25 int sum[2][N<<2], cov[N<<2], Xor[N<<2];
 26 
 27 void init(int x, int i, int len){
 28     mxL[x][i] = mxR[x][i] = mx[x][i] = len;
 29     sum[x][i] = len;
 30 }
 31 
 32 void push_up(int x, int i, int ll, int rr){
 33     mxL[x][i] = mxL[x][ls], mxR[x][i] = mxR[x][rs];
 34     mx[x][i] = max(mx[x][ls], mx[x][rs]);
 35     mx[x][i] = max(mx[x][i], mxR[x][ls] + mxL[x][rs]);
 36     if(mxL[x][ls] == md - ll + 1)
 37         mxL[x][i] += mxL[x][rs];
 38     if(mxR[x][rs] == rr - md)
 39         mxR[x][i] += mxR[x][ls];
 40     sum[x][i] = sum[x][ls] + sum[x][rs];
 41 }
 42 void build(int ll, int rr, int i){
 43     cov[i] = -1, Xor[i] = 0;
 44     if(ll == rr){
 45         int v;
 46         scanf("%d", &v);
 47         init(v, i, 1);
 48         init(v^1, i, 0);
 49         return ;
 50     }
 51     build(lson), build(rson);
 52     push_up(0, i, ll, rr);
 53     push_up(1, i, ll, rr);
 54 }
 55 void change(int i){
 56     Xor[i] ^= 1;
 57     swap(mxL[0][i], mxL[1][i]);
 58     swap(mxR[0][i], mxR[1][i]);
 59     swap(mx[0][i], mx[1][i]);
 60     swap(sum[0][i], sum[1][i]);
 61 }
 62 void push_down(int i, int ll, int rr){
 63     if(cov[i] != -1){
 64         int x = cov[i];
 65         cov[ls] = cov[rs] = x;
 66         Xor[ls] = Xor[rs] = 0;
 67         init(x, ls, md - ll + 1);
 68         init(x, rs, rr - md);
 69         init(x^1, ls, 0);
 70         init(x^1, rs, 0);
 71         cov[i] = -1;
 72     }
 73     if(Xor[i]){
 74         change(ls), change(rs);
 75         Xor[i] = 0;
 76     }
 77 }
 78 void update(int l, int r, int op, int ll, int rr, int i){
 79     if(l == ll && r == rr){
 80         if(op == 0 || op == 1){
 81             init(op, i, rr - ll + 1);
 82             init(op ^ 1, i, 0);
 83             cov[i] = op, Xor[i] = 0;
 84         }
 85         else{
 86             change(i);
 87         }
 88         return ;
 89     }
 90     push_down(i, ll, rr);
 91     if(r <= md) update(l, r, op, lson);
 92     else if(l > md) update(l, r, op, rson);
 93     else
 94         update(l, md, op, lson), update(md + 1, r, op, rson);
 95     push_up(0, i, ll, rr);
 96     push_up(1, i, ll, rr);
 97 }
 98 
 99 int query(int l, int r, int op, int ll, int rr, int i){
100     if(l == ll && r == rr){
101         if(op == 4)
102             return mx[1][i];
103         else return sum[1][i];
104     }
105     push_down(i, ll, rr);
106     int ret;
107     if(r <= md) ret = query(l, r, op, lson);
108     else if(l > md) ret = query(l, r, op, rson);
109     else{
110         int ret1 = query(l, md, op, lson);
111         int ret2 = query(md + 1, r, op, rson);
112         if(op == 4){
113             ret = max(ret1, ret2);
114             ret = max(ret, min(mxR[1][ls], md - l + 1) + min(mxL[1][rs], r - md));
115         }
116         else ret = ret1 + ret2;
117     }
118     push_up(0, i, ll, rr);
119     push_up(1, i, ll, rr);
120     return ret;
121 }
122 int main(){
123     int cas;
124     //freopen("tt.txt", "r", stdin);
125     scanf("%d", &cas);
126     while(cas--){
127         int n, m;
128         scanf("%d%d", &n, &m);
129         build(1, n, 1);
130         while(m--){
131             int op, L, R;
132             scanf("%d%d%d", &op, &L, &R);
133             ++L, ++R;
134             if(op <= 2)
135                 update(L, R, op, 1, n, 1);
136             else printf("%d
", query(L, R, op, 1, n, 1));
137         }
138     }
139     return 0;
140 }
View Code

 hdu 2871  Memory Control

区间更新，合并。。好题。。以前敲的时候感觉好难，现在就感觉还行。（细节没注意。push_down的时候tot[i] == 0的时候没写，wa了一发。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <queue>
  7 using namespace std;
  8 
  9 #define LL long long
 10 #define eps 1e-8
 11 #define inf 0x3f3f3f3f
 12 #define MP make_pair
 13 #define N 50020
 14 #define M 200020
 15 #pragma comment(linker, "/STACK:1024000000,1024000000")
 16 #define Pi acos(-1.0)
 17 #define mod 1000000007
 18 #define ls (i << 1)
 19 #define rs (ls | 1)
 20 #define md ((ll + rr) >> 1)
 21 #define lson ll, md, ls
 22 #define rson md + 1, rr, rs
 23 
 24 int cov[N<<2], mxL[N<<2], mxR[N<<2], mx[N<<2], tot[N<<2], id[N<<2], L[N], R[N];
 25 void build(int ll, int rr, int i){
 26     cov[i] = -1, id[i] = 0, tot[i] = 0;
 27     mxL[i] = mxR[i] = mx[i] = rr - ll + 1;
 28     if(ll == rr) return ;
 29     build(lson), build(rson);
 30 }
 31 
 32 int cnt;
 33 void f(int i, int len){
 34     mxL[i] = mxR[i] = mx[i] = len;
 35 }
 36 void push_down(int i, int ll, int rr){
 37     if(cov[i] != -1){
 38         cov[ls] = cov[rs] = cov[i];
 39         id[ls] = id[rs] = id[i];
 40         if(cov[i] == 0){
 41             f(ls, md - ll + 1);
 42             f(rs, rr - md);
 43         }
 44         else{
 45             f(ls, 0);
 46             f(rs, 0);
 47         }
 48         if(tot[i] == 0) tot[ls] = tot[rs] = 0;
 49         cov[i] = -1;
 50     }
 51 }
 52 void push_up(int i, int ll, int rr){
 53     mxL[i] = mxL[ls], mxR[i] = mxR[rs];
 54     mx[i] = max(mxR[ls] + mxL[rs], max(mx[ls], mx[rs]));
 55     tot[i] = tot[ls] + tot[rs];
 56     if(mxL[ls] == md - ll + 1)
 57         mxL[i] += mxL[rs];
 58     if(mxR[rs] == rr - md)
 59         mxR[i] += mxR[ls];
 60 }
 61 void update(int l, int r, int v, int ll, int rr, int i){
 62     if(l == ll && r == rr){
 63         cov[i] = v;
 64         if(v == 0)
 65             id[i] = 0, mxL[i] = mxR[i] = mx[i] = rr - ll + 1;
 66         else
 67             id[i] = cnt, mxL[i] = mxR[i] = mx[i] = 0;
 68         return ;
 69     }
 70     push_down(i, ll, rr);
 71     if(r <= md) update(l, r, v, lson);
 72     else if(l > md) update(l, r, v, rson);
 73     else
 74         update(l, md, v, lson), update(md + 1, r, v, rson);
 75     push_up(i, ll, rr);
 76 }
 77 void update(int p, int v, int ll, int rr, int i){
 78     if(ll == rr){
 79         tot[i] = v; return ;
 80     }
 81     push_down(i, ll, rr);
 82     if(p <= md) update(p, v, lson);
 83     else update(p, v, rson);
 84     push_up(i, ll, rr);
 85 }
 86 int query(int v, int ll, int rr, int i){
 87     if(ll == rr)
 88         return ll;
 89     push_down(i, ll, rr);
 90     int ret;
 91     if(mx[ls] >= v)
 92         ret = query(v, lson);
 93     else if(mxR[ls] + mxL[rs] >= v)
 94         ret = md - mxR[ls] + 1;
 95     else
 96         ret = query(v, rson);
 97     push_up(i, ll, rr);
 98     return ret;
 99 }
100 int find(int p, int ll, int rr, int i){
101     if(ll == rr)
102         return id[i];
103     push_down(i, ll, rr);
104     int ret;
105     if(p <= md) ret = find(p, lson);
106     else ret = find(p, rson);
107     push_up(i, ll, rr);
108     return ret;
109 }
110 int get(int v, int ll, int rr, int i){
111     if(ll == rr)
112         return ll;
113     push_down(i, ll, rr);
114     int ret;
115     if(tot[ls] >= v) ret = get(v, lson);
116     else ret = get(v - tot[ls], rson);
117     push_up(i, ll, rr);
118     return ret;
119 }
120 int main(){
121     int n, m;
122     while(scanf("%d%d", &n, &m) != EOF){
123         build(1, n, 1);
124         char s[10];
125         while(m--){
126             scanf("%s", s);
127             if(s[0] == 'R'){
128                 update(1, n, 0, 1, n, 1);
129                 cnt = 0;
130                 tot[1] = 0;
131                 puts("Reset Now");
132                 continue;
133             }
134             int v; scanf("%d", &v);
135             if(s[0] == 'N'){
136                 if(mx[1] < v){
137                     puts("Reject New"); continue;
138                 }
139                 int ans = query(v, 1, n, 1);
140                 printf("New at %d
", ans);
141                 L[++cnt] = ans, R[cnt] = ans + v - 1;
142                 update(ans, ans + v - 1, 1, 1, n, 1);
143                 update(ans, 1, 1, n, 1);
144             }
145             else if(s[0] == 'F'){
146                 int ret = find(v, 1, n, 1);
147                 if(ret == 0){
148                     puts("Reject Free"); continue;
149                 }
150                 printf("Free from %d to %d
", L[ret], R[ret]);
151                 update(L[ret], R[ret], 0, 1, n, 1);
152                 update(L[ret], 0, 1, n, 1);
153             }
154             else{
155                 if(tot[1] < v){
156                     puts("Reject Get"); continue;
157                 }
158                 printf("Get at %d
", get(v, 1, n, 1));
159             }
160         }
161         puts("");
162     }
163     return 0;
164 }
View Code

 hdu 1540 Tunnel Warfare

区间合并。。没什么难度了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <queue>
  7 using namespace std;
  8 
  9 #define LL long long
 10 #define eps 1e-8
 11 #define inf 0x3f3f3f3f
 12 #define MP make_pair
 13 #define N 100020
 14 #define M 200020
 15 #pragma comment(linker, "/STACK:1024000000,1024000000")
 16 #define Pi acos(-1.0)
 17 #define mod 1000000007
 18 #define ls (i << 1)
 19 #define rs (ls | 1)
 20 #define md ((ll + rr) >> 1)
 21 #define lson ll, md, ls
 22 #define rson md + 1, rr, rs
 23 
 24 int mxL[N<<2], mxR[N<<2], mx[N<<2];
 25 int a[N], tot;
 26 bool vis[N];
 27 void build(int ll, int rr, int i){
 28     mxL[i] = mxR[i] = mx[i] = rr - ll + 1;
 29     if(ll == rr) return;
 30     build(lson), build(rson);
 31 }
 32 
 33 void push_up(int i, int ll, int rr){
 34     mxL[i] = mxL[ls], mxR[i] = mxR[rs];
 35     mx[i] = max(mxR[ls] + mxL[rs], max(mx[ls], mx[rs]));
 36     if(mxL[i] == md - ll + 1)
 37         mxL[i] += mxL[rs];
 38     if(mxR[i] == rr - md)
 39         mxR[i] += mxR[ls];
 40 }
 41 void update(int p, int v, int ll, int rr, int i){
 42     if(ll == rr){
 43         mxL[i] = mxR[i] = mx[i] = v;
 44         return ;
 45     }
 46     if(p <= md) update(p, v, lson);
 47     else update(p, v, rson);
 48     push_up(i, ll, rr);
 49 }
 50 
 51 int queryL(int l, int r, int ll, int rr, int i){
 52     if(l == ll && r == rr)
 53         return mxR[i];
 54     if(r <= md) return queryL(l, r, lson);
 55     if(l > md) return queryL(l, r, rson);
 56     int ret = queryL(md + 1, r, rson);
 57     if(ret == r - md)
 58         ret += queryL(l, md, lson);
 59     return ret;
 60 }
 61 int queryR(int l, int r, int ll, int rr, int i){
 62     if(l == ll && r == rr)
 63         return mxL[i];
 64     if(r <= md) return queryR(l, r, lson);
 65     if(l > md) return queryR(l, r, rson);
 66     int ret = queryR(l, md, lson);
 67     if(ret == md - l + 1)
 68         ret += queryR(md + 1, r, rson);
 69     return ret;
 70 }
 71 int main(){
 72     int n, m;
 73    // freopen("tt.txt", "r", stdin);
 74     while(scanf("%d%d", &n, &m) != EOF){
 75         build(1, n, 1);
 76         memset(vis, 0, sizeof vis);
 77         tot = 0;
 78         char s[2];
 79         int p;
 80         while(m--){
 81             scanf("%s", s);
 82             if(s[0] == 'D'){
 83                 scanf("%d", &p);
 84                 a[++tot] = p;
 85                 vis[p] = 1;
 86                 update(p, 0, 1, n, 1);
 87             }
 88             else if(s[0] == 'Q'){
 89                 scanf("%d", &p);
 90                 if(vis[p]){
 91                     puts("0"); continue;
 92                 }
 93                 int ret = 1;
 94                 if(p - 1 > 0)
 95                     ret += queryL(1, p - 1, 1, n, 1);
 96                 if(p + 1 <= n)
 97                     ret += queryR(p + 1, n, 1, n, 1);
 98                 printf("%d
", ret);
 99             }
100             else{
101                 if(tot > 0){
102                     vis[a[tot]] = 0;
103                     update(a[tot--], 1, 1, n, 1);
104                 }
105             }
106         }
107     }
108     return 0;
109 }
View Code

hdu 4288 Coder

离散化，单点更新，要用long long。num[i]表示区间i内有num[i]个存在的元素。然后sum[j][i] = sum[j][ls] + sum[(5-num[ls]%5+j)%5]（一开始推错了）。。最后询问的时候输出sum[3][1]就好了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <queue>
 7 using namespace std;
 8 
 9 #define LL long long
10 #define eps 1e-8
11 #define inf 0x3f3f3f3f
12 #define MP make_pair
13 #define N 100020
14 #define M 200020
15 #pragma comment(linker, "/STACK:1024000000,1024000000")
16 #define Pi acos(-1.0)
17 #define mod 1000000007
18 #define ls (i << 1)
19 #define rs (ls | 1)
20 #define md ((ll + rr) >> 1)
21 #define lson ll, md, ls
22 #define rson md + 1, rr, rs
23 
24 LL sum[5][N<<2];
25 int num[N<<2];
26 void push_up(int i){
27     num[i] = num[ls] + num[rs];
28     int tmp = 5 - num[ls] % 5;
29     for(int j = 0; j < 5; ++j)
30         sum[j][i] = sum[j][ls] + sum[(j+tmp) % 5][rs];
31 }
32 
33 int a[N], b[N], op[N];
34 void update(int p, int op, int ll, int rr, int i){
35     if(ll == rr){
36         sum[1][i] = op ? b[p] : 0;
37         num[i] = op;
38         return ;
39     }
40     if(p <= md) update(p, op, lson);
41     else update(p, op, rson);
42     push_up(i);
43 }
44 
45 int main(){
46     //freopen("tt.txt", "r", stdin);
47     int m;
48     while(scanf("%d", &m) != EOF){
49         memset(sum, 0, sizeof sum);
50         memset(num, 0, sizeof num);
51         int  n = 0, tot = 0, v;
52         char s[5];
53         for(int i = 0; i < m; ++i){
54             scanf("%s", s);
55             if(s[0] == 'a'){
56                 scanf("%d", &a[i]);
57                 op[i] = 1;
58                 b[++n] = a[i];
59             }
60             else if(s[0] == 'd'){
61                 scanf("%d", &a[i]);
62                 op[i] = 0;
63             }
64             else op[i] = 2;
65         }
66         sort(b + 1, b + n + 1);
67         for(int i = 0; i < m; ++i){
68             if(op[i] == 1 || op[i] == 0){
69                 int p = lower_bound(b + 1, b + n + 1, a[i]) - b;
70                 update(p, op[i], 1, n, 1);
71             }
72             else printf("%lld
", sum[3][1]);
73         }
74     }
75     return 0;
76 }
View Code

 hdu 4521 小明系列问题——小明序列

给你一个序列，求最长上升子序列且 序列中相邻的数的下标要大于d。。

按照 x 排序，x相同就按照下标由大到小排。按 x值 扫过去，用线段树维护下标id的最长上升序列的值。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<string>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<set>
 8 using namespace std;
 9 
10 #define ULL unsigned long long
11 #define eps 1e-9
12 #define inf 0x3f3f3f3f
13 #define FOR(i,s,t) for(int i = s; i < t; ++i )
14 #define REP(i,s,t) for( int i = s; i <= t; ++i )
15 #define pii pair<int,int>
16 #define MP make_pair
17 #define ls i << 1
18 #define rs ls | 1
19 #define md ((ll + rr) >> 1)
20 #define lson ll, md, ls
21 #define rson md + 1, rr, rs
22 #define LL long long
23 #define N 150010
24 #define M 200020
25 #define mod 1000000007
26 
27 struct node{
28     int x, id;
29     bool operator < (const node &b) const{
30         return x < b.x || (x == b.x && id > b.id);
31     }
32 }b[N];
33 int mx[N<<2];
34 void update(int p, int v, int ll, int rr, int i){
35     if(ll == rr){
36         mx[i] = max(mx[i], v);
37         return ;
38     }
39     if(p <= md) update(p, v, lson);
40     else update(p, v, rson);
41     mx[i] = max(mx[ls], mx[rs]);
42 }
43 int query(int l, int r, int ll, int rr, int i){
44     if(l == ll && r == rr)
45         return mx[i];
46     if(r <= md) return query(l, r, lson);
47     if(l > md) return query(l, r, rson);
48     return max(query(l, md, lson), query(md + 1, r, rson));
49 }
50 int a[N];
51 int main(){
52     int n, d;
53     while(scanf("%d%d", &n, &d) != EOF){
54         for(int i = 1; i <= n; ++i){
55             scanf("%d", &a[i]);
56             b[i].x = a[i], b[i].id = i;
57         }
58         sort(b + 1, b + 1 + n);
59         int ans = 0, dp;
60         memset(mx, 0, sizeof mx);
61         for(int i = 1; i <= n; ++i){
62             if(b[i].id - d - 1 > 0)
63                 dp = query(1, b[i].id - d - 1, 1, n, 1) + 1;
64             else dp = 1;
65             ans = max(dp, ans);
66             update(b[i].id, dp, 1, n, 1);
67         }
68         printf("%d
", ans);
69     }
70     return 0;
71 }
View Code

hdu 1542  Atlantis

矩形面积并。。发现不用push_down，感觉好厉害。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<string>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<set>
 8 using namespace std;
 9 
10 #define ULL unsigned long long
11 #define eps 1e-9
12 #define inf 0x3f3f3f3f
13 #define ls i << 1
14 #define rs ls | 1
15 #define md ((ll + rr) >> 1)
16 #define lson ll, md, ls
17 #define rson md + 1, rr, rs
18 #define LL long long
19 #define N 150010
20 #define M 200020
21 #define mod 1000000007
22 
23 struct edge{
24     double ux, vx, y, in;
25     edge(double ux = 0, double vx = 0, double y = 0, int in = 0) : ux(ux), vx(vx), y(y), in(in) {}
26     bool operator < (const edge &b) const{
27         return y < b.y;
28     }
29 }e[N];
30 
31 double sum[N<<2], x[N];
32 int vis[N<<2];
33 void build(int ll, int rr, int i){
34     vis[i] = 0, sum[i] = 0;
35     if(ll == rr) return ;
36     build(lson), build(rson);
37 }
38 void push_up(int i, int ll, int rr){
39     if(vis[i]) sum[i] = x[rr+1] - x[ll];
40     else if(ll == rr) sum[i] = 0;
41     else sum[i] = sum[ls] + sum[rs];
42 }
43 void update(int l, int r, int v, int ll, int rr, int i){
44     if(l == ll && r == rr){
45         vis[i] += v;
46         push_up(i, ll, rr);
47         return ;
48     }
49     if(r <= md) update(l, r, v, lson);
50     else if(l > md) update(l, r, v, rson);
51     else update(l, md, v, lson), update(md + 1, r, v, rson);
52     push_up(i, ll, rr);
53 }
54 int main(){
55     int n, kk = 0;
56     while(scanf("%d", &n) != EOF && n){
57         printf("Test case #%d
", ++kk);
58         for(int i = 0; i < n; ++i){
59             double ax, ay, bx, by;
60             scanf("%lf%lf%lf%lf", &ax, &ay, &bx, &by);
61             x[i] = ax, e[i] = edge(ax, bx, ay, 1);
62             x[i+n] = bx, e[i+n] = edge(ax, bx, by, -1);
63         }
64         n <<= 1;
65         sort(x, x + n);
66         sort(e, e + n);
67         int k = 1;
68         for(int i = 1; i < n; ++i)
69             if(x[i] != x[i-1]) x[k++] = x[i];
70         build(0, k, 1);
71         double ans = 0;
72         for(int i = 0; i < n - 1; ++i){
73             int l = lower_bound(x, x + k, e[i].ux) - x;
74             int r = lower_bound(x, x + k, e[i].vx) - x;
75             if(l < r)
76                 update(l, r - 1, e[i].in, 0, k, 1);
77             ans += sum[1] * (e[i+1].y - e[i].y);
78         }
79         printf("Total explored area: %.2lf
", ans);
80         puts("");
81     }
82     return 0;
83 }
View Code

相关推荐