首页 > 代码库 > "Ray, Pass me the dishes!"

"Ray, Pass me the dishes!"

2024-07-11 19:21:34   216人阅读

uvaLive3938:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1939

题意：给你n个数，然后给你一个区间，让你查询这个区间内最大和连续子区间。

题解：哎。智商是硬伤啊，虽然线段树也做过不少题目，但是遇到这样的题目还是不会处理啊，看了别人的代码才明白了怎么做。用那个线段树维护区间最大前缀，最大后缀，以及真正的最大区间。要注意父节点这三个变量是怎么由子节点推导出来的。还是贴代码吧。

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 using namespace std;  6 const int N=500009;  7 int ll[N*3],rr[N*3];  8 struct  Node{  9    int pre,suf; 10    int vx,vy; 11 }num[N*3]; 12 long long sum[N]; 13 void pushup(int rt,int l,int r){ 14     if(sum[num[rt<<1].pre]-sum[l-1]>=sum[num[rt<<1|1].pre]-sum[l-1]) 15         num[rt].pre=num[rt<<1].pre; 16     else 17         num[rt].pre=num[rt<<1|1].pre; 18     if(sum[r]-sum[num[rt<<1].suf-1]>=sum[r]-sum[num[rt<<1|1].suf-1]) 19         num[rt].suf=num[rt<<1].suf; 20     else 21         num[rt].suf=num[rt<<1|1].suf; 22     long long v1=sum[num[rt<<1].vy]-sum[num[rt<<1].vx-1]; 23     long long v2=sum[num[rt<<1|1].vy]-sum[num[rt<<1|1].vx-1]; 24     long long v0=sum[num[rt<<1|1].pre]-sum[num[rt<<1].suf-1]; 25     if(v1>=v2){ 26         num[rt].vx=num[rt<<1].vx; 27         num[rt].vy=num[rt<<1].vy; 28     } 29     else{ 30         num[rt].vx=num[rt<<1|1].vx; 31         num[rt].vy=num[rt<<1|1].vy; 32     } 33     if(v0==sum[num[rt].vy]-sum[num[rt].vx-1]){ 34         if(num[rt<<1].suf<num[rt].vx){ 35         num[rt].vx=num[rt<<1].suf; 36         num[rt].vy=num[rt<<1|1].pre; 37         } 38     } 39      if(v0>sum[num[rt].vy]-sum[num[rt].vx-1]){ 40          num[rt].vx=num[rt<<1].suf; 41         num[rt].vy=num[rt<<1|1].pre; 42     } 43 } 44 void build(int rt,int l,int r){ 45      ll[rt]=l; 46      rr[rt]=r; 47      if(l==r){ 48         num[rt].pre=num[rt].suf=num[rt].vx=num[rt].vy=l; 49         return; 50      } 51     int mid=(l+r)/2; 52     build(rt<<1,l,mid); 53     build(rt<<1|1,mid+1,r); 54     pushup(rt,l,r); 55 } 56 Node query(int rt,int s,int t){ 57     if(ll[rt]==s&&rr[rt]==t) 58         return num[rt]; 59      int mid=(ll[rt]+rr[rt])/2; 60     if(mid>=t)return query(rt<<1,s,t); 61     else if(mid<s)return query(rt<<1|1,s,t); 62     else{ 63          Node temp1=query(rt<<1,s,mid); 64          Node temp2=query(rt<<1|1,mid+1,t); 65          Node temp; 66     if(sum[temp1.pre]-sum[s-1]>=sum[temp2.pre]-sum[s-1]) 67         temp.pre=temp1.pre; 68     else 69        temp.pre=temp2.pre; 70     if(sum[t]-sum[temp1.suf-1]>=sum[t]-sum[temp2.suf-1]) 71         temp.suf=temp1.suf; 72     else 73          temp.suf=temp2.suf; 74     long long v1=sum[temp1.vy]-sum[temp1.vx-1]; 75     long long v2=sum[temp2.vy]-sum[temp2.vx-1]; 76     long long v0=sum[temp2.pre]-sum[temp1.suf-1]; 77     if(v1>=v2){ 78        temp.vx=temp1.vx; 79        temp.vy=temp1.vy; 80     } 81     else{ 82          temp.vx=temp2.vx; 83          temp.vy=temp2.vy; 84     } 85     if(v0==sum[temp.vy]-sum[temp.vx-1]){ 86         if(temp1.suf<temp.vx){ 87         temp.vx=temp1.suf; 88         temp.vy=temp2.pre; 89         } 90     } 91      if(v0>sum[temp.vy]-sum[temp.vx-1]){ 92         temp.vx=temp1.suf; 93         temp.vy=temp2.pre; 94     } 95     return temp; 96   } 97 } 98 int main(){ 99     int  cas=0,n,m,l,r;100     long long tp;101     while(~scanf("%d%d",&n,&m)){102           memset(sum,0,sizeof(sum));103         for(int i=1;i<=n;i++){104             scanf("%lld",&tp);105             sum[i]=sum[i-1]+tp;106         }107          build(1,1,n);108         printf("Case %d:\n",++cas);109         for(int i=1;i<=m;i++){110             scanf("%d%d",&l,&r);111             Node ans=query(1,l,r);112             printf("%d %d\n",ans.vx,ans.vy);113         }114     }115 116 }
View Code

 


联系
我们