猫树

第 $1\sim6$ 个点 WA
第 $7\sim10$ 个点 RE

开的越大 RE 越多

#include<cstdio>
#include<algorithm>
using namespace std;

#define N 5000500
#define DEPTH 25

int n,q;
int a[N];
int tree[DEPTH][N],sum[DEPTH][N];
int maxn,leaf[N<<2],depth[N<<2];

void build(int k,int l,int r,int dep)
{
	int *Tree=tree[dep],*Sum=sum[dep];
	
	if(l==r)
	{
		Tree[l]=Sum[l]=a[l];
		leaf[l]=k;
		return;
	}
	
	int mid=l+r>>1;
	
	Sum[mid]=Tree[mid]=a[mid];
	int sums=a[mid],mins=min(a[mid],0);
	for(int i=mid-1;i>=l;--i)
		sums+=a[i],
		Sum[i]=max(Sum[i+1],sums),
		Tree[i]=max(Tree[i+1],sums-mins),
		mins=min(mins,sums);
	
	Sum[mid+1]=Tree[mid+1]=a[mid+1];
	sums=a[mid+1],mins=min(a[mid+1],0);
	for(int i=mid+2;i<=r;++i)
		sums+=a[i],
		Sum[i]=max(Sum[i-1],sums),
		Tree[i]=max(Tree[i-1],sums-mins),
		mins=min(mins,sums);
	
	build(k<<1,l,mid,dep+1);
	build(k<<1|1,mid+1,r,dep+1);
}

int query(int l,int r)
{
	if(l==r)
		return a[l];
	int dep=depth[leaf[l]]-depth[leaf[l]^leaf[r]];
	int *Tree=tree[dep],*Sum=sum[dep];
	#ifdef debug
	printf("[%d]",dep);
	#endif
	return max(max(Tree[l],Tree[r]),Sum[l]+Sum[r]);
}

signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	
	for(maxn=1;maxn<n;maxn<<=1);
	for(int i=1;i<=1<<maxn;++i)
		depth[i]=depth[i>>1]+1;
	build(1,1,maxn,1);
	
	#ifdef debug
	putchar('[');
	printf("_%d_ ",maxn);
	for(int i=1;i<=7;++i)
		printf("%d ",depth[i]);
	putchar(']');
	#endif
	
	scanf("%d",&q);
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",query(l,r));
	}
	return 0;
}

说句闲话, 今天在站外交的都带 RE, 在洛谷交的都是 UKE