此博客停更

--->http://www.lydsy.com/JudgeOnline/problem.php?id=4358

（为了这题我还写邮件叫管理员开大时限，然而并没有什么卵用

总之这题的话$\mathcal{O}\left(n\sqrt{n}\log n\right)$的复杂度应该是很显然的，因为题目给的是一个排列所以就是一个求区间连续最长串的经典问题-。-，然后我算了一下复杂度-。-1.7亿，不，我要相信玄学---->然后我就写了0.0

，不要喷我，我一直以为应该是能过的-。-  ，为什么呢，我要来数据，然后测了一下发现要跑20s，然后我想，卡卡常数应该就行了，然后。。，父亲大人，我已经卡常数卡掉了11s，为什么还是过不了bzoj上的20s总时限？

卡完常数的代码还是放一下：

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 50050
int i,j,k,m,n,x,y,sz,c[N],a[N],d[N],l,r,ans,Ans[N],O,v;bool f;
#define max(a,b) ((a)>(b)?(a):(b))
struct node{int l,r,id;bool operator <(const node&b)const{return(c[r]<c[b.r])||(c[r]==c[b.r])&&(l<b.l);}}q[N];
struct tree{int L,R,V;bool operator ==(const tree&b)const{return L==b.L&&R==b.R&&V==b.V;};}T[N<<2],W;
#define ups(k,l,r,L,R) (W=T[k],T[L].L==r-l+2>>1?T[k].L=T[L].L+T[R].L:T[k].L=T[L].L,T[R].R==r-l+1>>1?T[k].R=T[R].R+T[L].R:T[k].R=T[R].R,T[k].V=max(max(T[L].V,T[R].V),T[L].R+T[R].L),f=W==T[k])
void add(int k,int l,int r){
	if(l==r){T[k].L=T[k].R=T[k].V=v;return;}
	int m=l+r>>1,L=k<<1,R=k<<1|1;if(x<=m)add(L,l,m);else add(R,m+1,r);if(!f)ups(k,l,r,L,R);
}
int main(){
	for(n=read(),m=read(),sz=sqrt(n),i=1;i<=n;++i)a[i]=read();
	for(i=1;i<=n;++i)c[i]=i/300;
	for(i=1;i<=m;++i)q[i].l=read(),q[i].r=read(),q[i].id=i;
	for(sort(q+1,q+m+1),i=q[1].l;i<=q[1].r;++i)f=0,x=a[i],v=1,add(1,1,n);
	for(Ans[q[1].id]=T[1].V,l=q[1].l,r=q[1].r,i=2;i<=m;++i){
		while(r<q[i].r)f=0,x=a[++r],v=1,add(1,1,n);
		while(l>q[i].l)f=0,x=a[--l],v=1,add(1,1,n);
		while(r>q[i].r)f=0,x=a[r--],v=0,add(1,1,n);
		while(l<q[i].l)f=0,x=a[l++],v=0,add(1,1,n);
		Ans[q[i].id]=T[1].V;
	}
	for(i=1;i<=m;++i)printf("%d\n",Ans[i]);
}

然后有句话叫做经典的log做法问题都有$\mathcal{O}\left(1\right)$的解法-。-||| 

如果只考虑不删数的情况，每加入一个数可以直接用并查集维护-。-，然后想想莫队分块的方法，对于左端点在同一个块的询问，右端点是从小到大排的，于是对于左端点那块后面的数就可以只加入不删除，然后考虑左端点所属的那块，发现暴力就可以啦~，具体可见代码

$\mathcal{O}\left(n\sqrt{n}\right)$:

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 50050
int i,j,k,m,n,sz=300,x,a[N],c[N],fa[N],s[N],last,cnt,o,loc,L,R,rk[N],v[N],ans,Ans[N];
#define min(a,b) ((a)<(b)?(a):(b))
struct node{int l,r,id;bool operator <(const node&b)const{return(c[l]<c[b.l])||(c[l]==c[b.l])&&(r<b.r);}}q[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int l,int r){l=find(l),r=find(r),fa[r]=l,s[l]+=s[r];}
inline void Mx(int&a,int b){if(b>a)a=b;}
int main(){
	for(n=read(),m=read(),i=1;i<=n;++i)a[i]=read();
	for(i=1;i<=m;++i)q[i].l=read(),q[i].r=read(),q[i].id=i;
	for(i=1;i<=n;++i)c[i]=i/sz;
	for(sort(q+1,q+m+1),o=-1,i=1;i<=m;++i){
		if(c[q[i].l]!=o){
			for(j=1;j<=n;++j)fa[j]=s[j]=0;
			L=c[q[i].l]*sz+1,R=min(n,(c[q[i].l]+1)*sz);
			for(j=L;j<=R;++j)v[a[j]]=j,rk[j]=a[j];
			loc=R+1,sort(rk+L,rk+R+1),ans=0;
		}cnt=0,last=-1;
		if(q[i].r<=R){
			for(j=L;j<=R;++j){
				k=rk[j];
				if(v[k]>=q[i].l&&v[k]<=q[i].r)cnt=1+(last==k-1?cnt:0),Mx(Ans[q[i].id],cnt),last=k;
			}
			o=c[q[i].l];continue;
		}
		while(loc<=q[i].r){
			k=a[loc++],fa[k]=k,s[k]=1;
			if(find(k+1))merge(k,k+1);
			if(find(k-1))merge(k,k-1);
			Mx(ans,s[find(k)]);
		}Ans[q[i].id]=ans;
		for(j=L;j<=R;++j){
			k=rk[j];
			if(v[k]>=q[i].l){
				if(find(k-1))cnt=find(last+1)==fa[k-1]?cnt+1:s[fa[k-1]]+1;
				else if(last==k-1)++cnt;else cnt=1;
				if(find(k+1))cnt+=s[fa[k+1]];last=k;
				Mx(Ans[q[i].id],cnt);
			}
		}
		o=c[q[i].l];
	}
	for(i=1;i<=m;++i)printf("%d\n",Ans[i]);
}

另外有一个复杂度和我一样的但是常数比我小的多的写法@比利

loading...