这道题是几天前水过去的，现在快没印象了，水一发。
首先我们看到它让求解的是最长的值域 连续段长度，很好。
然后就想到了山海经，但但是我还没有做。
然后又想到了很久以前的一次考试的T3旅馆hotel（我是用暴力直接过的QAQ），正解也是线段树。
但是我还是想不到用线段树，因为我单纯的认为当前在学莫队就只会用到莫队。
后来还是问了同学。
然后就很简单了。
我们考虑询问区间的这类操作。
一种做法是各种神仙树套树解决区间问题。
另一种骗分做法就是莫队了。
不会莫队。。出门左拐（逃
那么这道题思路就可以出来了：莫队操作，每次在值域线段树这个位置的数上位置插入“1”，删除减少“1”即可，然后直接答案就是[1,n]的最长连续段长。
如果你做过类似的线段树的题，这种东西就很简单了喂。
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 const int N=5e4+5;
8 inline int read(){
9 int x=0,f=1;char ch=getchar();
10 while(ch<'0'||ch>'9') f=(ch=='-')?-1:1,ch=getchar();
11 while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
12 return x*f;
13 }
14
15 int n,m,blo;
16 int col[N],bel[N],ans[N];
17 struct node{
18 int l,r,ord;
19 inline friend bool operator<(node a,node b){
20 return (bel[a.l] ^ bel[b.l]) ? bel[a.l] < bel[b.l] : ((bel[a.l] & 1) ? a.r < b.r : a.r > b.r);
21 }
22 }q[N];
23 struct Seg_Tree{
24 #define lch k<<1
25 #define rch k<<1|1
26 struct Node{
27 int lmax,rmax,mmax;
28 int len;
29 }tr[N<<2];
30 inline void Build(int k,int l,int r){
31 tr[k].len=r-l+1;
32 if(l==r) return;
33 int mid=(l+r)>>1;
34 Build(lch,l,mid);Build(rch,mid+1,r);
35 }
36 inline void up(int k){
37 tr[k].lmax=tr[lch].lmax;
38 tr[k].rmax=tr[rch].rmax;
39 if(tr[lch].lmax==tr[lch].len) tr[k].lmax+=tr[rch].lmax;
40 if(tr[rch].rmax==tr[rch].len) tr[k].rmax+=tr[lch].rmax;
41 tr[k].mmax=max(max(tr[lch].mmax,tr[rch].mmax),tr[lch].rmax+tr[rch].lmax);
42 }
43 inline void Insert(int k,int l,int r,int x){
44 if(l==x&&r==x){
45 tr[k].lmax=1;tr[k].rmax=1;tr[k].mmax=1;
46 return;
47 }
48 int mid=(l+r)>>1;
49 if(x<=mid)Insert(lch,l,mid,x);
50 else Insert(rch,mid+1,r,x);
51 up(k);
52 }
53 inline void Erase(int k,int l,int r,int x){
54 if(l==x&&r==x){
55 tr[k].lmax=0;tr[k].rmax=0;tr[k].mmax=0;
56 return;
57 }
58 int mid=(l+r)>>1;
59 if(x<=mid)Erase(lch,l,mid,x);
60 else Erase(rch,mid+1,r,x);
61 up(k);
62 }
63 }str;
64
65 int main(){
66 n=read();
67 m=read();
68 blo=(int)sqrt(n)+1;
69 str.Build(1,1,n);
70 for(int i=1;i<=blo;++i)
71 for(int j=1;j<=blo;++j)
72 {bel[(i-1)*blo+j]=i;if((i-1)*blo+j==n) break;}
73 for(int i=1;i<=n;++i) col[i]=read();
74 for(int i=1;i<=m;++i){
75 q[i].l=read();
76 q[i].r=read();
77 q[i].ord=i;
78 }
79 sort(q+1,q+m+1);
80 register int l=q[1].l,r=q[1].r;
81 for(int i=l;i<=r;++i) str.Insert(1,1,n,col[i]);
82 for(int i=1;i<=m;++i){
83 while(r<q[i].r) str.Insert(1,1,n,col[++r]);
84 while(l>q[i].l) str.Insert(1,1,n,col[--l]);
85 while(l<q[i].l) str.Erase(1,1,n,col[l++]);
86 while(r>q[i].r) str.Erase(1,1,n,col[r--]);
87 ans[q[i].ord]=str.tr[1].mmax;
88 }
89 for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
90 return 0;
91 }
View Code