10121. 「一本通 4.2 例 3」与众不同

题意

定义完美序列:一段连续的序列满足序列中的数互不相同。 想知道区间 $[L,R]$ 之间最长的完美序列长度。

思路

设$las[x]$表示盈利$x$最近出现位置。 设$st[i]$表示以第$i$个数结尾的最长完美序列的起始位置。
$$st[i]=max(st[i-1],las[a[i]]+1)$$
设$f[i]$表示以第$i$个数结尾的最长完美序列的长度
$$f[i]=i-st[i]+1$$
由$st$的递推式可知,$st$的值是一个非递减的序列。 对于一个询问区间$[l_i,r_i]$,该区间内的$st$值可能会有两种情况:
  • 左边一部分的$st$值不在区间内,即$<l_i$
  • 右边一部分的$st$值不在区间内,即$\ge l_i$
由于$st$的值具有单调性,所以这个边界可以通过二分得到。设求出的边界为$mid$_i,可得:
$$st[l_i…mid_i-1]<l_i$$ $$st[mid_i…r_i]\ge l_i$$ 那么整个区间$[l_i,r_i]$的最长完美序列的长度可以分两部分来求。
  • 左边:很显然为$mid_i-l_i$
  • 右边:$MAX(m_i…r_i)$
所以右边的长度要使用ST表,即RMQ来求。 整个问题的时间复杂度:
$$O((M+N) \times logN)$$
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
const int N=2e5+5,M=1e6;
using namespace std;
inline ll read(){
    char ch=getchar();ll res=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(ll zx){
    if(zx<0) zx=-zx,putchar('-');
    if(zx<10) putchar(zx+'0');
    else{
        write(zx/10);
        putchar(zx%10+'0');
    }
}
ll n,m,f[N][20],st[N],las[M<<1];
void ST(){
    for(ll j=1;(1<<j)<=n;j++){
        for(ll i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
ll RMQ(ll l,ll r){
    ll k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
ll find(ll l,ll r){
    if(st[l]==l) return l;
    if(st[r]<l) return r+1;
    int L=l,R=r;
    while(L<=R){
        int m=L+R>>1;
        if(st[m]<l) L=m+1;
        else R=m-1;
    }
    return L;
}
int main(){
    n=read();m=read();
    for(ll i=1;i<=n;i++){
        int x=read();
        st[i]=max(st[i-1],las[x+M]+1);
        f[i][0]=i-st[i]+1;
        las[x+M]=i;
    }
    ST();
    for(ll i=1;i<=m;i++){
        ll L,R;
        L=read();R=read();L++;R++;
        ll mid=find(L,R),ans=0,tmp;
        if(mid>L) ans=mid-L;
        if(mid<=R){
            tmp=RMQ(mid,R);
            ans=max(ans,tmp);
        }
        write(ans);putchar('\n');
    }
    return 0;
}

评论

  1. yzx1798106406 博主
    2年前
    2019-8-15 7:33:35

    fixed

  2. none
    2年前
    2019-8-10 14:14:17

    st[i]=max(st[i−1],las[a[i]+1]) 应为 st[i] = max(st[i – 1], las[a[i]] + 1)

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇