UVA - 1471 Defense Lines (set/bit/lis)

你的名字 2021-09-30 04:42 185阅读 0赞

紫薯例题+1。

题意：给你一个长度为n(n<=200000)的序列a\[n\]，求删除一个连续子序列后的可能的最长连续上升子序列的长度。

首先对序列进行分段，每一段连续的子序列的元素递增，设L\[i\]为下标i对应的元素向左能延伸到的最大长度(在同一段内)，R\[i\]为向右能延伸到的最大长度，则问题转化成了对于每个下标i，找到在它前面的下标j中a\[j\]<a\[i\]且L\[j\]最大的j，然后用R\[i\]+L\[j\]去更新ans。

第一种方法是用一个二元组(x,y)表示大小为x的元素所对应的L的值，用一个set保存所有这样的二元组，则任意两个二元组不存在包含关系，即满足x递增且y也递增。于是对原序列从左往右扫一遍，每扫到一个元素，就可以从set中二分找到最大的x使得a\[i\]>x，用R\[i\]+y去更新ans即可。然后向set中插入(a\[i\],L\[i\])，并根据set中左右两边的二元组的值来确定是否需要保留它，并清掉一些无用的二元组。

这里用到了一点小技巧，就是向set中插入两个虚的元素作为左右边界，这样就不用特判了，方便了很多。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 
     3 using namespace std;
     4 typedef long long ll;
     5 const int N=2e5+10,inf=0x3f3f3f3f;
     6 int a[N],L[N],R[N],n,ans;
     7 struct nd {
     8     int x,y;
     9     bool operator<(const nd& b)const {
         return x!=b.x?x<b.x:y<b.y;}
    10 };
    11 set<nd> st;
    12 
    13 int main() {
    14     int T;
    15     for(scanf("%d",&T); T--;) {
    16         st.clear();
    17         st.insert({
         0,0});
    18         st.insert({inf,inf});
    19         ans=0;
    20         scanf("%d",&n);
    21         for(int i=0; i<n; ++i)scanf("%d",&a[i]);
    22         for(int l=0,r; l<n; l=r) {
    23             for(r=l+1; r<n&&a[r]>a[r-1]; ++r);
    24             for(int j=l; j<r; ++j)L[j]=j-l+1,R[j]=r-j;
    25         }
    26         for(int i=0; i<n; ++i) {
    27             set<nd>::iterator it,it2;
    28             it=st.lower_bound({a[i],-1}),it--;
    29             ans=max(ans,it->y+R[i]);
    30             st.insert({a[i],L[i]});
    31             it=st.find({a[i],L[i]});
    32             while(1) {
    33                 it2=it,it2++;
    34                 if(it2->y<=it->y)st.erase(it2);
    35                 else break;
    36             }
    37             it2=it,it2--;
    38             if(it2->y>=it->y)st.erase(it);
    39         }
    40         printf("%d\n",ans);
    41     }
    42     return 0;
    43 }

第二种方法是每扫到一个i，直接查询a\[j\]<a\[i\]的元素中最大的L，怎么查呢？用树状数组(BIT)呗！树状数组不仅能动态维护前缀和，还能动态维护所有小于k的元素中的最大值哦！（当然，前提是没有将元素减小的操作）将原序列离散化后的值作为下标插入BIT中就行了，注意下标要从1开始。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 
     3 using namespace std;
     4 typedef long long ll;
     5 const int N=2e5+10,inf=0x3f3f3f3f;
     6 int a[N],b[N],c[N],L[N],R[N],n,nn,ans;
     7 int lowbit(int x) {
         return x&-x;}
     8 void add(int u,int x) {
         for(; u<=nn; u+=lowbit(u))c[u]=max(c[u],x);}
     9 int get(int u) {
         int ret=0; for(; u; u-=lowbit(u))ret=max(ret,c[u]); return ret;}
    10 
    11 int main() {
    12     int T;
    13     for(scanf("%d",&T); T--;) {
    14         ans=0;
    15         scanf("%d",&n);
    16         for(int i=0; i<n; ++i)scanf("%d",&a[i]),b[i]=a[i];
    17         sort(b,b+n);
    18         nn=unique(b,b+n)-b;
    19         for(int i=0; i<n; ++i)a[i]=lower_bound(b,b+nn,a[i])-b+1;
    20         for(int l=0,r; l<n; l=r) {
    21             for(r=l+1; r<n&&a[r]>a[r-1]; ++r);
    22             for(int j=l; j<r; ++j)L[j]=j-l+1,R[j]=r-j;
    23         }
    24         memset(c,0,sizeof c);
    25         for(int i=0; i<n; ++i) {
    26             ans=max(ans,R[i]+get(a[i]-1));
    27             add(a[i],L[i]);
    28         }
    29         printf("%d\n",ans);
    30     }
    31     return 0;
    32 }

第三种方法是最简洁最高效但也是最抽象的一种方法，就是仿照求LIS的算法，维护一个单调的数组c，记录所有L值为i的元素中最小的a\[i\]（和BIT正好相反），每扫到一个元素a\[i\]，在c中通过二分查找到比a\[i\]小的最大的元素，它的下标值就是最大的L，然后令c\[L\[i\]\]=min(c\[L\[i\]\],a\[i\])即可。其实这种方法和方法一原理是相同的，由于这道题比较特殊——L值是连续的！因为假设出现了某个L值，则L-1一定要出现在它前面，以此类推，因此不会出现下标空缺的现象，完全可以用数组来代替set。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 
     3 using namespace std;
     4 typedef long long ll;
     5 const int N=2e5+10,inf=0x3f3f3f3f;
     6 int a[N],c[N],L[N],R[N],n,ans;
     7 
     8 int main() {
     9     int T;
    10     for(scanf("%d",&T); T--;) {
    11         ans=0;
    12         scanf("%d",&n);
    13         for(int i=0; i<n; ++i)scanf("%d",&a[i]);
    14         for(int l=0,r; l<n; l=r) {
    15             for(r=l+1; r<n&&a[r]>a[r-1]; ++r);
    16             for(int j=l; j<r; ++j)L[j]=j-l+1,R[j]=r-j;
    17         }
    18         memset(c,inf,sizeof c);
    19         c[0]=0;
    20         for(int i=0; i<n; ++i) {
    21             ans=max(ans,int(R[i]+lower_bound(c,c+n,a[i])-c-1));
    22             c[L[i]]=min(c[L[i]],a[i]);
    23         }
    24         printf("%d\n",ans);
    25     }
    26     return 0;
    27 }

虽然这种题已经做过n遍了，但做完之后还是有很大的感悟，里面蕴含的思想真的不容小觑啊。

转载于:https://www.cnblogs.com/asdfsag/p/10358561.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/c85c566b8804457684aa9f94b5ae45fb.png