2019/5/27 day9 解题日志

2019-05-27

字数统计: 785字 | 阅读时长: 3分

题目链接

给定一个序列A，问最大的长度len，使得A[l..l+len-1]经过排序后是公差为1的等差数列。

day9

思路O(nlogn)

用双指针维护当前指向的$l$和$r$。
由于要使得公差为$1$，那么当$A_r$与$A[l..r-1]$当中某个值冲突，说明要保存$r$的前提是$l$要进行移动。这个过程显然是$O(n)$的。
现在的问题是，如何判断当前双指针维护的区间内对答案的贡献呢？
不妨定义这样的线段树：
- $lv[rt]$维护当前区间$[l..r]$里，从$l$开始的最长连续等差数列长度；
- $rv[rt]$维护当前区间$[l..r]$里，到$r$结束的最长连续等差数列长度；
- $mv[rt]$维护当前区间$[l..r]$里，最长连续等差数列长度。
其实到这里问题就解决了，对于查询，只需要查$mv[1]$的值便可（$1$维护$[1..n]$）。
那么$update$操作只需要递归到叶子节点，然后把$lv[rt]=rv[rt]=mv[rt]$置为1或者0便可，这个区间长度只有1。
然后push_up操作稍微复杂点：
- 对于lv[rt]，如果左儿子的lv值已经覆盖整个区间，那么lv[rt]可以拓展到右儿子。
- 同理rv[rt]。
- mv[rt]其实就是两个儿子的mv值取最大，然后再计算左儿子的rv和右儿子的lv拼接，取最大值便可。
整体时间复杂度是$O(nlogn)$，但在poj上并没有通过，个人认为是时限给的不好，标算是$O(nlogn)$的。但是这题有$O(n)$的做法。

代码

没有AC，不保证正确性，但思路肯定没问题。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define intmid int mid=l+r>>1
int lv[maxn<<2],rv[maxn<<2],mv[maxn<<2];
int n,a[maxn],last[maxn];
void push_up(int l,int r,int rt){
    intmid;
    if(lv[rt<<1]==mid-l+1)lv[rt]=lv[rt<<1]+lv[rt<<1|1];
    else lv[rt]=lv[rt<<1];
    if(rv[rt<<1|1]==r-mid)rv[rt]=rv[rt<<1|1]+rv[rt<<1];
    else rv[rt]=rv[rt<<1|1];
    mv[rt]=max(mv[rt<<1],mv[rt<<1|1]);
    mv[rt]=max(mv[rt],rv[rt<<1]+lv[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        lv[rt]=rv[rt]=mv[rt]=0;return;
    }intmid;
    build(lson);build(rson);push_up(l,r,rt);
}
void update(int p,int v,int l,int r,int rt){
    if(p<1||p>n)return;
    if(l==r){
        lv[rt]=rv[rt]=mv[rt]=v;return;
    }intmid;
    if(p<=mid)update(p,v,lson);
    else update(p,v,rson);
    push_up(l,r,rt);
}
int main(){
    int T;read(T);
    while(T--){
        read(n);
        for(int i=0;i<=n;i++)last[i]=0;
        build(1,n,1);
        int posl=1,ans=0;
        for(int i=1;i<=n;i++){
            read(a[i]);
            if(last[a[i]]>=posl){
                while(last[a[i]]>=posl){
                    update(a[posl],0,1,n,1);posl++;
                }
            }
            update(a[i],1,1,n,1);
            last[a[i]]=i;
            ans=max(ans,mv[1]);
        }
        print(ans,'\n');
    }
    return 0;
}