【传送门：BZOJ4491】
简要题意：
给出一个长度为n的序列，m个操作，每个操作输入x，y，求出第x个数到第y个数的最长子串，保证这个最长子串是不上升或不下降子串
题解：
线段树
因为不上升或不下降嘛，就差分一下呗
每一段区间维护：
d表示最多连续的非正数的个数，u表示最多连续的非负数的个数
ld表示左端点开始向右连续的非正数的个数，rd表示右端点开始向左连续的非正数的个数
lu表示左端点开始向右连续的非负数的个数，ru表示右端点开始向左连续的非负数的个数
然后每次操作的时候注意一下一种情况就是：
比如3 2 1，差分之后是3 -1 -1，最多连续的非负数的个数为2，但是答案为3，也就是说所有连续的个数前一个位置其实也可以算作答案
参考代码：
#include#include #include #include #include using namespace std; struct node {int l,r,lc,rc,u,d;int lu,ld,ru,rd; }tr[110000];int trlen; void bt(int l,int r) {int now=++trlen;tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;tr[now].lu=tr[now].ld=tr[now].ru=tr[now].rd=tr[now].u=tr[now].d=0;if(l<r){int mid=(l+r)/2;tr[now].lc=trlen+1;bt(l,mid);tr[now].rc=trlen+1;bt(mid+1,r);} } void follow(int now) {int lc=tr[now].lc,rc=tr[now].rc;tr[now].d=max(max(tr[lc].d,tr[rc].d),tr[lc].rd+tr[rc].ld);tr[now].u=max(max(tr[lc].u,tr[rc].u),tr[lc].ru+tr[rc].lu);if(tr[lc].ld==(tr[lc].r-tr[lc].l+1)&&tr[rc].rd==(tr[rc].r-tr[rc].l+1)) tr[now].ld=tr[now].rd=tr[now].r-tr[now].l+1;else if(tr[lc].ld==(tr[lc].r-tr[lc].l+1)&&tr[rc].rd!=(tr[rc].r-tr[rc].l+1)) tr[now].ld=tr[lc].ld+tr[rc].ld,tr[now].rd=tr[rc].rd;else if(tr[lc].ld!=(tr[lc].r-tr[lc].l+1)&&tr[rc].rd==(tr[rc].r-tr[rc].l+1)) tr[now].ld=tr[lc].ld,tr[now].rd=tr[lc].rd+tr[rc].rd;else tr[now].ld=tr[lc].ld,tr[now].rd=tr[rc].rd;if(tr[lc].lu==(tr[lc].r-tr[lc].l+1)&&tr[rc].ru==(tr[rc].r-tr[rc].l+1)) tr[now].lu=tr[now].ru=tr[now].r-tr[now].l+1;else if(tr[lc].lu==(tr[lc].r-tr[lc].l+1)&&tr[rc].ru!=(tr[rc].r-tr[rc].l+1)) tr[now].lu=tr[lc].lu+tr[rc].lu,tr[now].ru=tr[rc].ru;else if(tr[lc].lu!=(tr[lc].r-tr[lc].l+1)&&tr[rc].ru==(tr[rc].r-tr[rc].l+1)) tr[now].lu=tr[lc].lu,tr[now].ru=tr[lc].ru+tr[rc].ru;else tr[now].lu=tr[lc].lu,tr[now].ru=tr[rc].ru; } void change(int now,int x,int c) {if(tr[now].l==tr[now].r){if(c==0) tr[now].u=tr[now].d=tr[now].lu=tr[now].ld=tr[now].ru=tr[now].rd=1;else if(c<0){tr[now].ld=tr[now].rd=tr[now].d=1;tr[now].lu=tr[now].ru=tr[now].u=0;}else{tr[now].ld=tr[now].rd=tr[now].d=0;tr[now].lu=tr[now].ru=tr[now].u=1;}return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(x<=mid) change(lc,x,c);else change(rc,x,c);follow(now); } int tot,p[110000]; void findd(int now,int l,int r) {if(tr[now].l==l&&tr[now].r==r){p[++tot]=now;return ;}int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;if(r<=mid) findd(lc,l,r);else if(l>mid) findd(rc,l,r);else findd(lc,l,mid),findd(rc,mid+1,r); } int a[51000]; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=n;i>=1;i--) a[i]=a[i]-a[i-1];trlen=0;bt(1,n);for(int i=1;i<=n;i++) change(1,i,a[i]);int m;scanf("%d",&m);for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);tot=0;findd(1,l,r);int ans=0;int dd=0,uu=0;for(int i=1;i<=tot;i++){int d=tr[p[i]].d,u=tr[p[i]].u;if(d!=tr[p[i]].ld) d++;if(u!=tr[p[i]].lu) u++;ans=max(ans,max(d,u));if(tr[p[i]].d==(tr[p[i]].r-tr[p[i]].l+1)) dd+=tr[p[i]].r-tr[p[i]].l+1;else{ans=max(ans,dd+tr[p[i]].ld);dd=tr[p[i]].rd+1;}if(tr[p[i]].u==(tr[p[i]].r-tr[p[i]].l+1)) uu+=tr[p[i]].r-tr[p[i]].l+1;else{ans=max(ans,uu+tr[p[i]].lu);uu=tr[p[i]].ru+1;}ans=max(ans,max(dd,uu));}printf("%d ",ans);}return 0; }