算法競賽2022年第十三屆藍橋杯C++ B組_砍竹子
//?https://www.acwing.com/problem/content/4412/
//? 代碼已經(jīng)通過測試
#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;
}
