线段树，TLE，各种。唉。。。。我真是笨死了。。。。
我用的线段树是记录左右区间最长连续棵数的。。。反正TLE
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int N=50050;
struct Q{
int val,index;
}Que[N];
int SegT[N*4],L[N*4],R[N*4],C[N*4];
int TreeH[N];
int ans[N];
bool cmp(Q a,Q b){
if(a.val<b.val) return true;
return false;
} void build(int l,int r,int rt){
L[rt]=R[rt]=r-l+1;C[rt]=1;
if(l==r){
SegT[rt]=TreeH[l];
return ;
}
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
SegT[rt]=max(SegT[rt<<1],SegT[rt<<1|1]);
} void slove(int l,int r,int rt,int hv){
if(l==r){
return ;
}
int m=(l+r)>>1;
if(hv>=SegT[rt<<1])
L[rt<<1]=R[rt<<1]=C[rt<<1]=0;
else
slove(l,m,rt<<1,hv);
if(hv>=SegT[rt<<1|1]) L[rt<<1|1]=R[rt<<1|1]=C[rt<<1|1]=0;
else
slove(m+1,r,rt<<1|1,hv);
L[rt]=L[rt<<1],R[rt]=R[rt<<1|1];
if(L[rt<<1]>=m-l+1) L[rt]+=L[rt<<1|1];
if(R[rt<<1|1]>=r-m) R[rt]+=R[rt<<1];
C[rt]=C[rt<<1]+C[rt<<1|1];
if(R[rt<<1]&&L[rt<<1|1]&&C[rt]) C[rt]--;
} void readint1(int i) {
TreeH[i]=0;
char ch;
ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){
TreeH[i]=TreeH[i]*10+ch-'0';
ch=getchar();
}
} int readint2(){
int x=0;
char ch;
ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
} int main(){
int n,q;
while(scanf("%d%d",&n,&q)!=EOF){
memset(ans,0,sizeof(int)*n);
for(int i=1;i<=n;i++)
readint1(i);
build(1,n,1);
for(int i=0;i<q;i++){
Que[i].val=readint2();
Que[i].index=i;
}
sort(Que,Que+q,cmp);
for(int i=0;i<q;i++){
if(Que[i].val>=SegT[1]){
ans[Que[i].index]=0;
}
else{
slove(1,n,1,Que[i].val);
ans[Que[i].index]=C[1];
}
}
for(int i =0;i<q;i++)
printf("%d\n",ans[i]);
}
return 0;
}
这个是看了别人之后的解法，漂亮啊。。。
把树排序，把询问排序，都按高度。两个指针扫描，对于不高于询问高度的树，对其原本的位置，若左右均未砍去，则段数+1，若均砍去，则段数-1，除此外，段数不变。
再感叹一下，漂亮啊。。。。T_T
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std;
const int N=50050; struct TH{
int height,index;
}Tree[N],Que[N];
bool vis[N];
int n,q,ans[N];
bool cmp(TH a,TH b){
if(a.height<b.height) return true;
return false;
} void work(int &c,int index){
if(index==0){
if(vis[index+1]) c--;
}
else if(index==n-1){
if(vis[index-1]) c--;
}
else{
if(!vis[index+1]&&!vis[index-1]) c++;
else if(vis[index+1]&&vis[index-1]){
c--;
}
}
} int main(){
while(scanf("%d%d",&n,&q)!=EOF){
for(int i=0;i<n;i++){
scanf("%d",&Tree[i].height);
Tree[i].index=i;
}
sort(Tree,Tree+n,cmp);
for(int i=0;i<q;i++){
scanf("%d",&Que[i].height);
Que[i].index=i;
}
sort(Que,Que+q,cmp);
memset(vis,false,sizeof(vis));
int ct=0;
int counts=1;
for(int i=0;i<q;i++){
for(;ct<n;ct++){
if(Tree[ct].height>Que[i].height) break;
vis[Tree[ct].index]=true;
work(counts,Tree[ct].index);
}
ans[Que[i].index]=counts;
}
for(int i=0;i<q;i++)
printf("%d\n",ans[i]);
}
return 0;
}