BZOJ 4358 坑 莫队+线段树 死T

这是一个坑
竟然卡nsqrt(n)logn

T死 等更

//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define Max(x,y) x>y?x:y;
const int N=50050,T=50050*8;
int n,m,Block,a[N],block[N],sum[T],lmax[T],rmax[T],maxx[T],num[T];
struct Ask{int l,r,id,ans;}ask[N];
bool cmp(Ask a,Ask b){
    if(block[a.l]!=block[b.l])return a.r<b.r;
    return a.l<b.l;
}
bool cmpid(Ask a,Ask b){return a.id<b.id;}
void insert(int l,int r,int pos,int num,int wei){
    if(l==r){
        sum[pos]+=wei;
        if(sum[pos])sum[pos]=lmax[pos]=rmax[pos]=maxx[pos]=1;
        else sum[pos]=-40000,lmax[pos]=rmax[pos]=maxx[pos]=0;
        return;
    }
    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
    if(mid<num)insert(mid+1,r,rson,num,wei);
    else insert(l,mid,lson,num,wei);
    sum[pos]=sum[lson]+sum[rson];
    lmax[pos]=Max(lmax[lson],sum[lson]+lmax[rson]);
    rmax[pos]=Max(rmax[rson],sum[rson]+rmax[lson]);
    maxx[pos]=Max(maxx[lson],maxx[rson]);
    maxx[pos]=Max(lmax[rson]+rmax[lson],maxx[pos]);
}
inline int read(){
    char p=getchar();int x=0;
    while(p<'0'||p>'9')p=getchar();
    while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();
    return x;
}
int main(){
    for(int i=1;i<T;i++)sum[i]=-40000;
    n=read(),m=read();
    for(int i=1;i<=n;i++)*(a+i)=read();
    for(int i=1;i<=m;i++)ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
    Block=sqrt(n);
    for(int i=1;i<=n;i++)block[i]=(i-1)/Block+1;
    sort(ask+1,ask+1+m,cmp);
    for(int i=1,l=1,r=0;i<=m;i++){
        for(;l<ask[i].l;l++)insert(1,n,1,a[l],-1);
        for(;l>ask[i].l;l--)insert(1,n,1,a[l-1],1);
        for(;r<ask[i].r;r++)insert(1,n,1,a[r+1],1);
        for(;r>ask[i].r;r--)insert(1,n,1,a[r],-1);
        ask[i].ans=maxx[1];
    }
    sort(ask+1,ask+1+m,cmpid);
    for(int i=1;i<=m;i++)printf("%d
",ask[i].ans);
}

2017.4.27 Update

//By SiriusRen
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=50050;
int n,m,col[N],Block,block[N],L[N],R[N],Ans[N],ans,ls[N],rs[N];
int stk1[N],stk2[N],rec1[N],rec2[N];
struct Node{int l,r,id;}node[N];
bool cmp(Node a,Node b){
    if(block[a.l]!=block[b.l])return a.l<b.l;
    return a.r<b.r;
}
int main(){
    scanf("%d%d",&n,&m);Block=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&col[i]),block[i]=(i-1)/Block+1;
    for(int i=1;i<=m;i++)scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i;
    for(int i=1;i<=n;i++)R[block[i]]=i;
    for(int i=n;i;i--)L[block[i]]=i;
    sort(node+1,node+1+m,cmp);
    for(int i=1,l,r;i<=m;i++){
        if(block[node[i].l]!=block[node[i-1].l]){
            memset(ls,0,sizeof(ls));
            memset(rs,0,sizeof(rs));
            l=r=R[block[node[i].l]],ans=0;
        }
        while(r<node[i].r){
            r++;
            ls[col[r]]=ls[col[r]-1]+1,rs[col[r]]=rs[col[r]+1]+1;
            int t=rs[col[r]]+ls[col[r]]-1;
            rs[col[r]-ls[col[r]]+1]=t,ls[col[r]+rs[col[r]]-1]=t;
            ans=max(ans,t);
        }int temp=ans,top=0;
        for(int j=node[i].l;j<=min(node[i].r,l);j++){
            ls[col[j]]=ls[col[j]-1]+1,rs[col[j]]=rs[col[j]+1]+1;
            int t=rs[col[j]]+ls[col[j]]-1;
            int tx=col[j]-ls[col[j]]+1,ty=col[j]+rs[col[j]]-1;
            stk1[++top]=tx,rec1[top]=rs[tx];
            stk2[top]=ty,rec2[top]=ls[ty];
            rs[tx]=t,ls[ty]=t,temp=max(temp,t);
        }Ans[node[i].id]=temp;
        for(int j=top;j;j--)
            rs[stk1[j]]=rec1[j],ls[stk2[j]]=rec2[j];
        for(int j=node[i].l;j<=min(node[i].r,l);j++)ls[col[j]]=rs[col[j]]=0;
    }
    for(int i=1;i<=m;i++)printf("%d
",Ans[i]);
}