[heuristic divide and conquer] the inverse idea of heuristic merging

Blog ：

• ( violence / Heuristic splitting ) Code source daily question Div1 Good sequence

• Heuristic divide and conquer

• 「 essays 」 A divide and conquer strategy based on heuristic thought —— Heuristic splitting

First think about the heuristic method of merging sequence attributes ： Take the number of attributes as an example that satisfy the property of the sequence . Now there are two sets , It is required to calculate the number of merged pairs . We enumerate the elements in a smaller set , Query number to number in another set . Put larger elements after query . Time complexity $O(n\log n)$

Heuristic divide and conquer is actually the inverse process of heuristic merging . We choose a subscript in an interval as the dividing point （ Divide and conquer in reverse order 、 The dividing points selected in the sorting algorithm are all intermediate points ）, Count the number of pairs of left and right subintervals . Then we need to calculate the number of pairs at both ends of the dividing point , Here we need the core of heuristic divide and conquer ： enumeration There are fewer interval elements The elements of , Then count the number of pairs in another interval . This is exactly the inverse process of heuristic merging . This ensures that the time complexity is also $O(n\log n)$

---

#613. Good sequence

The question ： There's a long one for $n$ Sequence $A_1,A_2,\cdots ,A_n$ . Define a sequence $\{A\}$ Good. , If and only if each of his subintervals $[l,r]$ Satisfy , At least one element exists $x$ Only once .

Answer key ：- ( violence / Heuristic splitting ) Code source daily question Div1 Good sequence

Ideas ： First preprocess the subscript of each number that is the same as him and the nearest number . For an interval $[l,r]$ , If there is a number that only appears once , Then it must be good to span the subinterval of this number , Don't have to consider , Just consider the two sub intervals separated . The core here is to enumerate from both ends to the middle , This can ensure that the number of enumerations must be less than half of the total number of elements .

AC Code ：http://oj.daimayuan.top/submission/299119

---

HDU 2019 Multi school Make Rounddog Happy

The question ： The length of the question is $n(n\le 3\times 10^5)$ How many subintervals satisfy $\max (a_l,a_{l+1},\cdots ,a_r)-(r-l+1)\le k$ And the elements in the interval are different from each other

Answer key ： Heuristic divide and conquer

Ideas ： Heuristic divide and conquer takes the maximum subscript as the dividing point . Calculate the heresy with two ends at the dividing point , Then enumerate the elements in the interval with smaller length , Calculation is enough .

AC Code ：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

#define endl '\n'
#define fi first
#define se second
#define ppb pop_back
#define pb push_back
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof (x))
#define rep(i, l, r) for(LL i = l; i <= (r); ++ i)
#define per(i, r, l) for(LL i = r; i >= (l); -- i)
#define reps(i, l, r, d) for(LL i = l; i <= (r); i += d)
#define pers(i, r, l, d) for(LL i = r; i >= (l); i -= d)

template<class T> bool ckmax(T& a, T b) {
     return a < b ? (a = b, 1) : 0; }
template<class T> bool ckmin(T& a, T b) {
     return a > b ? (a = b, 1) : 0; }

const int N = 3e5 + 10, M = 1e5 + 10, LG = 20;
const LL p = 1e9 + 7;

struct st_pair{
    
    int w, idx;
    bool operator < (const st_pair & x) const{
    
        return w < x.w;
    }
};

st_pair f[N][LG];
int n, a[N], k, cnt[N], L[N], R[N];

void init(){
    
    rep(j, 0, LG - 1){
    
        for(int i = 1; i + (1 << j) - 1 <= n; i ++ ){
    
            if(!j) f[i][j] = {
    a[i], i};
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}

st_pair query(int l, int r){
    
    int k = __lg(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

LL split(int l, int r){
    
    if(l > r) return 0;
    if(l == r) return a[l] - 1 <= k;

    st_pair pr = query(l, r);
    LL mid = pr.idx, mx = pr.w;
    LL res = split(l, mid - 1) + split(mid + 1, r);

    if(mid - l < r - mid){
    
        rep(i, l, mid) if(R[i] >= mid) res += max(0LL, min(R[i], r) - max(mid, mx - k + i - 1) + 1);
    }else{
    
        rep(i, mid, r) if(L[i] <= mid) res += max(0LL, min(mid, i + 1 - mx + k) - max(L[i], l) + 1);
    }
    return res;
}

void solve()
{
    
    cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    init();

    rep(i, 1, n) cnt[i] = 0;
    for(int i = 1, j = 0; i <= n; i ++ ){
    
        while(j < n && !cnt[a[j + 1]]) j ++ , cnt[a[j]] ++ ;
        R[i] = j;
        cnt[a[i]] -- ;
    }
    rep(i, 1, n) cnt[i] = 0;
    for(int i = n, j = n + 1; i >= 1; i -- ){
    
        while(j > 1 && !cnt[a[j - 1]]) j -- , cnt[a[j]] ++ ;
        L[i] = j;
        cnt[a[i]] -- ;
    }

    cout << split(1, n) << endl;
}

int main()
{
    
    ios;

    int T; cin >> T;
    while(T -- )
        solve();


    return 0;
}