线段树

线段树功能:update:单点增减 query:区间求和 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 55555;
int sum[maxn<<2];
void PushUP(int rt) {
       sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt) {
       if (l == r) {
              scanf("%d",&sum[rt]);
              return ;
       }
       int m = (l + r) >> 1;
       build(lson);
       build(rson);
       PushUP(rt);
}
void update(int p,int add,int l,int r,int rt) {
       if (l == r) {
              sum[rt] += add;
              return ;
       }
       int m = (l + r) >> 1;
       if (p <= m) update(p , add , lson);
       else update(p , add , rson);
       PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
       if (L <= l && r <= R) {
              return sum[rt];
       }
       int m = (l + r) >> 1;
       int ret = 0;
       if (L <= m) ret += query(L , R , lson);
       if (R > m) ret += query(L , R , rson);
       return ret;
}
int main() {
       int T , n;
       scanf("%d",&T);
       for (int cas = 1 ; cas <= T ; cas ++) {
              printf("Case %d:\n",cas);
              scanf("%d",&n);
              build(1 , n , 1);
              char op[10];
              while (scanf("%s",op)) {
                     if (op[0] == 'E') break;
                     int a , b;
                     scanf("%d%d",&a,&b);
                     if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));
                     else if (op[0] == 'S') update(a , -b , 1 , n , 1);
                     else update(a , b , 1 , n , 1);
              }
       }
       return 0;
}
线段树功能:update:单点替换 query:区间最值 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <algorithm>
using namespace std;

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 222222;
int MAX[maxn<<2];
void PushUP(int rt) {
       MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l,int r,int rt) {
       if (l == r) {
              scanf("%d",&MAX[rt]);
              return ;
       }
       int m = (l + r) >> 1;
       build(lson);
       build(rson);
       PushUP(rt);
}
void update(int p,int sc,int l,int r,int rt) {
       if (l == r) {
              MAX[rt] = sc;
              return ;
       }
       int m = (l + r) >> 1;
       if (p <= m) update(p , sc , lson);
       else update(p , sc , rson);
       PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
       if (L <= l && r <= R) {
              return MAX[rt];
       }
       int m = (l + r) >> 1;
       int ret = 0;
       if (L <= m) ret = max(ret , query(L , R , lson));
       if (R > m) ret = max(ret , query(L , R , rson));
       return ret;
}
int main() {
       int n , m;
       while (~scanf("%d%d",&n,&m)) {
              build(1 , n , 1);
              while (m --) {
                     char op[2];
                     int a , b;
                     scanf("%s%d%d",op,&a,&b);
                     if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));
                     else update(a , b , 1 , n , 1);
              }
       }
       return 0;
}
线段树功能:update:单点增减 query:区间求和 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <algorithm>
using namespace std;

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 5555;
int sum[maxn<<2];
void PushUP(int rt) {
       sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt) {
       sum[rt] = 0;
       if (l == r) return ;
       int m = (l + r) >> 1;
       build(lson);
       build(rson);
}
void update(int p,int l,int r,int rt) {
       if (l == r) {
              sum[rt] ++;
              return ;
       }
       int m = (l + r) >> 1;
       if (p <= m) update(p , lson);
       else update(p , rson);
       PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
       if (L <= l && r <= R) {
              return sum[rt];
       }
       int m = (l + r) >> 1;
       int ret = 0;
       if (L <= m) ret += query(L , R , lson);
       if (R > m) ret += query(L , R , rson);
       return ret;
}
int x[maxn];
int main() {
       int n;
       while (~scanf("%d",&n)) {
              build(0 , n - 1 , 1);
              int sum = 0;
              for (int i = 0 ; i < n ; i ++) {
                     scanf("%d",&x[i]);
                     sum += query(x[i] , n - 1 , 0 , n - 1 , 1);
                     update(x[i] , 0 , n - 1 , 1);
              }
              int ret = sum;
              for (int i = 0 ; i < n ; i ++) {
                     sum += n - x[i] - x[i] - 1;
                     ret = min(ret , sum);
              }
              printf("%d\n",ret);
       }
       return 0;
}
线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <algorithm>
using namespace std;

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 222222;
int h , w , n;
int MAX[maxn<<2];
void PushUP(int rt) {
       MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l,int r,int rt) {
       MAX[rt] = w;
       if (l == r) return ;
       int m = (l + r) >> 1;
       build(lson);
       build(rson);
}
int query(int x,int l,int r,int rt) {
       if (l == r) {
              MAX[rt] -= x;
              return l;
       }
       int m = (l + r) >> 1;
       int ret = (MAX[rt<<1] >= x) ? query(x , lson) : query(x , rson);
       PushUP(rt);
       return ret;
}
int main() {
       while (~scanf("%d%d%d",&h,&w,&n)) {
              if (h > n) h = n;
              build(1 , h , 1);
              while (n --) {
                     int x;
                     scanf("%d",&x);
                     if (MAX[1] < x) puts("-1");
                     else printf("%d\n",query(x , 1 , h , 1));
              }
       }
       return 0;
}
线段树功能:update:成段替换 (由于只query一次总区间,所以可以直接输出1结点的信息) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <algorithm>
using namespace std;

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 111111;
int h , w , n;
int col[maxn<<2];
int sum[maxn<<2];
void PushUp(int rt) {
       sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void PushDown(int rt,int m) {
       if (col[rt]) {
              col[rt<<1] = col[rt<<1|1] = col[rt];
              sum[rt<<1] = (m - (m >> 1)) * col[rt];
              sum[rt<<1|1] = (m >> 1) * col[rt];
              col[rt] = 0;
       }
}
void build(int l,int r,int rt) {
       col[rt] = 0;
       sum[rt] = 1;
       if (l == r) return ;
       int m = (l + r) >> 1;
       build(lson);
       build(rson);
       PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt) {
       if (L <= l && r <= R) {
              col[rt] = c;
              sum[rt] = c * (r - l + 1);
              return ;
       }
       PushDown(rt , r - l + 1);
       int m = (l + r) >> 1;
       if (L <= m) update(L , R , c , lson);
       if (R > m) update(L , R , c , rson);
       PushUp(rt);
}
int main() {
       int T , n , m;
       scanf("%d",&T);
       for (int cas = 1 ; cas <= T ; cas ++) {
              scanf("%d%d",&n,&m);
              build(1 , n , 1);
              while (m --) {
                     int a , b , c;
                     scanf("%d%d%d",&a,&b,&c);
                     update(a , b , c , 1 , n , 1);
              }
              printf("Case %d: The total value of the hook is %d.\n",cas , sum[1]);
       }
       return 0;
}
线段树功能:update:成段增减 query:区间求和 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <algorithm>
using namespace std;

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define LL long long
const int maxn = 111111;
LL add[maxn<<2];
LL sum[maxn<<2];
void PushUp(int rt) {
       sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void PushDown(int rt,int m) {
       if (add[rt]) {
              add[rt<<1] += add[rt];
              add[rt<<1|1] += add[rt];
              sum[rt<<1] += add[rt] * (m - (m >> 1));
              sum[rt<<1|1] += add[rt] * (m >> 1);
              add[rt] = 0;
       }
}
void build(int l,int r,int rt) {
       add[rt] = 0;
       if (l == r) {
              scanf("%lld",&sum[rt]);
              return ;
       }
       int m = (l + r) >> 1;
       build(lson);
       build(rson);
       PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt) {
       if (L <= l && r <= R) {
              add[rt] += c;
              sum[rt] += (LL)c * (r - l + 1);
              return ;
       }
       PushDown(rt , r - l + 1);
       int m = (l + r) >> 1;
       if (L <= m) update(L , R , c , lson);
       if (m < R) update(L , R , c , rson);
       PushUp(rt);
}
LL query(int L,int R,int l,int r,int rt) {
       if (L <= l && r <= R) {
              return sum[rt];
       }
       PushDown(rt , r - l + 1);
       int m = (l + r) >> 1;
       LL ret = 0;
       if (L <= m) ret += query(L , R , lson);
       if (m < R) ret += query(L , R , rson);
       return ret;
}
int main() {
       int N , Q;
       scanf("%d%d",&N,&Q);
       build(1 , N , 1);
       while (Q --) {
              char op[2];
              int a , b , c;
              scanf("%s",op);
              if (op[0] == 'Q') {
                     scanf("%d%d",&a,&b);
                     printf("%lld\n",query(a , b , 1 , N , 1));
              } else {
                     scanf("%d%d%d",&a,&b,&c);
                     update(a , b , c , 1 , N , 1);
              }
       }
       return 0;
}
线段树功能:update:成段替换 query:简单hash 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

const int maxn = 11111;
bool hash[maxn];
int li[maxn] , ri[maxn];
int X[maxn*3];
int col[maxn<<4];
int cnt;

void PushDown(int rt) {
       if (col[rt] != -1) {
              col[rt<<1] = col[rt<<1|1] = col[rt];
              col[rt] = -1;
       }
}
void update(int L,int R,int c,int l,int r,int rt) {
       if (L <= l && r <= R) {
              col[rt] = c;
              return ;
       }
       PushDown(rt);
       int m = (l + r) >> 1;
       if (L <= m) update(L , R , c , lson);
       if (m < R) update(L , R , c , rson);
}
void query(int l,int r,int rt) {
       if (col[rt] != -1) {
              if (!hash[col[rt]]) cnt ++;
              hash[ col[rt] ] = true;
              return ;
       }
       if (l == r) return ;
       int m = (l + r) >> 1;
       query(lson);
       query(rson);
}
int Bin(int key,int n,int X[]) {
       int l = 0 , r = n - 1;
       while (l <= r) {
              int m = (l + r) >> 1;
              if (X[m] == key) return m;
              if (X[m] < key) l = m + 1;
              else r = m - 1;
       }
       return -1;
}
int main() {
       int T , n;
       scanf("%d",&T);
       while (T --) {
              scanf("%d",&n);
              int nn = 0;
              for (int i = 0 ; i < n ; i ++) {
                     scanf("%d%d",&li[i] , &ri[i]);
                     X[nn++] = li[i];
                     X[nn++] = ri[i];
              }
              sort(X , X + nn);
              int m = 1;
              for (int i = 1 ; i < nn; i ++) {
                     if (X[i] != X[i-1]) X[m ++] = X[i];
              }
              for (int i = m - 1 ; i > 0 ; i --) {
                     if (X[i] != X[i-1] + 1) X[m ++] = X[i] + 1;
              }
              sort(X , X + m);
              memset(col , -1 , sizeof(col));
              for (int i = 0 ; i < n ; i ++) {
                     int l = Bin(li[i] , m , X);
                     int r = Bin(ri[i] , m , X);
                     update(l , r , i , 0 , m , 1);
              }
              cnt = 0;
              memset(hash , false , sizeof(hash));
              query(0 , m , 1);
              printf("%d\n",cnt);
       }
       return 0;
}
线段树功能:update:成段替换,区间异或 query:简单hash 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

const int maxn = 131072;
bool hash[maxn];
int cover[maxn<<2];
int XOR[maxn<<2];
void FXOR(int rt) {
       if (cover[rt] != -1) cover[rt] ^= 1;
       else XOR[rt] ^= 1;
}
void PushDown(int rt) {
       if (cover[rt] != -1) {
              cover[rt<<1] = cover[rt<<1|1] = cover[rt];
              XOR[rt<<1] = XOR[rt<<1|1] = 0;
              cover[rt] = -1;
       }
       if (XOR[rt]) {
              FXOR(rt<<1);
              FXOR(rt<<1|1);
              XOR[rt] = 0;
       }
}
void update(char op,int L,int R,int l,int r,int rt) {
       if (L <= l && r <= R) {
              if (op == 'U') {
                     cover[rt] = 1;
                     XOR[rt] = 0;
              } else if (op == 'D') {
                     cover[rt] = 0;
                     XOR[rt] = 0;
              } else if (op == 'C' || op == 'S') {
                     FXOR(rt);
              }
              return ;
       }
       PushDown(rt);
       int m = (l + r) >> 1;
       if (L <= m) update(op , L , R , lson);
       else if (op == 'I' || op == 'C') {
              XOR[rt<<1] = cover[rt<<1] = 0;
       }
       if (m < R) update(op , L , R , rson);
       else if (op == 'I' || op == 'C') {
              XOR[rt<<1|1] = cover[rt<<1|1] = 0;
       }
}
void query(int l,int r,int rt) {
       if (cover[rt] == 1) {
              for (int it = l ; it <= r ; it ++) {
                     hash[it] = true;
              }
              return ;
       } else if (cover[rt] == 0) return ;
       if (l == r) return ;
       PushDown(rt);
       int m = (l + r) >> 1;
       query(lson);
       query(rson);
}
int main() {
       cover[1] = XOR[1] = 0;
       char op , l , r;
       int a , b;
       while ( ~scanf("%c %c%d,%d%c\n",&op , &l , &a , &b , &r) ) {
              a <<= 1 , b <<= 1;
              if (l == '(') a ++;
              if (r == ')') b --;
              if (a > b) {
                     if (op == 'C' || op == 'I') {
                            cover[1] = XOR[1] = 0;
                     }
              } else update(op , a , b , 0 , maxn , 1);
       }
       query(0 , maxn , 1);
       bool flag = false;
       int s = -1 , e;
       for (int i = 0 ; i <= maxn ; i ++) {
              if (hash[i]) {
                     if (s == -1) s = i;
                     e = i;
              } else {
                     if (s != -1) {
                            if (flag) printf(" ");
                            flag = true;
                            printf("%c%d,%d%c",s&1?'(':'[' , s>>1 , (e+1)>>1 , e&1?')':']');
                            s = -1;
                     }
              }
       }
       if (!flag) printf("empty set");
       puts("");
       return 0;
}
线段树操作:update:区间替换 query:询问满足条件的最左断点 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

const int maxn = 55555;
int lsum[maxn<<2] , rsum[maxn<<2] , msum[maxn<<2];
int cover[maxn<<2];

void PushDown(int rt,int m) {
       if (cover[rt] != -1) {
              cover[rt<<1] = cover[rt<<1|1] = cover[rt];
              msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : m - (m >> 1);
              msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : (m >> 1);
              cover[rt] = -1;
       }
}
void PushUp(int rt,int m) {
       lsum[rt] = lsum[rt<<1];
       rsum[rt] = rsum[rt<<1|1];
       if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1];
       if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1];
       msum[rt] = max(lsum[rt<<1|1] + rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1]));
}
void build(int l,int r,int rt) {
       msum[rt] = lsum[rt] = rsum[rt] = r - l + 1;
       cover[rt] = -1;
       if (l == r) return ;
       int m = (l + r) >> 1;
       build(lson);
       build(rson);
}
void update(int L,int R,int c,int l,int r,int rt) {
       if (L <= l && r <= R) {
              msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : r - l + 1;
              cover[rt] = c;
              return ;
       }
       PushDown(rt , r - l + 1);
       int m = (l + r) >> 1;
       if (L <= m) update(L , R , c , lson);
       if (m < R) update(L , R , c , rson);
       PushUp(rt , r - l + 1);
}
int query(int w,int l,int r,int rt) {
       if (l == r) return l;
       PushDown(rt , r - l + 1);
       int m = (l + r) >> 1;
       if (msum[rt<<1] >= w) return query(w , lson);
       else if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return m - rsum[rt<<1] + 1;
       return query(w , rson);
}
int main() {
       int n , m;
       scanf("%d%d",&n,&m);
       build(1 , n , 1);
       while (m --) {
              int op , a , b;
              scanf("%d",&op);
              if (op == 1) {
                     scanf("%d",&a);
                     if (msum[1] < a) puts("0");
                     else {
                            int p = query(a , 1 , n , 1);
                            printf("%d\n",p);
                            update(p , p + a - 1 , 1 , 1 , n , 1);
                     }
              } else {
                     scanf("%d%d",&a,&b);
                     update(a , a + b - 1 , 0 , 1 , n , 1);
              }
       }
       return 0;
}
线段树操作:update:区间增减 query:直接取根节点的值 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

const int maxn = 2222;
int cnt[maxn << 2];
double sum[maxn << 2];
double X[maxn];
struct Seg {
       double h , l , r;
       int s;
       Seg(){}
       Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {}
       bool operator < (const Seg &cmp) const {
              return h < cmp.h;
       }
}ss[maxn];
void PushUp(int rt,int l,int r) {
       if (cnt[rt]) sum[rt] = X[r+1] - X[l];
       else if (l == r) sum[rt] = 0;
       else sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void update(int L,int R,int c,int l,int r,int rt) {
       if (L <= l && r <= R) {
              cnt[rt] += c;
              PushUp(rt , l , r);
              return ;
       }
       int m = (l + r) >> 1;
       if (L <= m) update(L , R , c , lson);
       if (m < R) update(L , R , c , rson);
       PushUp(rt , l , r);
}
int Bin(double key,int n,double X[]) {
       int l = 0 , r = n - 1;
       while (l <= r) {
              int m = (l + r) >> 1;
              if (X[m] == key) return m;
              if (X[m] < key) l = m + 1;
              else r = m - 1;
       }
       return -1;
}
int main() {
       int n , cas = 1;
       while (~scanf("%d",&n) && n) {
              int m = 0;
              while (n --) {
                     double a , b , c , d;
                     scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
                     X[m] = a;
                     ss[m++] = Seg(a , c , b , 1);
                     X[m] = c;
                     ss[m++] = Seg(a , c , d , -1);
              }
              sort(X , X + m);
              sort(ss , ss + m);
              int k = 1;
              for (int i = 1 ; i < m ; i ++) {
                     if (X[i] != X[i-1]) X[k++] = X[i];
              }
              memset(cnt , 0 , sizeof(cnt));
              memset(sum , 0 , sizeof(sum));
              double ret = 0;
              for (int i = 0 ; i < m - 1 ; i ++) {
                     int l = Bin(ss[i].l , k , X);
                     int r = Bin(ss[i].r , k , X) - 1;
                     if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1);
                     ret += sum[1] * (ss[i+1].h - ss[i].h);
              }
              printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++ , ret);
       }
       return 0;
}
线段树操作:update:区间增减 query:直接取根节点的值 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1

const int maxn = 22222;
struct Seg{
       int l , r , h , s;
       Seg() {}
       Seg(int a,int b,int c,int d):l(a) , r(b) , h(c) , s(d) {}
       bool operator < (const Seg &cmp) const {
              return h < cmp.h;
       }
}ss[maxn];
bool lbd[maxn<<2] , rbd[maxn<<2];
int numseg[maxn<<2];
int cnt[maxn<<2];
int len[maxn<<2];
void PushUP(int rt,int l,int r) {
       if (cnt[rt]) {
              lbd[rt] = rbd[rt] = 1;
              len[rt] = r - l + 1;
              numseg[rt] = 2;
       } else if (l == r) {
              len[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;
       } else {
              lbd[rt] = lbd[rt<<1];
              rbd[rt] = rbd[rt<<1|1];
              len[rt] = len[rt<<1] + len[rt<<1|1];
              numseg[rt] = numseg[rt<<1] + numseg[rt<<1|1];
              if (lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt] -= 2;//两条线重合
       }
}
void update(int L,int R,int c,int l,int r,int rt) {
       if (L <= l && r <= R) {
              cnt[rt] += c;
              PushUP(rt , l , r);
              return ;
       }
       int m = (l + r) >> 1;
       if (L <= m) update(L , R , c , lson);
       if (m < R) update(L , R , c , rson);
       PushUP(rt , l , r);
}
int main() {
       int n;
       while (~scanf("%d",&n)) {
              int m = 0;
              int lbd = 10000, rbd = -10000;
              for (int i = 0 ; i < n ; i ++) {
                     int a , b , c , d;
                     scanf("%d%d%d%d",&a,&b,&c,&d);
                     lbd = min(lbd , a);
                     rbd = max(rbd , c);
                     ss[m++] = Seg(a , c , b , 1);
                     ss[m++] = Seg(a , c , d , -1);
              }
              sort(ss , ss + m);
              int ret = 0 , last = 0;
              for (int i = 0 ; i < m ; i ++) {
                     if (ss[i].l < ss[i].r) update(ss[i].l , ss[i].r - 1 , ss[i].s , lbd , rbd - 1 , 1);
                     ret += numseg[1] * (ss[i+1].h - ss[i].h);
                     ret += abs(len[1] - last);
                     last = len[1];
              }
              printf("%d\n",ret);
       }
       return 0;
}