1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
| #include <bits/stdc++.h> #define MAXN (1<<20)+7 #define MAXM 23 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int cnt[MAXN]; inline void Init(int len){ cnt[1]=0; for(register int i=2;i<=len<<1;++i){ cnt[i]=cnt[i>>1]+1; } } inline void write(int x){ if(x<0)putchar('-'),x*=-1; if(!x)putchar(48); static int sta[45],tp; for(tp=0;x;x/=10)sta[++tp]=x%10; for(;tp;putchar(sta[tp--]^48)); putchar('\n'); } int a[MAXN]; namespace Meow_Tree{ int pos[MAXN]; int maxn[MAXM][MAXN],pmax[MAXM][MAXN]; void Build(int l,int r,int i,int d){ if (l==r) { pos[l]=i; return ; } int mid=(l+r)>>1; int sum,Max; sum=pmax[d][mid]=maxn[d][mid]=a[mid],Max=max(a[mid],0); for (register int i=mid-1;i>=l;--i){ sum+=a[i],Max+=a[i]; pmax[d][i]=max(pmax[d][i+1],sum); maxn[d][i]=max(maxn[d][i+1],Max); Max=max(Max,0); } sum=pmax[d][mid+1]=maxn[d][mid+1]=a[mid+1],Max=max(a[mid+1],0); for (register int i=mid+2;i<=r;++i){ sum+=a[i],Max+=a[i]; pmax[d][i]=max(pmax[d][i-1],sum); maxn[d][i]=max(maxn[d][i-1],Max); Max=max(Max,0); } Build(l,mid,i<<1,d+1); Build(mid+1,r,i<<1|1,d+1); } inline int Query(int l,int r){ if (l==r) return a[l]; int p=cnt[pos[l]]-cnt[pos[l]^pos[r]]; return max(max(maxn[p][l],maxn[p][r]),pmax[p][l]+pmax[p][r]); } } using namespace Meow_Tree; int main(){ int n=read(); for (register int i=1;i<=n;++i) { a[i]=read(); } int len=2; while (len<n) len<<=1; Init(len); Build(1,len,1,1); int m=read(); while (m--){ int l=read(),r=read(); printf("%d\n",Query(l,r)); } }
|