洛谷 P4093 [HEOI2016/TJOI2016]序列 解题报告

时间：2023-03-09 14:57:18
洛谷 P4093 [HEOI2016/TJOI2016]序列 解题报告

P4093 [HEOI2016/TJOI2016]序列

题目描述

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可 。

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

1 2 3

2 2 3

1 3 3

1 1 3

1 2 4

输入输出格式

输入格式：

输入的第一行有两个正整数\(n\),\(m\)，分别表示序列的长度和变化的个数。接下来一行有\(n\)个数，表示这个数列原始的状态。接下来\(m\)行，每行有2个数\(x\),\(y\)，表示数列的第\(x\)项可以变化成\(y\)这个值。\(1 \le x \le n\)。

输出格式：

输出一个整数，表示对应的答案

说明

对于\(20\%\)数据所有数字均为正整数，且小于等于\(300\)

对于\(50\%\)数据所有数字均为正整数，且小于等于\(3,000\)

对于\(100\%\)数据所有数字均为正整数，且小于等于\(100,000\)

窝太菜了，\(dp\)想复杂了...

一开始一直想着是只能改一个还要取最坏情况，我不可能在\(dp\)状态里面存着这些奇怪的是否取了还能取到最差结果啊。

然而重点在于取最坏情况的任意性...

令\(mx_i,mi_i.now_i\)分别为位置\(i\)的可取最大，最小和当前值。

则可以转移\(dp_i=\max dp_j+1(mx_j\le now_i \&\& now_j\le mi_i)\)

后面的偏序条件可以树套树维护，这里采用CDQ分治

有一些注意点

  • 先做左边，然后处理左对右的贡献，然后做右边
  • 处理完贡献要把右边的顺序还原

Code:

#include <cstdio>

#include <algorithm>

const int N=1e5+10;

struct node

{

    int mi,mx,now,id;

}q[N],sq[N];

bool cmp1(node n1,node n2){return n1.mx<n2.mx;}

bool cmp2(node n1,node n2){return n1.now<n2.now;}

int s[N],n,m,ans[N];

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

void add(int x,int d){while(x<=N)s[x]=max(s[x],d),x+=x&-x;}

void Clear(int x){while(x<=N)s[x]=0,x+=x&-x;}

int ask(int x){int mx=0;while(x)mx=max(mx,s[x]),x-=x&-x;return mx;}

void CDQ(int l,int r)

{

    if(l==r) {ans[q[l].id]=max(ans[q[l].id],1);return;}

    int mid=l+r>>1;

    CDQ(l,mid);

    for(int i=mid+1;i<=r;i++) sq[i]=q[i];

    std::sort(q+l,q+mid+1,cmp1);std::sort(q+mid+1,q+r+1,cmp2);

    int lp=l,rp=mid+1;

    while(lp<=mid&&rp<=r)

    {

        if(q[lp].mx<=q[rp].now)

            add(q[lp].now,ans[q[lp].id]),++lp;

        else

            ans[q[rp].id]=max(ans[q[rp].id],ask(q[rp].mi)+1),++rp;

    }

    while(rp<=r) ans[q[rp].id]=max(ans[q[rp].id],ask(q[rp].mi)+1),++rp;

    for(int i=l;i<lp;i++) Clear(q[i].now);

    for(int i=mid+1;i<=r;i++) q[i]=sq[i];

    CDQ(mid+1,r);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

        scanf("%d",&q[i].now),q[i].mx=q[i].mi=q[i].now,q[i].id=i;

    for(int a,b,i=1;i<=m;i++)

    {

        scanf("%d%d",&a,&b);

        q[a].mi=min(q[a].mi,b);

        q[a].mx=max(q[a].mx,b);

    }

    CDQ(1,n);

    int mx=0;

    for(int i=1;i<=n;i++) mx=max(mx,ans[i]);

    printf("%d\n",mx);

    return 0;

}

2018.11.27

相关文章