区间反转 参考代码C++

#include 
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f,N=1e5+10;;
int rootx[N*20],ch[N*20][2],totx,toty,Lim,A[N],sum[N],rev[N];
struct node {
	int Lrt,Rrt,Max;
}NODE[N*20*20];
void Update_y(int& y, int l, int r, int pos, int val) {
	if (!y) {
		y=++toty;
		NODE[y].Max=-1;
	}
	NODE[y].Max=max(NODE[y].Max,val);
	if (l==r) return;
	int m=(l+r)>>1;
	if (pos<=m) Update_y(NODE[y].Lrt,l,m,pos,val);
	else Update_y(NODE[y].Rrt,m+1,r,pos,val);
}
void Update_x(int&x, int y, int l, int r, int pos, int val) {
	if (!x) x=++totx;
	Update_y(rootx[x],1,Lim,y,val);
	if (l==r) return;
	int m=(l+r)>>1;
	if (pos<=m) Update_x(ch[x][0],y,l,m,pos,val);
	else Update_x(ch[x][1],y,m+1,r,pos,val);
}
int query_y(int rt, int L, int R, int l, int r) {
	if (rt==0) return -INF;
	if (L==l&&R==r) return NODE[rt].Max;
	int m=(l+r)>>1;
	if (R<=m) return query_y(NODE[rt].Lrt,L,R,l,m);
	else if (L>m) return query_y(NODE[rt].Rrt,L,R,m+1,r);
	else return max(query_y(NODE[rt].Lrt,L,m,l,m),query_y(NODE[rt].Rrt,m+1,R,m+1,r));
}
int query_x(int rt, int ly, int ry, int lx, int rx, int l, int r) {
	if (rt==0) return -INF;
	if (lx==l&&r==rx) return query_y(rootx[rt],ly,ry,1,Lim);
	int m=(l+r)>>1;
	if (rx<=m) return query_x(ch[rt][0],ly,ry,lx,rx,l,m);
	else if (lx>m) return query_x(ch[rt][1],ly,ry,lx,rx,m+1,r);
	else return max(query_x(ch[rt][0],ly,ry,lx,m,l,m),query_x(ch[rt][1],ly,ry,m+1,rx,m+1,r));
}
int main() {
	int n; scanf("%d",&n);
	for (int i=1; i<=n; i++) {
		scanf("%d",&A[i]); Lim=max(Lim,A[i]);
	}
	Lim++;
	A[0]=Lim; //设置比最大值大 
	A[n+1]=-1; //设置比最小值小 
	for (int i=2; i<=n; i++) {
		sum[i]=sum[i-1];
		if (A[i]>A[i-1]) sum[i]++;
	}
	sum[n+1]=sum[n];
	for (int i=n-1; i>=1; i--) {
		rev[i]=rev[i+1];
		if (A[i]>A[i+1]) rev[i]++;
	}
	int rt=0,ans=0;
	for (int R=1; R<=n; R++) {
		Update_x(rt,A[R],1,Lim,A[R-1],sum[R-1]+rev[R]);
		int X=sum[n]-sum[R+1]-rev[R];
		//情况一： 
		int lx=1,rx=A[R]-1;
		int ly=1,ry=A[R+1]-1;
		if (lx<=rx&&ly<=ry) ans=max(ans,X+query_x(rt,ly,ry,lx,rx,1,Lim)+2);
		//情况二：
		lx=1,rx=A[R]-1;
		ly=max(A[R+1],1),ry=Lim;
		if (lx<=rx&&ly<=ry) ans=max(ans,X+query_x(rt,ly,ry,lx,rx,1,Lim)+1);
		//情况三：
		lx=A[R],rx=Lim;
		ly=1,ry=A[R+1]-1;
		if (lx<=rx&&ly<=ry) ans=max(ans,X+query_x(rt,ly,ry,lx,rx,1,Lim)+1);
		//情况四：
		lx=A[R],rx=Lim;
		ly=max(A[R+1],1),ry=Lim;
		if (lx<=rx&&ly<=ry) ans=max(ans,X+query_x(rt,ly,ry,lx,rx,1,Lim));
	}
	printf("%dn",ans);
	return 0;
}