树型模板

忠诚

标签(空格分隔): 树状数组 线段树


题目描述

老管家是一个聪明能干的人。他为财主工作了整整10年,财主为了让自已账目更加清楚。要求管家每天记k次账,由于管家聪明能干,因而管家总是让财主十分满意。但是由于一些人的挑拨,财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚,他把每次的账目按1,2,3…编号,然后不定时的问管家问题,问题是这样的:在a到b号账中最少的一笔是多少?为了让管家没时间作假他总是一次问多个问题。

输入

输入中第一行有两个数m,n表示有m(m< =100000)笔账,n表示有n个问题,n 输出文件中为每个问题的答案。具体查看样例

样例输入

10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10

样例输出

2 3 1


解法1:树状数组

树状数组定义

① c[x]=min_{i=x-lowbit(x)+1}^x a[i]

② c[x]管lg(lowbit(x))

### ③ c[x]的直接父亲=x+lowbir(x)

解法2:线段树

uses math;
var 
    f,a:array[1..2000000] of longint;
    n,m,i,x,y,ans:longint; op:char;
procedure buildtree(l,r,k:longint);
var mid:longint;
begin
    if l=r then
    begin
        f[k]:=a[l];
        exit;
    end;
    mid:=(l+r) shr 1;
    buildtree(l,mid,k shl 1);
    buildtree(mid+1,r,k shl 1+1);
    f[k]:=min(f[k shl 1],f[k shl 1+1]);
end;
procedure find(l1,r1,l2,r2,k:longint);
var mid:longint;
begin
    if (l1=l2)and(r1=r2) then
    begin
        ans:=min(f[k],ans);
        exit;
    end;
    mid:=(l2+r2) shr 1;
    if r1<=mid then 
    begin 
        find(l1,r1,l2,mid,k shl 1);
        exit;
    end;
    if l1>mid then
    begin
        find(l1,r1,mid+1,r2,k shl 1+1);
        exit;
    end;
    find(l1,mid,l2,mid,k shl 1);
    find(mid+1,r1,mid+1,r2,k shl 1+1);
end;
begin
    read(n,m);
    for i:=1 to n do read(a[i]);
    buildtree(1,n,1);
    for i:=1 to m do
    begin
        readln(x,y);
        ans:=1000000000;  
        find(x,y,1,n,1);
        if i<>m then write(ans,' ')
        else write(ans);
    end;
end.

st表
```c++
#include<bits/stdc++.h>
const int maxn=200007;
const int maxB=17;
using namespace std;
int n,m,f[maxn][maxB+1],Log[maxn];

int main(){
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++) scanf("%d", &f[i][0]);
Log[1]=0;
for (int i=2; i<=n; i++) Log[i]=Log[i>>1]+1;
for (int j=1; j<=Log[n]; j++)
for (int i=1; i<=n; i++){
f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
while (m--){
int L,R;
scanf("%d%d", &L, &R);
int k=Log[R-L+1];
int ans=min(f[L][k],f[R-(1<<k)+1][k]);
if (m>0) printf("%d ",ans);
else printf("%d\n",ans);
}
return 0;
}
```

还没有评论,快来抢沙发!

发表评论