启发式分治

启发式分治

例题 CF1156E

求$a[l]+a[r]=max \sum_{i=l}^r a[i]$的区间个数。每个$a[i]$不同。

考虑朴素做法,找出每个$a[i]$所控制的区间$[L[i],R[i]]$。

$l\in[L[i],i),r\in(i,R[i]]$ 枚举一端判断另一端是否存在即可。
选择在小的那个区间中枚举一个端点,在另外那个区间中查有没有对应的值。

这样子看上去是 $𝑂(𝑛^2)$ 的,实际上是 $𝑂(𝑛log𝑛)$ 的。

它的本质是在笛卡尔树上启发式分裂(代更新)。

一种分治的做法

处理$[l,r]$,处理$max(a[i])的i\in[l,mid]$,$a[L]+a[R]=a[i]$双指针去移动$L,R$。反之但是用$Set$维护即可。复杂度$O(n\log^2 n)$


例题 HDU6701

$max \sum_{i=l}^r a[i]- (r-l+1)<=k$且元素不重复的区间个数。

同样做法找出每个$a[i]$所控制的区间$[L[i],R[i]]$。

选择在小的那个区间中枚举一个端点,$a[i]-k<=(r-l+1)$

假设枚举$l\in[L[i],i]$,则最少到达就是$L=max(i,l+a[i]-k-1)$,并且预处理不重复元素每个元素的边界$[Lc[i],Rc[i]]$,此时最远到达就是$Rc[i]$,$ans=ans+min(Rc[i]-R+1)$

  • $r\in [i,R[i]]$也一样。
  • 注意由于元素相同,处理最大值的时候控制$L[i]$最远,$R[i]$最近,不然会出现重复计数。
CF1156E
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
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#include <set>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0', c = getchar();
return x * f;
}

int L[N], R[N];
int a[N], pos[N];
set<int> s;
int ans;
void solve(int l, int r)
{
if (l == r)
return;

int mid = (l + r) >> 1; // max in [mid+1,R]
s.clear();
int L = mid + 1, R = mid + 1;
int mx = 0;
while (R <= r)
{
mx = max(mx, a[R]);
while (L - 1 >= l && a[L - 1] < mx)
s.insert(a[--L]);
if (s.count(mx - a[R]))
ans++;
R++;
}
s.clear();
L = mid, R = mid;
mx = 0;
while (L >= l)
{
mx = max(mx, a[L]);
while (R + 1 <= r && a[R + 1] < mx)
s.insert(a[++R]);
if (s.count(mx - a[L]))
ans++;
L--;
}
solve(l, mid), solve(mid + 1, r);
}

int main()
{
int n = read();
for (int i = 1; i <= n; i++)
a[i] = read(), pos[a[i]] = i;
solve(1, n);
// a[0] = 1e9;
// a[n + 1] = 1e9;
// s.push(0);
// for (int i = 1; i <= n; i++)
// {
// while (!s.empty() && a[i] > a[s.top()])
// s.pop();
// L[i] = s.top() + 1;
// s.push(i);
// }
// while (!s.empty())
// s.pop();
// s.push(n + 1);
// for (int i = n; i >= 1; i--)
// {
// while (!s.empty() && a[i] > a[s.top()])
// s.pop();
// R[i] = s.top() - 1;
// s.push(i);
// }
// ll ans = 0;
// for (int i = 1; i <= n; i++)
// {
// // cout << L[i] << " " << R[i] << endl;
// if (i - L[i] < R[i] - i)
// {
// for (int j = L[i]; j < i; j++)
// if (pos[a[i] - a[j]] > i && pos[a[i] - a[j]] <= R[i])
// ans++;
// }

// else
// {
// for (int j = i + 1; j <= R[i]; j++)
// if (pos[a[i] - a[j]] < i && pos[a[i] - a[j]] >= L[i])
// ans++;
// }
// }
printf("%d\n", ans);
}
HDU6701
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
100
101
#include <bits/stdc++.h>
#include <set>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0', c = getchar();
return x * f;
}

int L[N], R[N], Lc[N], Rc[N], pos[N];
int a[N];

int main()
{
int T = read();
while (T--)
{
int n = read(), k = read();

for (int i = 1; i <= n; i++)
a[i] = read();
stack<int> s;
a[0] = 1e9;
a[n + 1] = 1e9;
s.push(0);
for (int i = 1; i <= n; i++)
{
while (!s.empty() && a[i] > a[s.top()])
s.pop();
L[i] = s.top() + 1;
s.push(i);
}
while (!s.empty())
s.pop();
s.push(n + 1);
for (int i = n; i >= 1; i--)
{
while (!s.empty() && a[i] > a[s.top()])
s.pop();
R[i] = s.top() - 1;
s.push(i);
}
for (int i = 1; i <= n; i++)
pos[i] = 0;
for (int i = 1; i <= n; i++)
{
Lc[i] = pos[a[i]] + 1;
pos[a[i]] = i;
}
for (int i = 1; i <= n; i++)
Lc[i] = max(Lc[i], Lc[i - 1]);
for (int i = 1; i <= n; i++)
pos[i] = n + 1;
for (int i = n; i >= 1; i--)
{
Rc[i] = pos[a[i]] - 1;
pos[a[i]] = i;
}
Rc[n + 1] = 1e9;
for (int i = n; i >= 1; i--)
Rc[i] = min(Rc[i], Rc[i + 1]);
ll ans = 0;
for (int i = 1; i <= n; i++)
{
//cout << L[i] << " " << R[i] << endl;
int len = a[i] - k;
if (i - L[i] < R[i] - i)
{
for (int j = L[i]; j <= i; j++)
{
int rr = max(i, j + len - 1);
ans += max(0, min(Rc[j], R[i]) - rr + 1);
}
}
//cout << ans << endl;
else
{
for (int j = i; j <= R[i]; j++)
{
int ll = min(i, j - len + 1);
ans += max(0, ll - max(Lc[j], L[i]) + 1);
}
}
}
printf("%lld\n", ans);
}
}