FZU2013 A short problem —— 线段树/树状数组 + 前缀和

题目链接：https://vjudge.net/problem/FZU-2013

Problem 2013 A short problem

Accept: 356 Submit: 1083
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

The description of this problem is very short. Now give you a string(length N), and ask you the max sum of the substring which the length can't small than M.

Input

The first line is one integer T(T≤20) indicates the number of the test cases. Then for every case, the first line is two integer N(1≤N≤1000000) and M(1≤M≤N).

Then one line contains N integer indicate the number. All the number is between -10000 and 10000.

Output

Output one line with an integer.

Sample Input

2 5 1 1 -2 -2 -2 1 5 2 1 -2 -2 -2 1

Sample Output

1 -1

Source

FOJ有奖月赛-2011年03月

题意：

给出一个序列，求长度不小于m且和最大的子序列。

题解：

1.求出前缀和。

2.将0插入到线段树第0位，然后从第m为开始枚举：去线段树范围为0~i-m的地方找最小值，然后以i为结尾的子序列最大值即为：sum[i] - query(1,0,n,0,i-m)。答案即为max（sum[i] - query(1,0,n,0,i-m)）。

3.类似的题目：CSU - 1551 Longest Increasing Subsequence Again

线段树：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXN = 1e6;
18 
19 int minv[MAXN*4];
20 void add(int u, int l, int r, int x, int val)
21 {
22     if(l==r)
23     {
24         minv[u] = val;
25         return;
26     }
27     int mid = (l+r)/2;
28     if(x<=mid) add(u*2, l, mid, x, val);
29     else add(u*2+1, mid+1,r, x, val);
30     minv[u] = min(minv[u*2], minv[u*2+1]);
31 }
32 
33 int query(int u, int l, int r, int x, int y)
34 {
35     if(l<=x&&y<=r)
36         return minv[u];
37 
38     int mid = (l+r)/2;
39     int ret = INF;
40     if(x<=mid) ret = min(ret, query(u*2, l, mid, x, mid));
41     if(y>=mid+1) ret = min(ret, query(u*2+1, mid+1, r, mid+1, y));
42     return ret;
43 }
44 
45 int sum[MAXN];
46 int main()
47 {
48     int T, n, m;
49     scanf("%d", &T);
50     while(T--)
51     {
52         scanf("%d%d", &n,&m);
53         sum[0] = 0;
54         for(int i = 1; i<=n; i++)
55         {
56             int val;
57             scanf("%d", &val);
58             sum[i] = sum[i-1]+val;
59         }
60 
61         for(int i = 0; i<=n*4; i++)
62             minv[i] = INF;
63 
64         int ans = -INF;
65         add(1,0,n,0,0);
66         for(int i = m; i<=n; i++)
67         {
68             ans = max(ans, sum[i]-query(1,0,n,0,i-m));
69             add(1,0,n,i-m+1,sum[i-m+1]);
70         }
71         printf("%d
", ans);
72     }
73 }

View Code

树状数组：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXN = 1e6;
18 
19 int T, n, m;
20 int lowbit(int x)
21 {
22     return x&(-x);
23 }
24 
25 int c[MAXN];
26 void add(int x, int d)
27 {
28     while(x<=n)
29     {
30         c[x] = min(c[x], d);
31         x += lowbit(x);
32     }
33 }
34 
35 int query(int x)
36 {
37     int s = INF;
38     while(x>0)
39     {
40         s = min(c[x], s);
41         x -= lowbit(x);
42     }
43     return s;
44 }
45 
46 int sum[MAXN];
47 int main()
48 {
49     scanf("%d", &T);
50     while(T--)
51     {
52         memset(c, 0, sizeof(c));
53         scanf("%d%d", &n,&m);
54         sum[0] = 0;
55         for(int i = 1; i<=n; i++)
56         {
57             int val;
58             scanf("%d", &val);
59             sum[i] = sum[i-1]+val;
60         }
61         for(int i = 1; i<=n+1; i++)
62             c[i] = INF;
63 
64         int ans = -INF;
65         add(1, 0);
66         for(int i = m; i<=n; i++)
67         {
68             ans = max(ans, sum[i]-query(i-m+1));
69             add(i-m+2, sum[i-m+1]);
70         }
71         printf("%d
", ans);
72     }
73 }

View Code