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 ;
}