Can you answer these queries

链接：here

Can you answer these queries I

 SPOJ - GSS1 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ls rt<<1
 4 #define rs rt<<1|1
 5 #define lson l, m, ls
 6 #define rson m+1, r, rs
 7 const int maxn = 50010;
 8 
 9 int a[maxn], s[maxn];
10 int pre[maxn<<2], post[maxn<<2], maxv[maxn<<2];
11 
12 void pushup(int l, int r, int rt){
13     int m = (l+r)>>1;
14     pre[rt] = max(pre[ls], s[m]-s[l-1]+pre[rs]);
15     post[rt] = max(post[rs], s[r]-s[m]+post[ls]);
16     maxv[rt] = max(max(maxv[rs], maxv[ls]), pre[rs]+post[ls]);
17 }
18 
19 void build(int l, int r, int rt){
20     if(l==r) {
21         pre[rt] = post[rt] = maxv[rt] = a[l];
22         return ;
23     }
24     int m = (l+r)>>1;
25     build(lson);
26     build(rson);
27     pushup(l, r, rt);
28 }
29 
30 int query(int L, int R, int &ql, int &qr, int l, int r, int rt){
31     if(L<=l && r<=R) {
32         ql = pre[rt];
33         qr = post[rt];
34         return maxv[rt];
35     }
36     int m = (l+r)>>1;
37     if(R<=m) return query(L, R, ql, qr, lson);
38     if(L>m) return query(L, R, ql, qr, rson);
39     int a1, a2, b1, b2;
40     int s1 = query(L, R, a1, b1, lson);
41     int s2 = query(L, R, a2, b2, rson);
42     ql = max(a1, s[m] - s[max(l-1, L-1)] + a2);
43     qr = max(b2, s[min(r, R)] - s[m] + b1);
44     int ans = max(s1, s2);
45     ans = max(ans, b1+a2);
46     return ans;
47 }
48 
49 int main() {
50     int n;
51 //    freopen("in.txt", "r", stdin);
52     while(scanf("%d", &n)!=EOF){
53         for(int i = 1; i <= n; i++) {
54             scanf("%d", &a[i]);
55             s[i] = s[i-1] + a[i];
56         }
57         build(1, n, 1);
58 
59         int t;
60         scanf("%d", &t);
61         while(t--){
62             int a, b;
63             scanf("%d %d", &a, &b);
64             int x,y;
65             printf("%d
", query(a, b, x, y, 1, n, 1));
66         }
67     }
68 }
View Code

下面这个稍慢，不过代码更清晰

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define ls rt<<1
 5 #define rs rt<<1|1
 6 #define lson l, m, ls
 7 #define rson m+1, r, rs
 8 
 9 const int maxn = 50010;
10 int sum[maxn<<2], pre[maxn<<2], post[maxn<<2], maxv[maxn<<2];
11 
12 void pushup(int rt){
13     sum[rt] = sum[ls] + sum[rs];
14     pre[rt] = max(pre[ls], sum[ls] + pre[rs]);
15     post[rt] = max(post[rs], sum[rs] + post[ls]);;
16     maxv[rt] = max(max(maxv[ls], maxv[rs]), post[ls]+pre[rs]);
17 }
18 
19 void build(int l, int r, int rt) {
20     if(l == r) {
21         scanf("%d", &sum[rt]);
22         pre[rt] = post[rt] = maxv[rt] = sum[rt];
23         return;
24     }
25     int m = (l+r)>>1;
26     build(lson);
27     build(rson);
28     pushup(rt);
29 }
30 
31 int query_sum(int L, int R, int l, int r, int rt) {
32     if(L <= l && r <= R) {
33         return sum[rt];
34     }
35     int ans = 0;
36     int m = (l+r) >> 1;
37     if(L <= m) ans += query_sum(L, R, lson);
38     if(R > m) ans += query_sum(L, R, rson);
39     return ans;
40 }
41 int query_pre(int L, int R, int l, int r, int rt) {
42     if(L <= l && r <= R) {
43         return pre[rt];
44     }
45     int m = (l+r)>>1;
46     if(R <= m) return query_pre(L, R, lson);
47     if(L > m) return query_pre(L, R, rson);
48     return max(query_pre(L, R, lson), query_sum(L, R, lson) + query_pre(L, R, rson));
49 }
50 int query_post(int L, int R, int l, int r, int rt) {
51     if(L <= l && r <= R) {
52         return post[rt];
53     }
54     int m = (l+r)>>1;
55     if(R <= m) return query_post(L, R, lson);
56     if(L > m) return query_post(L, R, rson);
57     return max(query_post(L, R, rson), query_sum(L, R, rson) + query_post(L, R, lson));
58 }
59 int query_max(int L, int R, int l, int r, int rt) {
60     if(L <= l && r <= R) {
61         return maxv[rt];
62     }
63     int m = (l+r)>>1;
64     if(R <= m) return query_max(L, R, lson);
65     if(L > m) return query_max(L, R, rson);
66     return max( max(query_max(L, R, lson), query_max(L, R, rson)), query_post(L, R, lson) + query_pre(L, R, rson));
67 }
68 
69 
70 int main(){
71     int n;
72     //freopen("in.txt", "r", stdin);
73     while(scanf("%d", &n) != EOF) {
74         build(1, n, 1);
75         int m;
76         scanf("%d", &m);
77         int L, R;
78         while(m--) {
79             scanf("%d %d", &L, &R);
80             printf("%d
", query_max(L, R, 1, n, 1));
81         }
82     }
83 }
View Code

Can you answer these queries III

 SPOJ - GSS3 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ls rt<<1
 4 #define rs rt<<1|1
 5 #define lson l, m, ls
 6 #define rson m+1, r, rs
 7 const int maxn = 50010;
 8 
 9 int a[maxn];
10 int pre[maxn<<2], post[maxn<<2], sum[maxn<<2], maxv[maxn<<2];
11 
12 void pushup(int l, int r, int rt) {
13     int m = (l+r)>>1;
14     sum[rt] = sum[ls] + sum[rs];
15     pre[rt] = max(pre[ls], sum[ls]+pre[rs]);
16     post[rt] = max(post[rs], sum[rs]+post[ls]);
17     maxv[rt] = max(max(maxv[rs], maxv[ls]), pre[rs]+post[ls]);
18 }
19 
20 void build(int l, int r, int rt){
21     if(l==r) {
22         pre[rt] = post[rt] = sum[rt] = maxv[rt] = a[l];
23         return ;
24     }
25     int m = (l+r)>>1;
26     build(lson);
27     build(rson);
28     pushup(l, r, rt);
29 }
30 
31 int query(int L, int R, int &ql, int &qr, int l, int r, int rt){
32     if(L<=l && r<=R) {
33         ql = pre[rt];
34         qr = post[rt];
35         return maxv[rt];
36     }
37     int m = (l+r)>>1;
38     if(R<=m) return query(L, R, ql, qr, lson);
39     if(L>m) return query(L, R, ql, qr, rson);
40     int a1, a2, b1, b2;
41     int s1 = query(L, R, a1, b1, lson);
42     int s2 = query(L, R, a2, b2, rson);
43     ql = max(a1, sum[ls] + a2);
44     qr = max(b2, sum[rs] + b1);
45     int ans = max(s1, s2);
46     ans = max(ans, b1+a2);
47     return ans;
48 }
49 void update(int pos, int val, int l, int r, int rt) {
50     if(l == r) {
51         sum[rt] = pre[rt] = post[rt] = maxv[rt] = val;
52         return;
53     }
54     int m = (l+r)>>1;
55     if(pos<=m) update(pos, val, lson);
56     else update(pos, val, rson);
57     pushup(l, r, rt);
58 }
59 
60 int main() {
61     int n;
62 //  freopen("in.txt", "r", stdin);
63     while(scanf("%d", &n)!=EOF){
64         for(int i = 1; i <= n; i++) {
65             scanf("%d", &a[i]);
66         }
67         build(1, n, 1);
68         int t;
69         scanf("%d", &t);
70         while(t--){
71             int a, b;
72             int op;
73             scanf("%d", &op);
74             scanf("%d %d", &a, &b);
75             int x,y;
76             if(op == 1){
77                 printf("%d
", query(a, b, x, y, 1, n, 1));
78             } else {
79                 update(a, b, 1, n, 1);
80             }
81         }
82     }
83     return 0;
84 }
View Code

Can you answer these queries IV

 SPOJ - GSS4 

题目没有说Ｌ一定小于Ｒ，　神坑．．．

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long 
 4 #define ls rt<<1
 5 #define rs rt<<1|1
 6 #define lson l, m, ls
 7 #define rson m+1, r, rs
 8 const int maxn = 100010;
 9 
10 ll sum[maxn<<2];
11 
12 void pushup(int rt) {
13     sum[rt] = sum[ls] + sum[rs];
14 }
15 
16 void build(int l, int r, int rt) {
17     if(l == r) {
18         scanf("%lld", &sum[rt]);
19         return;
20     }
21     int m = (l+r)>>1;
22     build(lson);
23     build(rson);
24     pushup(rt);
25 }
26 
27 void update(int L, int R, int l, int r, int rt) {
28     if(r-l+1 == sum[rt]) return;
29     if(l == r) {
30         sum[rt] = sqrt(sum[rt]);
31         return;
32     }
33     int m = (l+r)>>1;
34     if(L<=m) update(L, R, lson);
35     if(R>m) update(L, R, rson);
36     pushup(rt);
37 }
38 ll query(int L, int R, int l, int r, int rt) {
39     if(L<=l && r<=R) return sum[rt];
40     int m = (l+r)>>1;
41     ll ans = 0;
42     if(L <= m) ans+=query(L, R, lson);
43     if(R > m) ans+=query(L, R, rson);
44     return ans;
45 }
46 
47 int main(){
48     int n;
49     int kase = 0 ;
50    // freopen("in.txt", "r", stdin);
51     while(scanf("%d", &n)!=EOF) {
52         build(1, n, 1);
53         int L, R, op;
54         int m;
55         scanf("%d", &m);
56         printf("Case #%d:
", ++kase);
57         while(m--) {
58             scanf("%d %d %d", &op, &L, &R);
59             if(L > R) swap(L,R);
60             if(op) {
61                 printf("%lld
", query(L, R, 1, n, 1));
62             } else {
63                 update(L, R, 1, n, 1);
64             }
65         }
66         puts("");
67     }
68     return 0;
69 }
View Code

Can you answer these queries V

 SPOJ - GSS5 

终于过了...

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define ls rt<<1
 5 #define rs rt<<1|1
 6 #define lson l, m, ls
 7 #define rson m+1, r, rs
 8 
 9 const int maxn = 10010;
10 int sum[maxn<<2], pre[maxn<<2], post[maxn<<2], maxv[maxn<<2];
11 
12 void pushup(int rt){
13     sum[rt] = sum[ls] + sum[rs];
14     pre[rt] = max(pre[ls], sum[ls] + pre[rs]);
15     post[rt] = max(post[rs], sum[rs] + post[ls]);;
16     maxv[rt] = max(max(maxv[ls], maxv[rs]), post[ls]+pre[rs]);
17 }
18 
19 void build(int l, int r, int rt) {
20     if(l == r) {
21         scanf("%d", &sum[rt]);
22         pre[rt] = post[rt] = maxv[rt] = sum[rt];
23         return;
24     }
25     int m = (l+r)>>1;
26     build(lson);
27     build(rson);
28     pushup(rt);
29 }
30 
31 int query_sum(int L, int R, int l, int r, int rt) {
32     if(L > R) return 0;
33     if(L <= l && r <= R) {
34         return sum[rt];
35     }
36     int ans = 0;
37     int m = (l+r) >> 1;
38     if(L <= m) ans += query_sum(L, R, lson);
39     if(R > m) ans += query_sum(L, R, rson);
40     return ans;
41 }
42 int query_pre(int L, int R, int l, int r, int rt) {
43     if(L > R) return 0;
44     if(L <= l && r <= R) {
45         return pre[rt];
46     }
47     int m = (l+r)>>1;
48     if(R <= m) return query_pre(L, R, lson);
49     if(L > m) return query_pre(L, R, rson);
50     return max(query_pre(L, R, lson), query_sum(L, R, lson) + query_pre(L, R, rson));
51 }
52 int query_post(int L, int R, int l, int r, int rt) {
53     if(L > R) return 0;
54     if(L <= l && r <= R) {
55         return post[rt];
56     }
57     int m = (l+r)>>1;
58     if(R <= m) return query_post(L, R, lson);
59     if(L > m) return query_post(L, R, rson);
60     return max(query_post(L, R, rson), query_sum(L, R, rson) + query_post(L, R, lson));
61 }
62 int query_max(int L, int R, int l, int r, int rt) {
63     if(L > R) return 0;
64     if(L <= l && r <= R) {
65         return maxv[rt];
66     }
67     int m = (l+r)>>1;
68     if(R <= m) return query_max(L, R, lson);
69     if(L > m) return query_max(L, R, rson);
70     return max( max(query_max(L, R, lson), query_max(L, R, rson)), query_post(L, R, lson) + query_pre(L, R, rson));
71 }
72 
73 
74 int main(){
75     int n, t;
76    // freopen("in.txt", "r", stdin);
77     scanf("%d", &t);
78     while(t--) {
79         scanf("%d", &n);
80         build(1, n, 1);
81         int m;
82         scanf("%d", &m);
83         int x1, y1, x2, y2;
84         while(m--) {
85             scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
86             int ans = 0;
87             if(y1 < x2) {
88                 ans = query_post(x1, y1, 1, n, 1) + query_sum(y1+1, x2-1, 1, n, 1) + query_pre(x2, y2, 1, n, 1);
89             } else if(y1==y2) {
90                 ans = max(query_max(x2, y2, 1, n, 1), query_post(x1, x2-1, 1, n, 1) + query_pre(x2, y2, 1, n, 1));
91             } else if(x2 <= y1) {
92                 ans = max( max(query_max(x2, y1, 1, n, 1), query_post(x1, x2-1, 1, n, 1) + query_sum(x2, y1, 1, n, 1) + query_pre(y1+1, y2, 1, n, 1)),
93                         max(query_post(x1, x2-1, 1, n, 1) + query_pre(x2, y1, 1, n, 1), query_post(x2, y1, 1, n, 1) + query_pre(y1+1, y2, 1, n, 1)) );
94             }
95             printf("%d
", ans);
96         }
97     }
98     return 0;
99 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yijiull/p/7629349.html