hihocoder1710 等差子数列

思路：
将数列合并之后使用线段树。边界条件容易写错。
实现：
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 100005;
 4 const int INF = 0x3f3f3f3f;
 5 
 6 int a[MAXN], tree[MAXN * 4], n, m, sum[MAXN];
 7 vector<int> v(1, 0);
 8 
 9 void build(int num, int l, int r)
10 {
11     if (l == r) { tree[num] = v[l]; return; }
12     int m = l + r >> 1;
13     build(num * 2, l, m);
14     build(num * 2 + 1, m + 1, r);
15     tree[num] = max(tree[num * 2], tree[num * 2 + 1]);
16 }
17 
18 int query(int num, int l, int r, int x, int y)
19 {
20     if (x <= l && y >= r) return tree[num];
21     int ans = -INF, m = l + r >> 1;
22     if (x <= m) ans = max(ans, query(num * 2, l, m, x, y));
23     if (y >= m + 1) ans = max(ans, query(num * 2 + 1, m + 1, r, x, y));
24     return ans;
25 }
26 
27 int main()
28 {
29     scanf("%d %d", &n, &m);
30     for (int i = 0; i < n; i++) scanf("%d", &a[i]);
31     a[n] = INF;
32     int cnt = 2;
33     for (int i = 1; i < n; i++)
34     {
35         if (a[i] - a[i - 1] != a[i + 1] - a[i]) { v.push_back(cnt - 1); cnt = 2; }
36         else cnt++;
37     }
38     int tot = v.size() - 1;
39     build(1, 1, tot);
40     for (int i = 1; i <= tot; i++) sum[i] = sum[i - 1] + v[i];
41     int l, r;
42     for (int i = 0; i < m; i++)
43     {
44         scanf("%d %d", &l, &r);
45         if (n == 1) { puts("1"); continue; }
46         int ls = lower_bound(sum + 1, sum + tot + 1, l == n ? l - 1 : l) - sum;
47         int rs = lower_bound(sum + 1, sum + tot + 1, r == n ? r - 1 : r) - sum;
48         int ans = -1;
49         if (ls == rs) ans = r - l + 1;
50         else
51         {   
52             ans = max(sum[ls] - l + 2, r - sum[rs - 1]);
53             if (rs - ls > 1) ans = max(ans, query(1, 1, tot, ls + 1, rs - 1) + 1);
54         }
55         printf("%d
", ans);
56     }
57     return 0;
58 }