算法竞赛2022年第十三届蓝桥杯C++ B组_砍竹子
// https://www.acwing.com/problem/content/4412/
// 代码已经通过测试
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#include <iostream>
#include<math.h>
using namespace std;
const int maxn=210000,maxt=maxn*3;
int n;
long long B[maxn]={2,1 ,4, 2, 6, 7};
long long MAX[maxt ][5];
void Pushup(int p){//合并信息
MAX[p][0]=max(MAX[p<<1][0],MAX[p<<1|1][0]); // for update
MAX[p][2]=max(MAX[p<<1][2],MAX[p<<1|1][2]);
if(MAX[p<<1][0]!=MAX[p<<1|1][0]){
MAX[p][2]=1;
if (MAX[p][0]==MAX[p<<1][0]){ // max is on the left
MAX[p][1]=MAX[p<<1][1];
MAX[p][3]=MAX[p<<1][3];
MAX[p][4]=MAX[p<<1][4];
}
else { // max is on the right
MAX[p][1]=MAX[p<<1|1][1];
MAX[p][3]=MAX[p<<1|1][3];
MAX[p][4]=MAX[p<<1|1][4];
}
}
else // 左右最大值相等
{
if(MAX[p<<1][4]+1 != MAX[p<<1|1][3]) // not consecutive
MAX[p][1]=MAX[p<<1][1]+MAX[p<<1|1][1];
else // consecutive
MAX[p][1]=MAX[p<<1][1]+MAX[p<<1|1][1]-1;
MAX[p][3]=MAX[p<<1][3]; // left boundary
MAX[p][4]=MAX[p<<1|1][4]; // right boundary
}
}
void Build(int L,int R,int p ){
if (L==R){
MAX[p][0]=B[L];
MAX[p][1]=1; // The number of segments equal to the maximum
MAX[p][2]=0; // All nodes equal to the maximum
MAX[p][3]=L; // left boundary
MAX[p][4]=R; // right boundary
//if(p==8)printf("p=8: %lld , %lld, %lld \n",MAX[p][0], MAX[p][1], MAX[p][2]);
return;
}
int mid=(R+L)>>1;
Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
Pushup(p);
}
void update(int cur,int lt,int rt,int val){
if(lt==rt || MAX[cur][2]==0){
MAX[cur][0]=val;return;
}
int mid=(lt+rt)>>1;
if(MAX[cur<<1][0] ==MAX[cur][0])
update(cur<<1,lt,mid,val);//访问左孩子
if(MAX[cur<<1|1][0] ==MAX[cur][0])
update(cur<<1|1,mid+1,rt,val);//访问右孩子
Pushup(cur);//更新信息
}
int main(){
int count=0;
n=6;
//*
cin >>n;
for(int x=0;x<n;x++)
cin >> B[x];
//*/
Build(0,n-1,1);
int tmp;
while(MAX[1][0]!=1)
{
count += MAX[1][1];
tmp=sqrt( MAX[1][0]/2+1);
update(1, 0, n-1, tmp);
/*
for(int x=1;x<10;x++)
{
printf("%lld , %lld, %lld \n",MAX[x][0], MAX[x][1], MAX[x][2]);
}
printf("\n"); */
}
printf("%d\n",count);
return 0;
}
