老了，数据结构搞不动啦
线段树沙茶题，差分一下维护区间>=0和<=0即可
还没有change
我去这样的题还要写拍才能过。。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int a[51000]; struct seg_tree { int l,r,lc,rc; int u,uL,uR; int d,dL,dR; seg_tree(){} void U(int u1,int u2,int u3){u=max(u1,max(u2,u3)),uL=u2,uR=u3;} void D(int d1,int d2,int d3){d=max(d1,max(d2,d3)),dL=d2,dR=d3;} }tr[110000];int trlen; void upd(int now) { int l=tr[now].l,r=tr[now].r; int mid=(l+r)/2; int Ltot=mid-l+1,Rtot=r-(mid+1)+1; seg_tree LC=tr[tr[now].lc],RC=tr[tr[now].rc]; tr[now].U( max(max(LC.u,RC.u),LC.uR+RC.uL), (LC.uL==Ltot)?Ltot+RC.uL:LC.uL , (RC.uR==Rtot)?Rtot+LC.uR:RC.uR ); tr[now].D( max(max(LC.d,RC.d),LC.dR+RC.dL), (LC.dL==Ltot)?Ltot+RC.dL:LC.dL , (RC.dR==Rtot)?Rtot+LC.dR:RC.dR ); } void bt(int l,int r) { trlen++;int now=trlen; tr[now].l=l;tr[now].r=r; if(l==r) { tr[now].lc=tr[now].rc=-1; int ut=(a[l]>=0)?1:0; tr[now].U(ut,ut,ut); int dt=(a[l]<=0)?1:0; tr[now].D(dt,dt,dt); } else { int mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); upd(now); } } int findans(int now,int l,int r) { if(tr[now].l==l&&tr[now].r==r)return max(tr[now].u,tr[now].d); int mid=(tr[now].l+tr[now].r)/2; int lc=tr[now].lc,rc=tr[now].rc; if(r<=mid)return findans(lc,l,r); else if(mid+1<=l)return findans(rc,l,r); else { int ans1=findans(lc,l,mid); int ans2=findans(rc,mid+1,r); int ans3=min(tr[lc].uR,mid-l+1)+min(tr[rc].uL,r-(mid+1)+1); int ans4=min(tr[lc].dR,mid-l+1)+min(tr[rc].dL,r-(mid+1)+1); return max(max(ans1,ans2),max(ans3,ans4)); } } int main() { freopen("data.in","r",stdin); freopen("lj.out","w",stdout); int n; scanf("%d",&n); int x,last; scanf("%d",&last); for(int i=1;i<n;i++) scanf("%d",&x), a[i]=x-last, last=x; trlen=0;bt(1,n-1); int Q,l,r; scanf("%d",&Q); while(Q--) { scanf("%d%d",&l,&r); if(l==r)printf("1 "); else printf("%d ",findans(1,l,r-1)+1); } return 0; }