题目传送门
题意
给出一个长度为$n$的排列$P(P1,P2,...Pn)$，以及$m$个询问。每次询问某个区间$[l,r]$中，最长的值域 连续段长度。
思路
首先这道题事求连续段的长度，打个莫队先
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
inline int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
inline void Write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) Write(x/10);
putchar(x%10+'0');
return ;
}
inline void write(int x){
Write(x);
putchar('\n');
return ;
}
}
using namespace Testify;
const int N=5e4+5;
int n,m,blo,col[N],pos[N];
struct sb{
int l,r,k;
friend inline bool operator<(const sb&a,const sb&b){
if(pos[a.l]!=pos[b.l]){
return pos[a.l]<pos[b.l];
}
if(pos[a.l]&1) return pos[a.r]>pos[b.r];//奇偶性优化
return pos[a.r]<pos[b.r];
}
}q[N];
main(){
n=read(),m=read();
blo=sqrt(n);
for(register int i=1;i<=n;i++){
col[i]=read();
pos[i]=(i-1)/t+1;
}
for(register int i=1;i<=m;i++){
q[i].l=read(),q[i].r=read(),q[i].k=i;
}
int l=1,r=0;
return 0;
}
然后考虑用线段树求最长连读段长度
struct node{
int len,lmax,rmax,mmax;
}t[N<<2];
pushup操作
inline void pushup(int root){
t[root].lmax=t[lid].lmax;
t[root].rmax=t[rid].rmax;
if(t[lid].lmax==t[lid].len) {
t[root].lmax+=t[rid].lmax;
}
if(t[rid].rmax==t[rid].len){
t[root].rmax+=t[lid].rmax;
}
t[root].mmax=max({t[lid].mmax,t[rid].mmax,t[lid].rmax+t[rid].lmax});
return;
}
求解$ls$，那么我们有两个选择，选择左边区间的$ls$，或者是把左边区间全部选了然后再选取右边区间的$ls$。因为子段必须保持连续性，所以这两个选择是最优的。
同样道理求解$rs$，那么我们有两个选择，选择右边区间的$rs$，或者是把右边区间全部选了然后再选取左边区间的$rs$。因为子段必须保持连续性，所以这两个选择是最优的。
求解$ms$，那么我们有两个选择，选择右边区间的$ms$，或者是左边区间的$ ms$，或者是左边区间的$rs$和右边区间的$ls$的和，因为选择保证了连续子段的连续性，所以最优解一定在上面三种选择中。
建树
inline void build(int root,int l,int r){
t[root].len=r-l+1;
if(l==r) return;
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
}
这样写不用pushup2更新len捏
插入和删除(莫队操作)
inline void insert(int root,int l,int r,int x){
if(l==r){
t[root].lmax=1;
t[root].mmax=1;
t[root].rmax=1;
return;
}
int mid=(l+r)>>1;
if(x<=mid) insert(lid,l,mid,x);
else insert(rid,mid+1,r,x);
pushup(root);
}
inline void dele(int root,int l,int r,int x){
if(l==r){
t[root].lmax=0;
t[root].mmax=0;
t[root].rmax=0;
return;
}
int mid=(l+r)>>1;
if(x<=mid) dele(lid,l,mid,x);
else dele(rid,mid+1,r,x);
pushup(root);
}
莫队移动找答案
int l=1,r=0;
for(register int i=1;i<=m;i++){
//注意这里要先insert再dele否则会TLE(?
while(l>q[i].l) insert(1,1,n,col[--l]);
while(r<q[i].r) insert(1,1,n,col[++r]);
while(l<q[i].l) dele(1,1,n,col[l++]);
while(r>q[i].r) dele(1,1,n,col[r--]);
ans[q[i].k]=t[1].mmax;
}
或者这样写
for(register int i=l;i<=r;i++){
insert(1,1,n,col[i]);
}
for(register int i=1;i<=m;i++){
while(l>q[i].l) insert(1,1,n,col[--l]);
while(r<q[i].r) insert(1,1,n,col[++r]);
while(l<q[i].l) dele(1,1,n,col[l++]);
while(r>q[i].r) dele(1,1,n,col[r--]);
ans[q[i].k]=t[1].mmax;
}
输出
for(register int i=1;i<=m;i++){
write(ans[i]);
}