链接:https://nanti.jisuanke.com/t/16878
分析:先挖个坑。。这题貌似有问题,按题意应该是能砍则砍,但是样例是按能得到的最大数来算的。。下面先按能砍则砍来分析。。
首先预处理一下,f[i]表示从1砍到i,能砍的最大数,b[i]表示如果把i砍了,从i往后一共能砍多少棵,MAX[i]表示从1到i,砍过的树中的最大高度。f和MAX直接O(n)处理就行了,b[i]用线段树来处理,b[i]=b[j]+1,j是满足h[j]>h[i]且j>i的j中最小值,复杂度为O(nlogn)。
然后询问,如果b>MAX[a-1],第a棵修改后依然要砍,因此ans=1+f[a-1]+b[j],j是满足j>a且h[j]>b的j中最小值;否则,不砍第a棵,ans=f[a-1]+b[j],j是满足j>a且h[j]>MAX[a-1]的j中最小值。复杂度为O(nlogn)。
以下代码不能AC,样例都过不了。。坐等出题人修改题意或样例再改。。。
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=4e5+5; 6 int n,m; 7 class segTree{ 8 public: 9 int a[maxn],s[maxn*4];10 void build(int node,int begin,int end){11 if(begin==end){12 s[node]=begin;13 }else{14 build(2*node,begin,(begin+end)/2);15 build(2*node+1,(begin+end)/2+1,end);16 if(a[s[2*node]]>=a[s[2*node+1]])17 s[node]=s[2*node];18 else19 s[node]=s[2*node+1];20 }21 }22 int query(int node,int begin,int end,int left,int right,int low_bound){23 if(left>end||right =left&&end<=right)26 // return s[node];27 if(begin==end){28 if(a[begin]>low_bound)return begin;29 return -1;30 }31 int q1,q2;32 if(a[s[2*node]]>low_bound)return query(2*node,begin,(begin+end)/2,left,right,low_bound);33 if(a[s[2*node+1]]>low_bound)return query(2*node+1,(begin+end)/2+1,end,left,right,low_bound);34 return -1;35 }36 }st;37 int Max[maxn],sum_front[maxn],sum_back[maxn];38 int h[maxn];39 int main(){40 // freopen("e:\\in.txt","r",stdin);41 scanf("%d%d",&n,&m);42 Max[0]=0,sum_front[0]=0;43 for(int i=1;i<=n;i++){44 scanf("%d",&h[i]);45 st.a[i]=h[i];46 if(h[i]>Max[i-1]){47 sum_front[i]=sum_front[i-1]+1;48 Max[i]=h[i];49 }else{50 sum_front[i]=sum_front[i-1];51 Max[i]=Max[i-1];52 }53 }54 int k;55 ta.init(n);56 st.build(1,1,n);57 sum_back[n]=1;58 for(int i=n-1;i>=1;i--){59 k=st.query(1,1,n,i+1,n,h[i]);60 if(k!=-1)sum_back[i]=1+sum_back[k];61 else sum_back[i]=1;62 }63 int a,b;64 for(int i=0;i Max[a-1]){68 ans++;69 k=st.query(1,1,n,a+1,n,b);70 if(k!=-1)ans+=sum_back[k];71 }else{72 k=st.query(1,1,n,a+1,n,Max[a-1]);73 if(k!=-1)74 ans+=sum_back[k];75 }76 printf("%d\n",ans);77 }78 return 0;79 }