bzoj4358 perm

给出一个长度为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

Sample Output

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

Source

每一个点记录两个信息：f[i][j]表示i的子树中深度为j的节点的个数。

g[i][j]表示满足d[a]-2*d[lca(a,b)]=d[b]-2*d[lca(a,b)]的二元点对(a,b)的个数。

从下向上启示式合并，每次将轻儿子的信息合并到重儿子上。总的时间复杂度为O(nlogn)。在合并的过程中同一时候计算出答案。

#include<iostream> #include<cstdio> #include<cstring> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define pa pair<int,int> #define maxn 50005 #define inf 1000000000 using namespace std; int n,m,block,l,r,mx; int a[maxn],pos[maxn],pl[maxn],pr[maxn],ans[maxn]; bool vst[maxn]; stack<pa> st; struct data{int l,r,id;}b[maxn]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline bool cmp(data x,data y) { return pos[x.l]==pos[y.l]?x.r<y.r:x.l<y.l; } inline bool cmp_id(data x,data y) { return x.id<y.id; } inline void add(int x,int flg) { vst[x]=true; int tl=x,tr=x; if (vst[x-1]) tl=pl[x-1]; if (vst[x+1]) tr=pr[x+1]; if (flg) { st.push(make_pair(tl,pr[tl])); st.push(make_pair(tr,pl[tr])); } pr[tl]=tr;pl[tr]=tl; mx=max(mx,tr-tl+1); } inline int query(int l,int r) { memset(vst,false,sizeof(vst)); memset(pl,0,sizeof(pl)); memset(pr,0,sizeof(pr)); mx=0; F(i,l,r) add(a[i],0); return mx; } int main() { n=read();m=read(); block=int(sqrt(n)); F(i,1,n) a[i]=read(); F(i,1,n) pos[i]=(i-1)/block+1; F(i,1,m) { b[i].l=read();b[i].r=read();b[i].id=i; if (pos[b[i].l]==pos[b[i].r]) { ans[i]=query(b[i].l,b[i].r); b[i].l=0; } } sort(b+1,b+m+1,cmp); F(i,1,m) if (b[i].l) { if (pos[b[i].l]!=pos[b[i-1].l]) { l=pos[b[i].l]*block; r=l-1; mx=0; memset(vst,false,sizeof(vst)); memset(pl,0,sizeof(pl)); memset(pr,0,sizeof(pr)); } for(;r<b[i].r;r++) add(a[r+1],0); int tmp=mx; D(j,l-1,b[i].l) add(a[j],1); ans[b[i].id]=mx; mx=tmp; D(j,l-1,b[i].l) vst[a[j]]=false; while (!st.empty()) { pl[st.top().first]=st.top().second;st.pop(); pr[st.top().first]=st.top().second;st.pop(); } } F(i,1,m) printf("%d\n",ans[i]); return 0; }