与众不同

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2467 字
线段树最长互异子段
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1543
// 题意：N 个月盈利值、M 次询问；每次问区间[L,R]内最长"完美序列"(连续互异)长度。
// 思路：预处理 running start[i]=以 i 结尾最长互异段起点、f[i]=其长度；两棵线段树分别求被 L 截断的两种贡献取最大。
// 复杂度：O(N log N + M log^2 N) 时间 / O(N log N) 空间
// 易错点：下标 0-based；当 start[i]<L 时该点有效长度受窗口左端 L 限制。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200005;
int a[MAXN], left_[MAXN], f[MAXN];
vector<pair<int,int>> nodeA[4*MAXN];
vector<int> smaxA[4*MAXN];
int minL[4*MAXN];
void buildA(int id,int l,int r){
    if(l==r){
        nodeA[id].push_back({left_[l],f[l]});
        smaxA[id].push_back(f[l]);
        return;
    }
    int mid=(l+r)/2;
    buildA(id*2,l,mid);
    buildA(id*2+1,mid+1,r);
    auto &L=nodeA[id*2], &R=nodeA[id*2+1];
    int i=0,j=0;
    while(i<(int)L.size()||j<(int)R.size()){
        pair<int,int> cur;
        if(j==(int)R.size()||(i<(int)L.size()&&L[i].first<=R[j].first))cur=L[i++];
        else cur=R[j++];
        nodeA[id].push_back(cur);
    }
    int m=nodeA[id].size();
    smaxA[id].assign(m,0);
    for(int k=m-1;k>=0;k--)
        smaxA[id][k]=max(nodeA[id][k].second,(k+1<m?smaxA[id][k+1]:0));
}
int queryA(int id,int l,int r,int ql,int qr,int L0){
    if(ql>r||qr<l)return 0;
    if(ql<=l&&r<=qr){
        auto &v=nodeA[id];
        int lo=lower_bound(v.begin(),v.end(),make_pair(L0,0))-v.begin();
        if(lo>=(int)v.size())return 0;
        return smaxA[id][lo];
    }
    int mid=(l+r)/2;
    return max(queryA(id*2,l,mid,ql,qr,L0),queryA(id*2+1,mid+1,r,ql,qr,L0));
}
void buildB(int id,int l,int r){
    if(l==r){minL[id]=left_[l];return;}
    int mid=(l+r)/2;
    buildB(id*2,l,mid);
    buildB(id*2+1,mid+1,r);
    minL[id]=min(minL[id*2],minL[id*2+1]);
}
int findRight(int id,int l,int r,int ql,int qr,int L0){
    if(ql>r||qr<l||minL[id]>=L0)return -1;
    if(l==r)return l;
    int mid=(l+r)/2;
    int res=findRight(id*2+1,mid+1,r,ql,qr,L0);
    if(res!=-1)return res;
    return findRight(id*2,l,mid,ql,qr,L0);
}
int main(){
    int N,M;
    if(!(cin>>N>>M))return 0;
    map<int,int> last;
    int start=0;
    for(int i=0;i<N;i++){
        cin>>a[i];
        if(last.count(a[i]))start=max(start,last[a[i]]+1);
        left_[i]=start;
        f[i]=i-start+1;
        last[a[i]]=i;
    }
    buildA(1,0,N-1);
    buildB(1,0,N-1);
    while(M--){
        int L,R;cin>>L>>R;
        int p1=queryA(1,0,N-1,L,R,L);
        int idx=findRight(1,0,N-1,L,R,L);
        int p2=(idx!=-1)?(idx-L+1):0;
        cout<<max(p1,p2)<<"\n";
    }
    return 0;
}
与众不同

正文

一本通·提高篇的其它内容
