BZOJ 2342 [Shoi2011]双倍回文（manacher+堆+set）

题意

N<=500000

 

题解

维护一个set可以用堆来解决。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int N=500100;
int str[N*2],m,p[N*2];
int n,f[N],now,ans;
char s[N];
struct hhh{
    int l,r;
    bool operator <(const hhh &a)const{
        return a.r<r;
    }
}c[N];
set<int> se;
priority_queue<hhh> q;
void init(){
    str[0]=str[1]='#';
    for(int i=1;i<=n;i++){
        str[i*2]=s[i];
        str[i*2+1]='#';
    }
    m=n*2+1;
}
void manacher(){
    int mx=0,id;
    for(int i=1;i<=m;i++){
        if(mx>i)p[i]=min(p[id-(i-id)],id+p[id]-i);
        else p[i]=1;
        while(str[i-p[i]]==str[i+p[i]])p[i]++;
        if(i+p[i]-1>mx)mx=i+p[i]-1,id=i;
    }
}
int main(){
    scanf("%d",&n);
    scanf("%s",s+1);
    init();
    manacher();
    for(int i=1;i<=n;i++){
        f[i]=p[i*2+1]/2;
        c[i].l=i;
        c[i].r=i+f[i];
    }
    for(int i=1;i<=n;i++){
        if(i-1+f[i-1]>=i){
            se.insert(i-1);
            q.push(c[i-1]);
        }
        while(!q.empty()&&q.top().r<i){
            se.erase(q.top().l);
            q.pop();
        }
        set<int>::iterator it=se.lower_bound(i-f[i]/2);
        if(it!=se.end()){
            ans=max(ans,(i-*it)*4);
        }
    }
    printf("%d",ans);
    return 0;
}