[bzoj4552][Tjoi2016&Heoi2016]排序-二分+线段树

时间:2022-09-07 15:22:36

Brief Description

DZY有一个数列a[1..n],它是1∼n这n个正整数的一个排列。

现在他想支持两种操作:

0, l, r: 将a[l..r]原地升序排序。

1, l, r: 将a[l..r]原地降序排序。

操作完后,他会给你指定一个位置k,请你告诉他a[k]的值。

Algorithm Design

很好的一道题目, 反正我没有想到正解, 但是直接抄袭jcvb的bc题目就不太资辞了(连样例都抄也太懒了吧喂) , 附上原题地址.

这是一道良心的基础数据结构题。

我们二分a[k]的值,假设当前是mid,然后把大于mid的数字标为1,不大于mid的数字标为0。然后对所有操作做完以后检查一下a[k]位置上是0还是1。

因为只有两种值,所以操作还是不难做的。只要用一个线段树,支持区间求和、区间赋值即可。这样要排序一个区间时只要查询一下里面有几个1和几个0,然后把前半段赋值为0,后半段赋值为1即可(降序的话就是反过来)。

复杂度是\(O(mlog^2n)\)的。

这题用其他玄学做法或者用更加厉害的平衡树做法也是有可能AC的。

题解来自jcvb的官方题解

Code

#include <cstdio>
#define init int l = t[k].l, r = t[k].r, mid = (l + r) >> 1
const int maxn = 1e5 + 1e2;
int n, m, a[maxn], lambda, q;
struct seg {
int l, r, val, cov;
} t[maxn << 4];
struct op {
int a, b, c;
} o[maxn];
void update(int k) { t[k].val = t[k << 1].val + t[k << 1 | 1].val; }
void build(int k, int l, int r) {
t[k].l = l, t[k].r = r, t[k].cov = -1;
if (l == r) {
t[k].val = a[l] > lambda;
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
update(k);
}
void pushdown(int k) {
if (t[k].cov != -1) {
t[k << 1].cov = t[k].cov;
t[k << 1 | 1].cov = t[k].cov;
t[k << 1].val = (t[k << 1].r - t[k << 1].l + 1) * (t[k].cov);
t[k << 1 | 1].val = (t[k << 1 | 1].r - t[k << 1 | 1].l + 1) * (t[k].cov);
t[k].cov = -1;
}
if (t[k].l < t[k].r)
update(k);
}
int query(int k, int x, int y) {
init;
pushdown(k);
if (x <= l && r <= y)
return t[k].val;
int ans = 0;
if (x <= mid)
ans += query(k << 1, x, y);
if (y > mid)
ans += query(k << 1 | 1, x, y);
return ans;
}
void modify(int k, int x, int y, int val) {
init;
pushdown(k);
if (x <= l && r <= y) {
t[k].val = (r - l + 1) * val;
t[k].cov = val;
return;
}
if (x <= mid)
modify(k << 1, x, y, val);
if (y > mid)
modify(k << 1 | 1, x, y, val);
update(k);
}
bool check(int x) {
lambda = x;
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int opt = o[i].a, x = o[i].b, y = o[i].c;
int tmp = query(1, x, y);
if (opt == 0) {
modify(1, x, y - tmp, 0);
modify(1, y - tmp + 1, y, 1);
} else {
modify(1, x, x + tmp - 1, 1);
modify(1, x + tmp, y, 0);
}
}
return !query(1, q, q);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input", "r", stdin);
#endif
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
int l = 1, r = n;
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &o[i].a, &o[i].b, &o[i].c);
}
scanf("%d", &q);
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
printf("%d", r);
}

[bzoj4552][Tjoi2016&Heoi2016]排序-二分+线段树的更多相关文章

  1. 【BZOJ4552】&lbrack;Tjoi2016&amp&semi;Heoi2016&rsqb;排序 二分&plus;线段树

    [BZOJ4552][Tjoi2016&Heoi2016]排序 Description 在2016年,佳媛姐姐喜欢上了数字序列.因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题 ...

  2. bzoj 4552&colon; &lbrack;Tjoi2016&amp&semi;Heoi2016&rsqb;排序——二分&plus;线段树

    Description 在2016年,佳媛姐姐喜欢上了数字序列.因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题 ,需要你来帮助他.这个难题是这样子的:给出一个1到n的全排列,现在对这 ...

  3. &lbrack;BZOJ4552&rsqb;&lbrack;TJOI2016&amp&semi;&amp&semi;HEOI2016&rsqb;排序&lpar;二分答案&plus;线段树&sol;线段树分裂与合并&rpar;

    解法一:二分答案+线段树 首先我们知道,对于一个01序列排序,用线段树维护的话可以做到单次排序复杂度仅为log级别. 这道题只有一个询问,所以离线没有意义,而一个询问让我们很自然的想到二分答案.先二分 ...

  4. bzoj千题计划128:bzoj4552&colon; &lbrack;Tjoi2016&amp&semi;Heoi2016&rsqb;排序

    http://www.lydsy.com/JudgeOnline/problem.php?id=4552 二分答案 把>=mid 的数看做1,<mid 的数看做0 这样升序.降序排列相当于 ...

  5. BZOJ4552 &lbrack;Tjoi2016&amp&semi;Heoi2016&rsqb;排序 【二分 &plus; 线段树】

    题目链接 BZOJ4552 题解 之前去雅礼培训做过一道题,\(O(nlogn)\)维护区间排序并能在线查询 可惜我至今不能get 但这道题有着\(O(nlog^2n)\)的离线算法 我们看到询问只有 ...

  6. BZOJ4552&colon;&lbrack;TJOI2016&amp&semi;HEOI2016&rsqb;排序&lpar;线段树&comma;二分&rpar;

    Description 在2016年,佳媛姐姐喜欢上了数字序列.因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他. 这个难题是这样子的:给出一个1到n的全排列,现在对这 ...

  7. 2018&period;08&period;01 BZOJ4552&colon; &lbrack;Tjoi2016&Heoi2016&rsqb;排序(二分&plus;线段树)

    传送门 线段树简单题. 二分答案+线段树排序. 实际上就是二分答案mid" role="presentation" style="position: relat ...

  8. BZOJ4552 Tjoi2016&amp&semi;Heoi2016排序 【二分&plus;线段树】&ast;

    Description 在2016年,佳媛姐姐喜欢上了数字序列.因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他.这个难题是这样子的:给出一个1到n的全排列,现在对这个 ...

  9. &lbrack;BZOJ4552&rsqb;&lbrack;Tjoi2016&amp&semi;Heoi2016&rsqb;排序(二分答案&plus;线段树)

    二分答案mid,将>=mid的设为1,<mid的设为0,这样排序就变成了区间修改的操作,维护一下区间和即可 然后询问第q个位置的值,为1说明>=mid,以上 时间复杂度O(nlog2 ...

随机推荐

  1. C&num;中UnixTime和DateTime的转换(转载)

    由于在API请求中返回回来的时间格式为UNIX形式,需要转换成正常的显示方式,在网上找到了这么一个例子. 使用是在C#中使用的,所以WP8开发应该也可以. 转载源地址:http://blog.linu ...

  2. 转!!windows记事本保存&OpenCurlyDoubleQuote;联通” 编码问题

    原博文网址:http://blog.csdn.net/Zhiyuan_Ma/article/details/51838054 简单分析: 这是微软记事本的一个BUG,准确点就是unicode编码的问题 ...

  3. mysql-mmm 安装配置&lpar;双主&rpar;

    原文地址:mysql-mmm 安装配置 作者:chinaunix1116 MMM即Master-Master Replication Managerfor MySQL(mysql主主复制管理器)关于m ...

  4. 互联网4&period;0时代需要商业智能BI

    当今大数据互联网时代飞速发展,德国提出了工业化4.0, 美国提出了产业互联网,而中国提出了两化深度融合战略.越来越多的企业家开始安耐不住了,开始担心自己的企业是否跟的上时代的变化,是否使用了商业智能B ...

  5. HTML5 视频规范简介

    HTML5 视频规范简介  创建于 2013-02-03, 周日 00:56  作者 白建鹏 HTML 一词是“超文本标记语言”(Hyper-Text Markup Language)的缩写,是用于描 ...

  6. 使用ExtJs实现文件下载

    文件下载,是不可以直接通过Ext.Ajax.Request来实现的.一般的,可以通过创建一个隐藏的form表单来实现.具体代码以及代码注释如下: if (!Ext.fly('downForm')){ ...

  7. How Node&period;js Multiprocess Load Balancing Works

    As of version 0.6.0 of node, load multiple process load balancing is available for node. The concept ...

  8. USB接口定义

    一般的排列方式是:红白绿黑从左到右 定义: 红色-USB电源 标有-VCC.Power.5V.5VSB字样 绿色-USB数据线(正)-DATA+.USBD+.PD+.USBDT+ 白色-USB数据线( ...

  9. 随机采样和随机模拟:吉布斯采样Gibbs Sampling实现高斯分布参数推断

    http://blog.csdn.net/pipisorry/article/details/51539739 吉布斯采样的实现问题 本文主要说明如何通过吉布斯采样来采样截断多维高斯分布的参数(已知一 ...

  10. NFS、FTP介绍

    第二十五课 NFS.FTP介绍 目录 一. NFS介绍 二.NFS服务端安装配置 三.NFS配置选项 四.exportfs命令 五.NFS客户端问题 六.FTP介绍 七.使用vsftpd搭建ftp 八 ...