【BZOJ4553】[HAOI2016&TJOI2016]序列
2024-08-24 23:18:02
【BZOJ4553】[HAOI2016&TJOI2016]序列
题面
题解
一定要仔细看题啊qwq。。。
我们设$mn[i],mx[i]$表示第$i$个位置上最小出现、最大出现的值。
则选出的序列要满足
$ i<j\\ a[i]\leq mn[j]\\ mx[i]\leq a[j] $
这™不就是个三维偏序吗?
一边$CDQ$一边$dp$就好了
注意分治时注意清空
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e5 + 5;
void chkmin(int &x, int y) { if (x > y) x = y; }
void chkmax(int &x, int y) { if (x < y) x = y; }
int N, a[MAX_N], mx[MAX_N], mn[MAX_N], f[MAX_N];
struct Node { int x, y, z, id; } t[MAX_N];
bool cmp_id (Node a, Node b) { return a.id < b.id; }
bool cmp_x (Node a, Node b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmp_y (Node a, Node b) { return a.y == b.y ? a.z < b.z : a.y < b.y; }
int c[MAX_N], M;
inline int lb(int x) { return x & -x; }
void add(int x, int v) { while (x <= M) chkmax(c[x], v), x += lb(x); }
int sum(int x) { int res = 0; while (x > 0) chkmax(res, c[x]), x -= lb(x); return res; }
void Set(int x) { while (x <= M) c[x] = 0, x += lb(x); }
void Div(int l, int r) {
if (l == r) return (void)chkmax(f[t[l].id], 1);
int mid = (l + r) >> 1;
Div(l, mid);
sort(&t[l], &t[mid + 1], cmp_x);
sort(&t[mid + 1], &t[r + 1], cmp_y);
for (int i = mid + 1, j = l; i <= r; i++) {
while (t[j].x <= t[i].y && j <= mid) add(t[j].z, f[t[j].id]), ++j;
chkmax(f[t[i].id], sum(t[i].x) + 1);
}
for (int i = l; i <= mid; i++) Set(t[i].z);
sort(&t[l], &t[r + 1], cmp_id);
Div(mid + 1, r);
}
int main () {
N = gi(), M = gi();
for (int i = 1; i <= N; i++) a[i] = mn[i] = mx[i] = gi();
while (M--) {
int x = gi(), y = gi();
chkmax(mx[x], y), chkmin(mn[x], y);
}
for (int i = 1; i <= N; i++) t[i] = (Node){a[i], mn[i], mx[i], i}, chkmax(M, mx[i]);
Div(1, N);
int ans = 0;
for (int i = 1; i <= N; i++) chkmax(ans, f[i]);
printf("%d\n", ans);
return 0;
}
最新文章
- Linux sendmail发送邮件失败诊断案例(一)
- Centos允许root远程登录设置
- wndbg下载与安装
- Android应用性能优化之使用SparseArray替代HashMap
- Cocos2d-x 学习资料推荐
- override 与 overdown 的区别
- HttpClient的使用
- VC++读取资源中文件
- jquery简单的拖动效果
- net core与golang web
- Unity3D 如何图形问题修正旋转模型已导入?
- Canvas get/putImageData
- HDU 5008 求第k小子串
- Socket套接字
- python空字典列表两种生成方式对赋值带来的不同影响
- Centos 7 磁盘阵列配置介绍(RAID)
- 《.NET之美》之程序集
- [Jedis] ERR wrong number of arguments for &#39;mget&#39;
- 惊讶于word 的流畅
- Gitlab服务器维护
热门文章
- iOS js
- Guava包学习-Multimap
- 马克飞象markdown用法
- # 20155214 2016-2017-2 《Java程序设计》第9周学习总结
- HDU 1102(Constructing Roads)(最小生成树之prim算法)
- Blocking Master Example QT 自带 的 serial 即 串口 例子
- Vue04——vue自定义事件、Router、Vue-cli、发布上线
- Python 学习笔记(十三)Python函数(一)
- 8. DBNEWID 工具(使用nid命令修改db name及dbid)
- py基础---多线程、多进程、协程