文档章节

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

o
 osc_wws45aot
发布于 2019/08/21 20:05
字数 832
阅读 12
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

[TOC]

题目链接

传送门

题意

求有多少个子区间满足$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 <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> 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"=["<<x<<"]" <<endl
#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 300000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

LL ans;
int t, n, K;
int a[maxn], L[maxn], R[maxn], vis[maxn], dp[maxn][20], pos[maxn][20];

void init() {
    for(int j = 1; j < 20; ++j) {
        if(1<<(j-1) > n) break;
        for(int i = 1; i + (1<<j) - 1 <= n; ++i) {
            if(dp[i][j-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<<j-1)][j-1];
            }
        }
    }
}

int query(int l, int r) {
    int k = log(r - l + 1) / log(2);
    if(dp[l][k] >= dp[r-(1<<k)+1][k]) return pos[l][k];
    else return pos[r-(1<<k)+1][k];
}

void solve(int l, int r) {
    if(l > 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;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Linux 多屏幕管理软件--XRandR

XRandR是X Rotate and Reflect Extension(改变大小与旋转扩充)的缩写,用来在命令行界面中对linux系统中的 X窗口系统的多屏幕做出一些设定的软件,能更改外接屏幕的大小、分辨率等...

匿名
2012/10/22
3.1K
0
C多线程网络库--xs

基于C多线程网络库,欢迎大家使用,例子在代码example目录下,以后我会再增加一些例子。 文档暂时没有,有问题请邮件我:-) 获取代码:https://github.com/xueguoliang/xs xs致力于1)多线程网...

薛国良
2013/05/01
4.4K
0
微信框架的几个层次

第一层次:通信处理 对访问微信服务器进行处理,主要解决报文来来去去的问题。这里采用的技术一般是HttpClient或类似的技术。 第二层次:报文解析 通过对报文进行解析,让程序员直接要拿到的...

悠悠然然
2015/12/01
9.3K
58
phalapi-进阶篇5(数据库读写分离以及多库使用)

先在这里感谢phalapi框架创始人@dogstar,为我们提供了这样一个优秀的开源框架. 读写分离是我们常用的一种解决方案,它可以解决大量读操作的时候数据库瓶颈的问题,我们在真正开发一个项目的过程...

喵了_个咪
2015/11/24
2.1K
4
在mac上用AndroidStudio1.5 创建NDK开发环境(Ubuntu 16.4LTS亲测可用)

本文参考了youtube上的一个视频,想直接看视频的可以访问 https://www.youtube.com/watch?v=RmPuwdxR1qs (要翻墙) 废话少说打开androidStudio,新建一个工程 NDKTest 新建完毕 依次打开 File...

franos
2016/03/27
1.1K
0

没有更多内容

加载失败,请刷新页面

加载更多

SQL 语句大全

点击上方“掌上编程”,选择“置顶或者星标” 优质文章第一时间送达! 一、基础 「1、说明:创建数据库」 CREATE DATABASE database-name    「2、说明:删除数据库」 drop database ...

GeneralMa
昨天
0
0
山东创睦网络科技有限公司:使用Python爬取全球新冠肺炎疫情数据

使用Python爬取全球新冠肺炎疫情数据 导入所需库包 获取实时数据的url 正式编写程序 查看输出结果 导入所需库包 在获取数据之前,我们需要先安装好所需的包requests和pandas: 1.如果是使用p...

osc_qv1fwke0
58分钟前
14
0
如何1年获得别人3年的工作经验(深度好文)

最近有同学问我,为什么你的工作年限不长,技术却这么厉害,我笑了笑,啥也没说。 我不是不想回答,是不知道怎么回答。在他们的定位可能就是,每方面都懂一点,遇到问题能够快速解决,就是比...

zhang_rick
今天
1
0
新基建带动行业

什么是“新基建”? 什么是“新基建”? 根据央视发布的信息来看,其涵盖了5G基站建设、新能源汽车充电桩、大数据中心、人工智能、工业互联网,特高压,城际以及城轨交通,涉及了七大领域和相...

osc_anefoz50
59分钟前
16
0
怕入错行?这群技术人写了本“择业指南”

计算机专业好找工作吗?哪些方向是当前的主流和热门方向呢? 计算机专业的你是不是还在为职业发展纠结犹豫呢? 刚经历完高考选专业的你是不是还在迷茫徘徊呢? 那么福利来啦! 《软件技术职业...

阿里云云栖号
59分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部