题解 P4715 【【深基16.例1】淘汰赛】

· · 题解

继续承包入门赛压轴题题解~

这次比赛的压轴题，是关于求最值的题目：先相邻的两两求最大值，再把这些最大值重复操作，直到最后为止。

一看这架势：递归？？？嗯，确实是递归不假，咱来画个图看看：

哎，咱一看，怎么那么像棵二叉树呢？而且，这棵二叉树里，父节点存储的是左右子节点的最大值！其实，这东西不光是棵二叉树，还是一种更特殊的的数据结构——线段树！

啥事线段树你呢？别慌，咱先看个栗子：

有n个数，m次操作，操作可以修改某一个数或者查询一段区间的值

当然，这题修改操作O(1)就行，求和可以用O(n)方法一个个暴力去加，但是如果n和m都很大呢？？？...你懂得.....

这时聪明的小伙伴就想到了：我们可以开一个前缀和数组呀！这回求和操作倒是可以O(1)了，但修改操作嘛......每改一次，每个前缀和都要改一遍，还是难逃O(n)的命运啊......

那就没设么好的方法了吗？有啊！好方法就是我们前面说的线段树了，它可以把时间复杂度降低降低再降低，把修改和查询的时间复杂度都降到O(\log n)！！！

说到这了，咱先瞅瞅这线段树长啥样，当当当当~：

没错，线段树就长这个样！就是一棵二叉树，但是这颗二叉树有一个神奇的性质：每个父节点是它的两个子节点的值的和！

那为什么用了这个东西，就能降时间复杂度呢？？？别急，咱们先来看几个具体例子：

首先看修改的栗子，把节点中的2加3（也就是把2改成5）

只要像这个图一样，找到节点2，把2加上3，然后顺着路一个一个改上来就行了~

再来看查询的栗子：求区间2~5的和

还是用递归的思想：

2~5的和

=2~3的和+4~5的和

=2+3+4~5的和

=2+3+9

=14

总之，就是沿着线段树的划分把区间分开，再加到一块就行啦！

看了刚才的栗子，线段树确实能让时间复杂度降低不少，不过这么好个东西，咱们怎么来存它呢？？

（说句闲话：这棵树怎么那么像完全二叉树呢？？）

既然那么像完全二叉树，那咱们就硬核补几个顶点，把它变成完全二叉树吧！

既然能补上完全二叉树，那就好办了，我们就可以直接用一个数组来存它！

为啥用数组就好了呢？因为我们有完全二叉树的性质呀！

就像上图一样把各个节点标上号，如果根节点编号是n,那它的左子树编号是2n,右子树的编号是2n+1

所以说，知道了根节点的编号，我们就可以快速有效的找到左右子树的根节点

接下来就是放代码的时候了：首先，建立一棵线段树：

ll arr[100010]={0},tree[500050]={0};  //arr为存储数据的数组，tree是存线段树的数组
void build(int node,int start,int end){   //建树函数，参数是根节点和左右区间 
    if(start==end){     //如果两边相等 
        tree[node]=arr[start]; //填的就是数组里的初始值 
        return;  //递归边界 
    }
    int leftnode=node*2;  //算出左右节点（完全二叉树的性质） 
    int rightnode=node*2+1;  
    int mid=(start+end)/2;    //把数组从中间劈成两半
    build(leftnode,start,mid);  //左边右边分开建树 
    build(rightnode,mid+1,end);
    tree[node]=tree[leftnode]+tree[rightnode]; //根节点的值=左根+右根 
}

然后呢，进行单点修改和区间查询的操作，相信你对树的理解和经验，一定能看懂！

（剧透一下：这个题只需要把线段树建出来就行了，所以这俩函数并不是这个题的重点）

void update(int node,int start,int end,int id,int val){      //修改操作，参数分别是建树函数的那三个和修改节点的编号和修改的值
    if(start==end){ //递归边界，如果是叶节点
        tree[node]+=val; //修改node节点的值
        return;
    }
    int leftnode=node*2;  //算出左右子树和中点
    int rightnode=node*2+1;  
    int mid=(start+end)/2;   
    if(id>=start&&id<=mid) //如果要改的地方在中点左边
    update(leftnode,start,mid,id,val);//那就递归修改左子树
    else update(rightnode,mid+1,end,id,val);//要么就递归修改右子树    
    tree[node]=tree[leftnode]+tree[rightnode]; //根节点更新 
} 
int query(int node,int start ,int end,int l,int r){ //查询函数，l和r是求和的左右区间
    if(l<=start&&r>=end)  //如果求和的区间已经当前的部分包含了
//（比如当前在[1,3]区间，让你求[1，5]，那你就要求[1,3]+[4,5]，直接把建树的时候算好的[1,3]的和加上去就行了）
    return tree[node]; //直接返回根节点
    int leftnode=node*2;  //又双叒叕是左右子树和中点
    int rightnode=node*2+1;  
    int mid=(start+end)/2;
    int sum=0; //就是要返回的和啊   
    if(l<=mid) //如果要求和的区间包含中点左边的部分
    sum+=query(leftnode,start,mid,l,r); //那就加上左边那块
    if(r>mid) //同理，如果右边还有那就加上右边那块
    sum+=query(rightnode,mid+1,end,l,r);
    return sum; //返回sum，不解释
}

聊了那么久的线段树，接下来就说说这个题：这个题的思路大家都应该知道了吧，就是建立一棵线段树，每一个节点是左右两个子节点里较大的那个

由于最后肯定是tree[2]和tree[3]争冠军（看前面图），而题目让我们输出亚军，所以亚军就是tree[2]和tree[3]里能力值较小的那个

还有，题目让我们输出亚军的国家序号，因此我们可以把线段树的节点弄成包含能力值和序号的结构体来处理

AC code：

#include<iostream>
#include<cstring>
#include<algorithm> //比赛的时候闲的没事打了一堆头文件
#include<cmath>
#include<iomanip> 
using namespace std;
struct jiegouti{  //真·结构体
    int power,id;  //power——能力值，id——国家序号
}; 
jiegouti maxt(jiegouti a,jiegouti b){  //返回两个结构体里能力值更大的那个
    return a.power>b.power?a:b;
}
jiegouti mint(jiegouti a,jiegouti b){ //返回两个结构体里能力值更大的那个
    return a.power<b.power?a:b;
}
jiegouti a[150],tree[600];  //a——数据，tree——线段树（一般为了防爆，线段树都是开数组的4倍空间）
void build(int node,int start,int end){ //建树函数
    if(start==end){  //叶节点，返回
        tree[node]=a[start];
        return;
    }
    int lnode=node*2;  //左右子树、中点
    int rnode=node*2+1;
    int mid=(start+end)/2;
    build(lnode,start,mid);  //两边递归建树
    build(rnode,mid+1,end);
    tree[node]=maxt(tree[lnode],tree[rnode])  //父节点是左右子节点里更大的;
}
int main(){
    int n;  //输入
    cin>>n;
    for(int i=1;i<=(1<<n);i++){  //1<<n就是2的n次方啦！（这样比pow函数更快哦！）
        cin>>a[i].power;  //输入，赋值，很简单
        a[i].id=i;  
    }
    build(1,1,(1<<n)); //建树（根节点是1，整棵树从1到2的n次方）
    cout<<mint(tree[2],tree[3]).id; //从tree[2],tree[3]里找个小的就是亚军，输出它的序号
    return 0;
}

(P.S:我真没有恶搞代码的意思，考试的时候画了个图就想到线段树了，正好刚学，就用这个题练练)

The End