传送门
Description
佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可。注意：每种变化最多只有一个值发生变化。在样例输入1中，所有的变化是：
1 2 3
2 2 3
1 3 3
1 1 3
1 2 4选择子序列为原序列，即在任意一种变化中均为不降子序列在样例输入2中，所有的变化是:3 3 33 2 3选择子序列为第一个元素和第三个元素，或者第二个元素和第三个元素，均可满足要求
Solution
每个元素加下三个值：原值x，最大值ma，最小值mi
前后两个元素（a，b）要满足：
- (a.x leq b.mi)
- (a.ma leq b.x)
(dp[i]=max_{j} dp[j]+1),其中j，i满足上面两个条件
cdq求三维偏序即可，但是条件的左右属性是不一样的，所以要对(l,mid)和(mid+1,r)分别按照x和mi来排序
复杂度是(O(n log^2 n))
Code
#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
#define MN 100005
struct Node{int x,ma,mi,id;}a[MN];
inline bool cmp1(const int&o,const int&oo){return a[o].x<a[oo].x;}
inline bool cmp2(const int&o,const int&oo){return a[o].mi<a[oo].mi;}
int n,m,t[MN],f[MN],id[MN];
#define lb(x) (x&(-x))
inline void C(int x,int v){for(;x<MN;x+=lb(x)) t[x]=max(t[x],v);}
inline int G(int x){int r=0;for(;x;x-=lb(x)) r=max(r,t[x]);return r;}
inline void C0(int x){for(;x<MN;x+=lb(x)) t[x]=0;}
void solve(int l=1,int r=n)
{
// x.val<=y.min
// x.max<=y.val
if(l==r) return;
int mid=(l+r)>>1;
solve(l,mid);
register int i,j;
for(i=l;i<=r;++i) id[i]=i;
std::sort(id+l,id+mid+1,cmp1);
std::sort(id+mid+1,id+r+1,cmp2);
for(j=l,i=mid+1;i<=r;++i)
{
for(;j<=mid&&a[id[j]].x<=a[id[i]].mi;++j) C(a[id[j]].ma,f[a[id[j]].id]);
f[a[id[i]].id]=max(f[a[id[i]].id],G(a[id[i]].x)+1);
}
for(i=l;i<=mid;++i) C0(a[id[i]].ma);
solve(mid+1,r);
}
int main()
{
n=read();m=read();
register int i,v;
for(i=1;i<=n;++i) a[i].id=i,a[i].x=a[i].mi=a[i].ma=read(),f[i]=1;
while(m--)
{
i=read();v=read();
a[i].ma=max(a[i].ma,v);
a[i].mi=min(a[i].mi,v);
}
solve();
register int ans=0;
for(i=1;i<=n;++i) ans=max(ans,f[i]);
printf("%d
",ans);
return 0;
}
Blog来自PaperCloud，未经允许，请勿转载，TKS！