M_sea

洛谷4093 [HEOI2016/TJOI2016]序列
LuoguBZOJ分析设$up[i]$表示$i$最大能取多少,$down[i]$表示$i$最小能取多少。按照平常的...
扫描右侧二维码阅读全文
10
2019/01

洛谷4093 [HEOI2016/TJOI2016]序列

Luogu

BZOJ

分析

设$up[i]$表示$i$最大能取多少,$down[i]$表示$i$最小能取多少。

按照平常的最长不下降子序列的方法,设$f[i]$表示以$i$结尾的最长不下降子序列的长度。

然后,状态转移方程还是$\large f[i]=\max\limits_{j=1}^{i-1}\Big\{f[j]+1\Big\}$。

考虑限制条件。显然有$a[i]\leq up[i],down[i]\leq a[i],j\leq i$。

发现这个东西是三维偏序的形式,然后就可以用CDQ分治来搞了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmax(int& x,int y) { if (y>x) x=y; }
inline void chkmin(int& x,int y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;

int n,m,mx=-1;
int a[MAXN],up[MAXN],down[MAXN];
int f[MAXN],id[MAXN];
int c[MAXN];
inline int cmp1(int i,int j) { return a[i]<a[j]; }
inline int cmp2(int i,int j) { return down[i]<down[j]; }

inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) {
    while (x<=mx) chkmax(c[x],y),x+=lowbit(x);
}
inline void clean(int x) {
    while (x<=mx) c[x]=0,x+=lowbit(x);
}
inline int query(int x,int ans=0) {
    while (x) chkmax(ans,c[x]),x-=lowbit(x);
    return ans;
}

inline void CDQ(int l,int r) {
    if (l==r) { chkmax(f[l],1); return; }
    int mid=(l+r)>>1;
    CDQ(l,mid);
    for (re int i=l;i<=r;++i) id[i]=i;
    sort(id+l,id+mid+1,cmp1); sort(id+mid+1,id+r+1,cmp2);
    int j=l;
    for (re int i=mid+1;i<=r;++i) {
        while (j<=mid&&a[id[j]]<=down[id[i]])
            add(up[id[j]],f[id[j]]),++j;
        chkmax(f[id[i]],query(a[id[i]])+1);
    }
    for (re int i=l;i<j;++i) clean(up[id[i]]);
    CDQ(mid+1,r);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) a[i]=up[i]=down[i]=read();
    for (re int i=1;i<=m;++i) {
        int x=read(),y=read();
        chkmax(up[x],y),chkmin(down[x],y);
    }
    for (re int i=1;i<=n;++i) chkmax(mx,up[i]);
    CDQ(1,n);
    int ans=0;
    for (re int i=1;i<=n;++i) chkmax(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 01 月 23 日 01 : 02 PM

发表评论