首页 > 其他 > 详细

BZOJ 4553: [Tjoi2016&Heoi2016]序列 CDQ分治 树套树

时间:2019-09-13 21:21:59      阅读:67      评论:0      收藏:0      [点我收藏+]

title

BZOJ 4553

LUOGU 4093

Description

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

注意:每种变化最多只有一个值发生变化。在样例输入 \(1\) 中,所有的变化是:

1 2 3
2 2 3
1 3 3
1 1 3
1 2 4

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

3 3 3
3 2 3

选择子序列为第一个元素和第三个元素,或者第二个元素和第三个元素,均可满足要求。

Input

输入的第一行有两个正整数 \(n, m\),分别表示序列的长度和变化的个数。接下来一行有 \(n\) 个数,表示这个数列原始的状态。接下来 \(m\) 行,每行有 \(2\) 个数 \(x, y\),表示数列的第 \(x\) 项可以变化成 \(y\) 这个值。\(1\leqslant x \leqslant n\)。所有数字均为正整数,且小于等于 \(100,000\)

Output

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

Sample Input

3 4
1 2 3
1 2
2 3
2 1
3 4

Sample Output

3

analysis

此题可转化为一个序列 \(Dp\) ,设序列中的一个元素的原始值为 \(a_i\) ,最大值为 \(Max_i\) ,最小值为 \(Min_i\) ,则有:
\[ f_i=f_j+1(j\leqslant i,Max_j\leqslant a_i,a_j\leqslant Min_i) \]

所以这就是一个三维偏序的问题。

可以用树套树或者 \(CDQ\) 分治解决。

树套树,可以用 \(BIT\)\(SGT\) ,维护后两个条件即可。

\(CDQ\) 分治可以这样做:

对于区间 \([l,r]\) ,如果这个元素 \(i\)\(mid\) 前面,我们就用 \((Max_i,a_i)\) 作为它的权值;否则,就用 \((a_i,Min_i)\) 来作为它的权值。

这样,就可以实现上面的想法了:用前面来更新后面。

code

\(CDQ\) 分治

#include<bits/stdc++.h>

const int maxn=3e5+10,MaxV=3e5;
typedef int iarr[maxn];

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    template<typename T>inline void read(T &x)
    {
        x=0;
        T f=1, ch=getchar();
        while (!isdigit(ch) && ch^'-') ch=getchar();
        if (ch=='-') f=-1, ch=getchar();
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    template<typename T>inline void write(T x,char str)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++=str;
    }
}

using IO::read;
using IO::write;

template<typename T>inline bool chkMin(T &a,const T &b) { return a>b ? (a=b, true) : false; }
template<typename T>inline bool chkMax(T &a,const T &b) { return a<b ? (a=b, true) : false; }

namespace BIT
{
    int c[maxn];
    inline int lowbit(int x) { return x & -x; }
    inline void add(int x,int k) { while (x<=MaxV) !k ? c[x]=0 : chkMax(c[x],k), x+=lowbit(x); }
    inline int ask(int x) { int ans=0; while (x) chkMax(ans,c[x]), x-=lowbit(x); return ans; }
}

using BIT::add;
using BIT::ask;

struct Orz{int x,y,id;}o[maxn];
inline bool cmp(const Orz &a,const Orz &b)
{
    return a.x<b.x || (a.x==b.x && a.id<b.id);
}

iarr a,f,Max,Min;
inline void CDQ(int l,int r)
{
    if (l==r) { chkMax(f[l],1); return ; }
    int mid=(l+r)>>1;
    CDQ(l,mid);
    for (int i=l; i<=r; ++i)
    {
        if (i<=mid) o[i].x=a[i], o[i].y=Max[i];
        else o[i].x=Min[i], o[i].y=a[i];
        o[i].id=i;
    }
    std::sort(o+l,o+r+1,cmp);
    for (int i=l; i<=r; ++i)
    {
        if (o[i].id<=mid) add(o[i].y,f[o[i].id]);
        else chkMax(f[o[i].id],ask(o[i].y)+1);
    }
    for (int i=l; i<=r; ++i) add(o[i].y,0);
    CDQ(mid+1,r);
}

int main()
{
    int n,m;read(n);read(m);
    for (int i=1; i<=n; ++i) read(a[i]), Max[i]=Min[i]=a[i];
    for (int i=1,x,v; i<=m; ++i)
    {
        read(x);read(v);
        chkMax(Max[x],v);
        chkMin(Min[x],v);
    }
    CDQ(1,n);
    int ans=0;
    for (int i=1; i<=n; ++i) chkMax(ans,f[i]);
    write(ans,'\n');
    IO::flush();
    return 0;
}

树套树大法好

#include<bits/stdc++.h>

const int maxn=1e5+10,MaxV=1e5;
typedef int iarr[maxn];

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    template<typename T>inline void read(T &x)
    {
        x=0;
        T f=1, ch=getchar();
        while (!isdigit(ch) && ch^'-') ch=getchar();
        if (ch=='-') f=-1, ch=getchar();
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    template<typename T>inline void write(T x,char str)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++=str;
    }
}

using IO::read;
using IO::write;

template<typename T>inline bool chkMin(T &a,const T &b) { return a>b ? (a=b, true) : false; }
template<typename T>inline bool chkMax(T &a,const T &b) { return a<b ? (a=b, true) : false; }
template<typename T>inline T min(T a,T b) { return a<b ? a : b; }
template<typename T>inline T max(T a,T b) { return a>b ? a : b; }

struct SGT
{
    struct Orz{int l,r,z;}c[maxn*100]; int cnt;
    inline void Change(int &x,int l,int r,int pos,int k)
    {
        if (!x) x=++cnt;
        chkMax(c[x].z,k);
        if (l==r) return ;
        int mid=(l+r)>>1;
        if (pos<=mid) Change(c[x].l,l,mid,pos,k);
        else Change(c[x].r,mid+1,r,pos,k);
    }

    inline int query(int x,int l,int r,int tl,int tr)
    {
        if (!x || l>tr || r<tl) return 0;
        if (tl<=l && r<=tr) return c[x].z;
        int mid=(l+r)>>1;
        return max(query(c[x].l,l,mid,tl,tr),query(c[x].r,mid+1,r,tl,tr));
    }
} sgt;

iarr a,Max,Min,f;
struct BIT
{
    int rt[maxn];
    inline int lowbit(int x) { return x & -x; }

    inline void add(int x)
    {
        for (int i=a[x]; i<=MaxV; i+=lowbit(i)) sgt.Change(rt[i],1,MaxV,Max[x],f[x]);
    }

    inline int ask(int x)
    {
        int ans=0;
        for (int i=Min[x]; i>=1; i-=lowbit(i)) chkMax(ans,sgt.query(rt[i],1,MaxV,1,a[x]));
        return ans;
    }
}bit;

int main()
{
    int n,m;read(n);read(m);
    for (int i=1; i<=n; ++i) read(a[i]), Max[i]=Min[i]=a[i];
    for (int i=1,x,v; i<=m; ++i)
    {
        read(x);read(v);
        chkMax(Max[x],v);
        chkMin(Min[x],v);
    }
    int ans=0;
    for (int i=1; i<=n; ++i)
    {
        f[i]=bit.ask(i)+1;
        chkMax(ans,f[i]);
        bit.add(i);
    }
    write(ans,'\n');
    IO::flush();
    return 0;
}

BZOJ 4553: [Tjoi2016&Heoi2016]序列 CDQ分治 树套树

原文:https://www.cnblogs.com/G-hsm/p/BZOJ_4553.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!