P4093[HEOI2016/TJOI2016]序列
题目描述
佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。
玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。
输入格式
输入的第一行有两个正整数 n , m n,m n,m,分别表示序列的长度和变化的个数。
接下来一行有 n n n 个整数,表示这个数列原始的状态。
接下来 m m m 行,每行有 2 2 2 个整数 x , y x,y x,y,表示数列的第 x x x 项可以变化成 y y y 这个值。
输出格式
输出一个整数,表示对应的答案。
样例 #1
样例输入 #1
3 4
1 2 3
1 2
2 3
2 1
3 4
样例输出 #1
3
提示
注意:每种变化最多只有一个值发生变化。
在样例输入中,所有的变化是:
1 2 3
2 2 3
1 3 3
1 1 3
1 2 4
选择子序列为原序列,即在任意一种变化中均为不降子序列。
对于 20 % 20\% 20% 数据,所有数均为正整数,且小于等于 300 300 300。
对于 50 % 50\% 50% 数据,所有数字均为正整数,且小于等于 3000 3000 3000。
对于 100 % 100\% 100% 数据,所有数字均为正整数,且小于等于 1 0 5 10^5 105。 1 ≤ x ≤ n 1\le x\le n 1≤x≤n。
题目大意
有一个序列以及它的 n n n 种不同的变化,每次变化可以把 a x a_x ax 变成 y y y 。
你需要找出一个序列,使得在任何一种变化中(可以不变化),这个序列保持不降。
题目问你这种满足这种要求的序列的最大长度是多少?
思路
我们可以处理出 M x [ i ] , M n [ i ] Mx[i] , Mn[i] Mx[i],Mn[i] 表示在所有变化中 i i i 可以达到的最大值和最小值。
显然我们可以用
d
p
dp
dp 来做这道题,转移方程:
KaTeX parse error: Undefined control sequence: \and at position 34: …f_j) (i \leq j \̲a̲n̲d̲ ̲a_j \leq Mn_i \…
我们观察一下这个转移方程,发现这是一个
O
(
n
2
)
O(n ^ 2)
O(n2) 的方法吗,然后我们考虑用 CDQ分治 + 树状数组 维护
对于区间 [ l , r ] [l , r] [l,r] ,
我们把 [ l , m i d ] [l , mid] [l,mid] 按照 M x i Mx_i Mxi 升序排序,把区间 [ m i d + 1 , r ] [mid + 1 , r] [mid+1,r] 按照 a i a_i ai 升序排序
然后对于 [ m i d + 1 , r ] [mid + 1 , r] [mid+1,r] 用树状数组维护小于 M n i Mn_i Mni 的数就好了。
然后就发现我们把它转化成了三维偏序问题。文章来源:https://www.toymoban.com/news/detail-434621.html
最后时间复杂度就变成了 O ( n l o g 2 n ) O(n log_2 n) O(nlog2n) 可以通过。文章来源地址https://www.toymoban.com/news/detail-434621.html
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
#define LL long long
using namespace std;
const int N = 1e5 + 5;
int tr[N] , f[N] , n , m , a[N] , ans , Mx[N] , Mn[N] , p[N];
int read () {
int val = 0 , fu = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {
if (ch == '-') fu = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
val = val * 10 + (ch - '0');
ch = getchar ();
}
return val * fu;
}
bool cmp1 (int x , int y) { return Mx[x] < Mx[y]; }
bool cmp2 (int x , int y) { return a[x] < a[y]; }
int lowbit (int x) { return x & (-x); }
void Insert (int x , int y) {
while (x <= n) {
tr[x] = max (tr[x] , y);
x += lowbit (x);
}
}
int query (int x) {
int sum = 0;
while (x) {
sum = max (sum , tr[x]);
x -= lowbit (x);
}
return sum;
}
void Clear (int x) {
while (x <= n) {
tr[x] = 0;
x += lowbit (x);
}
}
void cdq (int l , int r) {
if (l == r) {
f[l] = max (f[l] , 1);
return;
}
else {
int mid = l + r >> 1;
cdq (l , mid);
fu (i , l , r)
p[i] = i;
sort (p + l , p + mid + 1 , cmp1) , sort (p + mid + 1 , p + r + 1 , cmp2);
int j = l;
fu (i , mid + 1 , r) {
while (j <= mid && Mx[p[j]] <= a[p[i]]) {
Insert (a[p[j]] , f[p[j]]);
j ++;
}
f[p[i]] = max (f[p[i]] , query (Mn[p[i]]) + 1);
}
fu (i , l , mid) {
Clear (a[i]);
}
cdq (mid + 1 , r);
}
}
int main () {
n = read () , m = read ();
fu (i , 1 , n) {
a[i] = read ();
Mx[i] = Mn[i] = a[i];
}
int x , y;
fu (i , 1 , m) {
x = read () , y = read ();
Mx[x] = max (Mx[x] , y) , Mn[x] = min (Mn[x] , y);
}
cdq (1 , n);
fu (i , 1 , n)
ans = max (ans , f[i]);
printf ("%d" , ans);
return 0;
}
到了这里,关于P4093[HEOI2016/TJOI2016]序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!