启发式分治

发表于 | 阅读数

启发式分治

例题 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);
    }
}