bzoj4553 [Tjoi2016&Heoi2016]序列

Description

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值

可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你

，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可

。注意：每种变化最多只有一个值发生变化。在样例输入1中，所有的变化是：

1 2 3

2 2 3

1 3 3

1 1 31 2 4

选择子序列为原序列，即在任意一种变化中均为不降子序列在样例输入2中，所有的变化是:3 3 33 2 3选择子序列

为第一个元素和第三个元素，或者第二个元素和第三个元素，均可满足要求

所有数字均为正整数，且小于等于100,000

Solution

一个需要注意的点是每次只能有一个数字发生改变

记录一下第i个数字a[i]能取得最小值l[i]和最大值r[i]，一个j能接在i后面需要满足i< j且r[i]<=a[j]且a[i]<=l[j]

容易得到一个n^2的dp柿子，仔细观察一下发现实际上就是一个三维偏序问题，直接上cdq分治。感觉树套树也是能过的

理性来说直接快排多方便x

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define lowbit(x) ((x)&(-(x)))

const int N=;

struct data {int a,l,r,id,ans;} t[N];

int c[N*+],Mx=,ans=;

void add(int x,int v) {
    for (;x<=Mx;x+=lowbit(x)) c[x]=std:: max(c[x],v);
}

void clear(int x) {
    for (;x<=Mx;x+=lowbit(x)) c[x]=;
}

int get(int x) {
    int ret=;
    for (;x;x-=lowbit(x)) ret=std:: max(ret,c[x]);
    return ret;
}

bool cmpl(data x,data y) {
    return x.l<y.l;
}

bool cmp(data x,data y) {
    return x.id<y.id;
}

bool cmpa(data x,data y) {
    return x.a<y.a;
}

void cdq(int l,int r) {
    if (l==r) {
        ans=std:: max(ans,t[l].ans);
        return ;
    }
    int mid=(l+r)>>;
    cdq(l,mid); std:: sort(t+mid+,t+r+,cmpl);
    for (int i=l,j=mid+;j<=r;j++) {
        while (i<=mid&&t[i].a<=t[j].l) {
            add(t[i].r,t[i].ans); i++;
        }
        t[j].ans=std:: max(t[j].ans,get(t[j].a)+);
    }
    std:: sort(t+mid+,t+r+,cmp);
    rep(i,l,mid) clear(t[i].r);
    cdq(mid+,r);
    std:: sort(t+l,t+r+,cmpa);
}

int main(void) {
    int n,m; scanf("%d%d",&n,&m);
    rep(i,,n) scanf("%d",&t[i].a);
    rep(i,,n) t[i].l=t[i].r=t[i].a;
    rep(i,,n) t[t[i].id=i].ans=;
    rep(i,,m) {
        int x,y; scanf("%d%d",&x,&y);
        t[x].l=std:: min(t[x].l,y);
        t[x].r=std:: max(t[x].r,y);
    }
    rep(i,,n) Mx=std:: max(Mx,t[i].r);
    cdq(,n);
    printf("%d\n", ans);
    return ;
}