【2016/4/28 考题】seq 莫队+链表思想
题意：给出一个长度为 n 的排列 P，以及 m 个询问。 每次询问某个区间[l,r]中，最长的值域连续段长度。(n,m <= 50000)
(注意不要求下标连续 ， 例如 3 1 7 2 的最长值域连续段为 1,2,3)
首先这道题给了一个警示，就是一定要确定理解了题意再开始思考做法，并且要看一看样例和自己想的是否一样。不然结果会很惨。
一眼看来，这道题就是一个裸的莫队+可撤销并查集。
这种莫队的写法与平时的莫队不同。大概是这样的，开始是同样地将询问按照左端点所在块分别处理，块内询问按照右端点排序。不同的是，我们每次只加入这个块以右的点，处理每个询问时，先加入这个块内的点，再撤销加入。
对于每一块的询问，块以右的每个点最多加入一次；对于 m 次查询，每次查询最多加入和撤销加入根号个点。于是复杂度也正确。
但是，用可撤销的并查集会多一个log，测试时 TLE 了两个点。
再考虑这道题的性质，我们用并查集是将代表值域的点连起来，这也就是说，每次连通两个值域只有可能是在原本这两个值域的边界处连通。于是我们只用对每个边界存下其对应的另一个边界在哪里即可，加入和撤销均为 O(1)。
#include<iostream>
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define my_min(a,b) ((a)<(b)?(a):(b))
#define my_max(a,b) ((a)>(b)?(a):(b))
using namespace std;
struct questions{
int l,r,xh;
questions(int _xh=0,int _l=0,int _r=0){ xh=_xh , l=_l , r=_r ; }
}qs[50005],que[50005];
bool cmp_r(const questions &a,const questions &b){
if(a.r==b.r)return a.l<b.l ;
return a.r<b.r ;
}
int b_size , now_ans , qnum , stk[50005] , top , n , m , P[50005] ;
int ans[50005] , bl[50005] , br[50005] ;
bool has[50005] ;
void restore(){
while(top){
int t=stk[top] ;
if(t!=1&&has[t-1])br[bl[t-1]]=t-1 ;
if(t!=n&&has[t+1])bl[br[t+1]]=t+1 ;
has[t]=false , top-- ;
}
}
void get_it(int t,bool f){
int ll=t,rr=t ;
if(t!=1&&has[t-1])ll=bl[t-1] ;
if(t!=n&&has[t+1])rr=br[t+1] ;
now_ans=my_max(now_ans,rr-ll+1) ;
br[ll]=rr , bl[rr]=ll , has[t]=true ;
if(f)stk[++top]=t ;
}
void solve(){
b_size=(int)(sqrt(n)+1e-8) ;
for(int i=1;i<=n;i+=b_size){
now_ans=1 , qnum=0 ;
for(int j=1;j<=m;++j) if(qs[j].l>=i && qs[j].l<=my_min(n,i+b_size-1))que[++qnum]=qs[j];
if(!qnum)continue ;
for(int j=1;j<=n;++j)has[j]=false , bl[j]=br[j]=j ;
sort(que+1,que+qnum+1,cmp_r) ;
int now_r=my_min(n,i+b_size-1) ;
for(int j=1;j<=qnum;++j){
while(now_r<que[j].r){
int t=P[++now_r] ;
get_it(t,false) ;
}
int t_ans=now_ans ;
for(int k=my_min(my_min(n,i+b_size-1),que[j].r);k>=que[j].l;--k){
int t=P[k] ;
get_it(t,true) ;
}
ans[que[j].xh]=now_ans , restore() ;
for(int k=my_min(my_min(n,i+b_size-1),que[j].r);k>=que[j].l;--k){ has[P[k]]=false ; }
now_ans=t_ans ;
}
}
for(int i=1;i<=m;++i) printf("%d\n",ans[i]) ;
}
int main()
{
freopen("seq.in","r",stdin) ;
freopen("seq.out","w",stdout) ;
scanf("%d%d",&n,&m) ;
for(int i=1;i<=n;++i)scanf("%d",&P[i]) ;
for(int i=1;i<=m;++i){
scanf("%d%d",&qs[i].l,&qs[i].r) ;
qs[i].xh=i ;
}
solve() ;
//fprintf(stderr,"%d\n",clock()) ;
return 0 ;
}
评论