【BZOJ4358】permu
Description
给出一个长度为n的排列P(P1,P2,...Pn)，以及m个询问。每次询问某个区间[l,r]中，最长的值域连续段长度。
Input
第一行两个整数n,m。
接下来一行n个整数，描述P。
接下来m行，每行两个整数l,r，描述一组询问。
Output
对于每组询问，输出一行一个整数，描述答案。
Sample Input
8 3
3 1 7 2 5 8 6 4
1 4
5 8
1 7
3 1 7 2 5 8 6 4
1 4
5 8
1 7
Sample Output
3
3
4
3
4
HINT
对于询问[1,4]，P2,P4,P1组成最长的值域连续段[1,3]；
对于询问[5,8]，P8,P5,P7组成最长的值域连续段[4,6]；
对于询问[1,7]，P5,P7,P3,P6组成最长的值域连续段[5,8]。
1<=n,m<=50000
题解：一开始想莫队没想出来，然后就去膜拜了Claris的题解。
然后下传标记的时候又有些不明白，于是又去膜拜了Claris的代码。。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=50010;
const int inf=1<<30;
int n,m,X,rt,D;
int p[maxn],v[maxn],ans[maxn];
struct kd
{
int v[2],sm[2],sn[2],ls,rs,ts,val,tt,org,ht,hs,hv;
kd () {}
kd (int a,int b){v[0]=sm[0]=sn[0]=a,v[1]=sm[1]=sn[1]=b,ls=rs=ts=val=hs=hv=0,tt=ht=-inf;}
}t[maxn];
bool cmp(const kd &a,const kd &b)
{
return (a.v[D]==b.v[D])?(a.v[D^1]<b.v[D^1]):(a.v[D]<b.v[D]);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void ps(int x,int y)
{
t[x].val+=y;
if(t[x].val>t[x].hv) t[x].hv=t[x].val;
if(t[x].tt>=0)
{
t[x].tt+=y;
if(t[x].tt>t[x].ht) t[x].ht=t[x].tt;
}
else
{
t[x].ts+=y;
if(t[x].ts>t[x].hs) t[x].hs=t[x].ts;
}
}
void pt(int x,int y)
{
t[x].val=y;
if(t[x].val>t[x].hv) t[x].hv=t[x].val;
t[x].tt=y,t[x].ts=0;
if(t[x].tt>t[x].ht) t[x].ht=t[x].tt;
}
void phs(int x,int y)
{
t[x].hv=max(t[x].hv,t[x].val+y);
if(t[x].ht>=0) t[x].ht=max(t[x].ht,t[x].tt+y);
else t[x].hs=max(t[x].hs,t[x].ts+y);
}
void pht(int x,int y)
{
t[x].hv=max(t[x].hv,y);
t[x].ht=max(t[x].ht,y);
}
void pushup(int x,int y)
{
t[x].sm[0]=max(t[x].sm[0],t[y].sm[0]);
t[x].sm[1]=max(t[x].sm[1],t[y].sm[1]);
t[x].sn[0]=min(t[x].sn[0],t[y].sn[0]);
t[x].sn[1]=min(t[x].sn[1],t[y].sn[1]);
}
void pushdown(int x)
{
if(t[x].hs)
{
if(t[x].ls) phs(t[x].ls,t[x].hs);
if(t[x].rs) phs(t[x].rs,t[x].hs);
t[x].hs=0;
}
if(t[x].ht>=0)
{
if(t[x].ls) pht(t[x].ls,t[x].ht);
if(t[x].rs) pht(t[x].rs,t[x].ht);
t[x].ht=-inf;
}
if(t[x].ts)
{
if(t[x].ls) ps(t[x].ls,t[x].ts);
if(t[x].rs) ps(t[x].rs,t[x].ts);
t[x].ts=0;
}
if(t[x].tt>=0)
{
if(t[x].ls) pt(t[x].ls,t[x].tt);
if(t[x].rs) pt(t[x].rs,t[x].tt);
t[x].tt=-inf;
}
}
int build(int l,int r,int d)
{
if(l>r) return 0;
int mid=(l+r)>>1;
D=d,nth_element(t+l,t+mid,t+r+1,cmp);
t[mid].ls=build(l,mid-1,d^1),t[mid].rs=build(mid+1,r,d^1);
if(t[mid].ls) pushup(mid,t[mid].ls);
if(t[mid].rs) pushup(mid,t[mid].rs);
return mid;
}
void updata(int x)
{
if(!x) return;
if(t[x].sn[0]>X||t[x].sm[1]<X)
{
pt(x,0);
return ;
}
if(t[x].sm[0]<=X&&t[x].sn[1]>=X)
{
ps(x,1);
return ;
}
pushdown(x);
if(t[x].v[0]<=X&&t[x].v[1]>=X) t[x].val++,t[x].hv=max(t[x].hv,t[x].val);
else t[x].val=0;
updata(t[x].ls),updata(t[x].rs);
}
void dfs(int x)
{
if(!x) return ;
pushdown(x),ans[t[x].org]=t[x].hv;
dfs(t[x].ls),dfs(t[x].rs);
}
int main()
{
n=rd(),m=rd();
int i,a,b;
for(i=1;i<=n;i++) p[rd()]=i;
for(i=1;i<=m;i++) a=rd(),b=rd(),t[i]=kd(a,b),t[i].org=i;
rt=build(1,m,0);
for(i=1;i<=n;i++)
X=p[i],updata(rt);
dfs(rt);
for(i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}