Make Rounddog Happy(2019年杭电多校第十场1011+HDU6701+启发式分治)

目录
  • 题目链接
  • 题意
  • 思路
  • 代码

题目链接

传送门

题意

求有多少个子区间满足\(a_l,a_{l+1},\dots,a_r\)均不相同且\(max(a_l,a_{l+1},\dots,a_r)-(r-l+1)\leq K\)。

思路

听说是启发式分治然后就去学了下如何套板子，赛场上写搓了本地过不了样例，赛后改过来了。

启发式分治在本题的思路貌似就是在处理\([l,r]\)时找到区间最大值的位置\(mid\)，然后看左半部分区间长度短还是右半部分短，然后暴力统计短的那部分的贡献。

首先预处理出以\(i\)为左端点，区间内没有相同数的右端点\(R[i]\)和以\(i\)为右端点，区间内没有相同数的左端点\(L[i]\)，再用\(st\)表处理出区间最大值的位置。

在分治时由于我们已知最大值位置在哪，然后算贡献时(拿左半部分为例子)枚举不等式中的\(l\)，然后移项计算出满足题意的最近右端点\(r\geq a[mid]-K+l-1\)，然后用以\(l\)为左端点区间内没有相同数的右端点\(R[l]\)(满足题意的最远右端点)来减去这个值就是这个左端点的贡献，复杂度为\(O(nlog(n))\)。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson (rt<<1),L,mid
#define rson (rt<<1|1),mid + 1,R
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< n) break;
        for(int i = 1; i + (1<= dp[i+(1<<(j-1))][j-1]) {
                dp[i][j] = dp[i][j-1];
                pos[i][j] = pos[i][j-1];
            } else {
                dp[i][j] = dp[i+(1<<(j-1))][j-1];
                pos[i][j] = pos[i+(1<= dp[r-(1< r) return;
    int mid = query(l, r);
    if(r - mid > mid - l) {
        for(int i = l; i <= mid; ++i) {
            int rs = a[mid] - K + i - 1;
            rs = max(rs, mid);
            int dd = min(r, R[i]);
            if(rs > dd) continue;
            ans += dd - rs + 1;
        }
    } else {
        for(int i = mid; i <= r; ++i) {
            int ls = K - a[mid] + i + 1;
            ls = min(ls, mid);
            int dd = max(l, L[i]);
            if(ls < dd) continue;
            ans += ls - dd + 1;
        }
    }
    solve(l, mid - 1), solve(mid + 1, r);
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &K);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            dp[i][0] = a[i];
            pos[i][0] = i;
            vis[i] = 0;
        }
        int r = 2;
        vis[a[1]] = 1;
        for(int i = 1; i <= n; ++i) {
            while(r <= n && !vis[a[r]]) {
                vis[a[r]] = 1;
                ++r;
            }
            vis[a[i]] = 0;
            R[i] = r - 1;
        }
        vis[a[n]] = 1;
        int l = n - 1;
        for(int i = n; i >= 1; --i) {
            while(l >= 1 && !vis[a[l]]) {
                vis[a[l]] = 1;
                --l;
            }
            vis[a[i]] = 0;
            L[i] = l + 1;
        }
        init();
        ans = 0;
        solve(1, n);
        printf("%lld\n", ans);
    }
    return 0;
}
比赛题解感想迷之分治

相关

标签