SP1043 GSS1 – Can you answer these queries I(猫树)[亲测有效]

SP1043 GSS1 – Can you answer these queries I(猫树)[亲测有效]给出了序列A[1],A[2],…,A[N]。(a[i]≤15007,1≤N≤50000)。查询定义如下:查询(x,y)=max{a[i]+a[i+1]+…+a[j];x≤i≤j≤y}。给定M个查询,程序必须输出这些查询的结果。这就是一个最大子段和,用线段树就能直接搞掉然后这里学习了一下一个叫做猫树的神奇东西->这里能做到预处理之后查询$O(1)$1//…

给出了序列A[1],A[2],…,A[N]。 (a[i]≤15007,1≤N≤50000)。查询定义如下: 查询(x,y)=max{a[i]+a[i+1]+…+a[j];x≤i≤j≤y}。 给定M个查询,程序必须输出这些查询的结果。

 

这就是一个最大子段和,用线段树就能直接搞掉

然后这里学习了一下一个叫做猫树的神奇东西->这里

能做到预处理之后查询$O(1)$

 1 //minamoto
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 6 char buf[1<<21],*p1=buf,*p2=buf;
 7 int read(){
 8     #define num ch-'0'
 9     char ch;bool flag=0;int res;
10     while(!isdigit(ch=getc()))
11     (ch=='-')&&(flag=true);
12     for(res=num;isdigit(ch=getc());res=res*10+num);
13     (flag)&&(res=-res);
14     #undef num
15     return res;
16 }
17 char sr[1<<21],z[20];int C=-1,Z;
18 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
19 void print(int x){
20     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
21     while(z[++Z]=x%10+48,x/=10);
22     while(sr[++C]=z[Z],--Z);sr[++C]='\n';
23 }
24 const int N=5e+5;
25 int n,m,a[N],len,log[N],pos[N],p[21][N],s[21][N];
26 void build(int pp,int l,int r,int d){
27     if(l==r) return (void)(pos[l]=pp);
28     int mid=(l+r)>>1,prep,sm;
29     p[d][mid]=s[d][mid]=sm=prep=a[mid];
30     if(sm<0) sm=0;
31     for(int i=mid-1;i>=l;--i){
32         prep+=a[i],sm+=a[i];
33         s[d][i]=max(s[d][i+1],prep),
34         p[d][i]=max(p[d][i+1],sm);
35         if(sm<0) sm=0;
36     }
37     p[d][mid+1]=s[d][mid+1]=sm=prep=a[mid+1];
38     if(sm<0) sm=0;
39     for(int i=mid+2;i<=r;++i){
40         prep+=a[i],sm+=a[i];
41         s[d][i]=max(s[d][i-1],prep),
42         p[d][i]=max(p[d][i-1],sm);
43         if(sm<0) sm=0;
44     }
45     build(pp<<1,l,mid,d+1);
46     build(pp<<1|1,mid+1,r,d+1);
47 }
48 int query(int l,int r){
49     if(l==r) return a[l];
50     int d=log[pos[l]]-log[pos[l]^pos[r]];
51     return max(max(p[d][l],p[d][r]),s[d][l]+s[d][r]);
52 }
53 int main(){
54 //    freopen("testdata.in","r",stdin);
55     n=read();for(int i=1;i<=n;++i) a[i]=read();
56     len=2;while(len<n) len<<=1;
57     for(int i=2,l=len<<1;i<=l;++i) log[i]=log[i>>1]+1;
58     build(1,1,len,1);
59     m=read();
60     while(m--){
61         int l=read(),r=read();
62         print(query(l,r));
63     }
64     return Ot(),0;
65 }

 

转载于:https://www.cnblogs.com/bztMinamoto/p/9826116.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/10629.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注