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
此题可转化为一个序列 \(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)\) 来作为它的权值。
这样,就可以实现上面的想法了:用前面来更新后面。
\(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