#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <
string>
#include <map>
#include <stack>
#include <vector>
#include <
set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 50005
#define MAXN 100005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int n,m,ans,cnt,tot,flag;
int len,st,ed;
// 直徑 起點 終點
bool vis[maxn];
int head[maxn],val[maxn],dist[maxn][
2];
int f[maxn][
20],g[maxn][
20],lg[maxn];
//第二維為二進位
struct Node
{
int v,w,next;
} edge[MAXN];
void addedge(
int u,
int v,
int w)
{
cnt++
;
edge[cnt].v=
v;
edge[cnt].w=
w;
edge[cnt].next=
head[u];
head[u]=
cnt;
}
void dfs(
int u,
int fa,
int sum){
if(sum>
len){
len=
sum;
st=
u;
}
int i,j,v;
for(i=head[u];i;i=
edge[i].next){
v=
edge[i].v;
if(v!=
fa){
dfs(v,u,sum+
edge[i].w);
}
}
}
void dfs1(
int u,
int fa,
int k,
int sum){
dist[u][k]=
sum;
int i,j,v;
for(i=head[u];i;i=
edge[i].next){
v=
edge[i].v;
if(v!=
fa)
dfs1(v,u,k,sum+
edge[i].w);
}
}
void init_rmq()
// 預處理 O(n*log(n))
{
int i,j;
for(i=
1;i<=n;i++
)
{
f[i][0]=g[i][
0]=
val[i];
}
for(j=
1;(
1<<j)<=n;j++
)
{
for(i=
1;i+j-
1<=n;i++
)
{
if((i+(
1<<(j-
1))<=
n))
{
f[i][j]=max(f[i][j-
1],f[i+(
1<<(j-
1))][j-
1]);
//避免越界
g[i][j]=min(g[i][j-
1],g[i+(
1<<(j-
1))][j-
1]);
}
else
{
f[i][j]=f[i][j-
1];
g[i][j]=g[i][j-
1];
}
}
}
}
int query_rmq(
int l,
int r)
{
int k=lg[r-l+
1];
return
max(f[l][k],f[r-(
1<<k)+
1][k])-min(g[l][k],g[r-(
1<<k)+
1][k]);
}
int main()
{
int i,j,t;
lg[1]=
0;
for(i=
2;i<=
50000;i++
)
{
lg[i]=lg[i>>
1]+
1;
}
while(~scanf(
"%d%d",&n,&
m))
{
if(n==
0&&m==
0)
break ;
cnt=
0;
memset(head,0,
sizeof(head));
int u,v,w;
for(i=
1;i<n;i++
)
{
scanf("%d%d%d",&u,&v,&
w);
addedge(u,v,w);
addedge(v,u,w);
}
len=
0;
dfs(1,
0,
0);
ed=
st;
len=
0;
dfs(st,0,
0);
dfs1(st,0,
0,
0);
dfs1(ed,0,
1,
0);
for(i=
1;i<=n;i++
)
{
val[i]=max(dist[i][
0],dist[i][
1]);
}
init_rmq();
int q,le,ri,mid,res,id;
while(m--
){
scanf("%d",&
q);
ans=id=
1;
for(i=
1;i<=n;i++
)
{
while(id<=
i){
res=
query_rmq(id,i);
if(res>
q)
id++
;
else break ;
}
ans=max(ans,i-id+
1);
}
printf("%d\n",ans);
}
}
return 0;
}
#include <stdio.h>
#include <
string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int val[
255][
255];
int mm[
255];
int dpmin[
255][
255][
8][
8];
//最小值
int dpmax[
255][
255][
8][
8];
//最大值
void initRMQ(
int n,
int m)
{
for(
int i =
1;i <= n;i++
)
for(
int j =
1;j <= m;j++
)
dpmin[i][j][0][
0] = dpmax[i][j][
0][
0] =
val[i][j];
for(
int ii =
0; ii <= mm[n]; ii++
)
for(
int jj =
0; jj <= mm[m]; jj++
)
if(ii+
jj)
for(
int i =
1; i + (
1<<ii) -
1 <= n; i++
)
for(
int j =
1; j + (
1<<jj) -
1 <= m; j++
)
{
if(ii)
{
dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-
1][jj],dpmin[i+(
1<<(ii-
1))][j][ii-
1][jj]);
dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-
1][jj],dpmax[i+(
1<<(ii-
1))][j][ii-
1][jj]);
}
else
{
dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-
1],dpmin[i][j+(
1<<(jj-
1))][ii][jj-
1]);
dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-
1],dpmax[i][j+(
1<<(jj-
1))][ii][jj-
1]);
}
}
}
//查询矩形的最大值
int rmq1(
int x1,
int y1,
int x2,
int y2)
{
int k1 = mm[x2-x1+
1];
int k2 = mm[y2-y1+
1];
x2 = x2 - (
1<<k1) +
1;
y2 = y2 - (
1<<k2) +
1;
return max(max(dpmax[x1][y1][k1][k2],dpmax[x1][y2][k1][k2]),max(dpmax[x2][y1][k1][k2],dpmax[x2][y2][k1][k2]));
}
//查询矩形的最小值
int rmq2(
int x1,
int y1,
int x2,
int y2)
{
int k1 = mm[x2-x1+
1];
int k2 = mm[y2-y1+
1];
x2 = x2 - (
1<<k1) +
1;
y2 = y2 - (
1<<k2) +
1;
return min(min(dpmin[x1][y1][k1][k2],dpmin[x1][y2][k1][k2]),min(dpmin[x2][y1][k1][k2],dpmin[x2][y2][k1][k2]));
}
int main()
{
mm[0] = -
1;
for(
int i =
1;i <=
500;i++
)
mm[i] = ((i&(i-
1))==
0)?mm[i-
1]+
1:mm[i-
1];
int N,B,K;
for(
int i=
1;i<=
250;i++
){
if(i%
5==
0)
printf("\n");
printf("d",mm[i]);
}
while(scanf(
"%d%d%d",&N,&B,&K)==
3)
{
for(
int i =
1;i <= N;i++
)
for(
int j =
1;j <= N;j++
)
scanf("%d",&
val[i][j]);
initRMQ(N,N);
int x,y;
while(K--
)
{
scanf("%d%d",&x,&
y);
printf("%d\n",rmq1(x,y,x+B-
1,y+B-
1)-rmq2(x,y,x+B-
1,y+B-
1));
}
}
return 0;
}
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN =
100010;
int dp[MAXN][
20];
int mm[MAXN];
void initRMQ(
int n,
int b[])
{
mm[0] = -
1;
for(
int i =
1;i <= n;i++
)
{
mm[i] = ((i&(i-
1)) ==
0)?mm[i-
1]+
1:mm[i-
1];
dp[i][0] =
b[i];
}
for(
int j =
1;j <= mm[n];j++
)
for(
int i =
1;i + (
1<<j) -
1 <= n;i++
)
dp[i][j] = max(dp[i][j-
1],dp[i+(
1<<(j-
1))][j-
1]);
}
int rmq(
int x,
int y)
{
int k = mm[y-x+
1];
return max(dp[x][k],dp[y-(
1<<k)+
1][k]);
}
int a[MAXN];
int hash[MAXN];
int L[MAXN],R[MAXN];
int b[MAXN];
int main()
{
int n,m;
while(scanf(
"%d",&n) ==
1 &&
n)
{
scanf("%d",&
m);
for(
int i =
1;i <= n;i++
)
scanf("%d",&
a[i]);
int k =
1;
int l =
1;
memset(b,0,
sizeof(b));
for(
int i =
1;i <= n;i++
)
{
if(i >
1 && a[i] != a[i-
1])
{
for(
int j = l;j < i;j++
)
{
L[j] =
l;
R[j] = i-
1;
}
b[k] = i -
l;
l =
i;
k ++
;
}
hash[i] =
k;
}
for(
int j = l;j <= n;j++
)
{
L[j] =
l;
R[j] =
n;
}
b[k] = n-l+
1;
initRMQ(k,b);
int u,v;
while(m--
)
{
scanf("%d%d",&u,&
v);
int t1 =
hash[u];
int t2 =
hash[v];
if(t1 ==
t2)
{
printf("%d\n",v-u+
1);
continue;
}
int ans = max(R[u]-u+
1,v-L[v]+
1);
t1++
;
t2--
;
if(t1 <= t2)ans =
max(ans,rmq(t1,t2));
printf("%d\n",ans);
}
}
return 0;
}
转载于:https://www.cnblogs.com/13224ACMer/p/4862195.html
相关资源：垃圾分类数据集及代码
