程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj4358 perm

bzoj4358 perm

編輯:C++入門知識

bzoj4358 perm


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

Sample Output

3
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

Source

By sumix173

思路很棒!

每個點記錄兩個信息: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; .l="read();b[i].r=read();b[i].id=i;" block="int(sqrt(n));" bool="" data="" if="" inline="" int="" l="pos[b[i].l]*block;" mx="max(mx,tr-tl+1);" n="read();m=read();" pre="" r="l-1;" return="" tl="x,tr=x;" tmp="mx;" tr="pr[x+1];" void="" while=""><p>
</p>
   
</y.r:x.l<y.l;></pa></int,int></stack></algorithm></cmath></cstring></cstring></cstdio></iostream>

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved