bzoj4553 [Tjoi2016&Heoi2016]序列

　　首先记录每个点原来的数字V、最小的变化L,最大的变化R，在子序列中两个点i,j(i<j)如果相邻，应满足A[I]<=L[J] && R[I]<=A[J],然后就维护一下这个东西，有点类似二维最长不降子序列，可以用cdq分治做，复杂度O(nlognlogn)。

　　代码

 1 #include<cstdio>
 2 #include<vector>
 3 #include<algorithm>
 4 #define lb(x) (x&-x)
 5 #define pb push_back
 6 using namespace std;
 7 const int N = 301010;
 8 int l[N],r[N],s[N],L[N],R[N],n,m,i,a,b,v[N],ans[N],Ans,c[N];
 9 struct g{
10     int l,r,id;
11 }d[N];
12 void cc(int x,int w)
13 {
14     while (x<=100000)
15     {
16         if (w) c[x]=max(c[x],w);else c[x]=0;
17         x+=lb(x);
18     }
19 }
20 int get(int x)
21 {
22     int ans=0;
23     while (x)
24     {
25         ans=max(ans,c[x]);
26         x-=lb(x);
27     }
28     return ans;
29 }
30 bool cmp(g a,g b)
31 {
32     if (a.l==b.l)
33         return a.id<b.id;
34     return a.l<b.l;
35 }
36 void solve(int l,int r)
37 {
38     if (l==r)
39     {
40         ans[l]=max(ans[l],1);
41         return;
42     }
43     int m=(l+r)>>1;
44     solve(l,m);
45     for (i=l;i<=r;i++)
46     {
47         if (i<=m)
48         {
49             d[i].l=v[i];
50             d[i].r=R[i];    
51         }
52         else
53         {
54             d[i].l=L[i];
55             d[i].r=v[i];
56         }
57         d[i].id=i;
58     }
59     sort(d+l,d+1+r,cmp);
60     for (i=l;i<=r;i++)
61     if (d[i].id<=m)
62         cc(d[i].r,ans[d[i].id]); 
63     else
64         ans[d[i].id]=max(ans[d[i].id],get(d[i].r)+1);
65     for (i=l;i<=r;i++)
66     if (d[i].id<=m)
67         cc(d[i].r,0);
68     solve(m+1,r);
69 }
70 int main()
71 {
72     scanf("%d%d",&n,&m);
73     for (i=1;i<=n;i++) 
74     {
75         scanf("%d",&v[i]);
76         R[i]=L[i]=v[i];
77     }
78     for (i=1;i<=m;i++)
79     {
80         scanf("%d%d",&a,&b);
81         R[a]=max(R[a],b);
82         L[a]=min(L[a],b);
83     }
84     solve(1,n); 
85     for (i=1;i<=n;i++)
86     if (ans[i]>Ans) Ans=ans[i];
87     printf("%d
",Ans);
88 }