首页 > 代码库 > cogs 775 山海经

cogs 775 山海经

2024-11-20 02:39:02   202人阅读

775. 山海经

★★★   输入文件：hill.in   输出文件：hill.out   简单对比
时间限制：1 s   内存限制：128 MB

【问题描述】

“南山之首日鹊山。其首日招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名日祝余，食之不饥……又东三百里，日堂庭之山，多棪木，多白猿，多水玉，多黄金。

又东三百八十里，日猨翼之山，其中多怪兽，水多怪鱼，多白玉，多蝮虫，多怪蛇，名怪木，不可以上。……”

《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。某天，你的地理老师想重游《山海经》中的路线，为了简化问题，老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第a座山到第b座山的中间某段路(i,j)。能使他感到最满意，即(i,j)这条路上所有山的喜恶度之和是（c,d）(a≤c≤d≤b)最大值。于是老师便向你请教，你能帮助他吗?值得注意的是，在《山海经》中，第i座山只能到达第i+1座山。

 

【输入】

输入第1行是两个数，n，m，2≤n≤100000，1≤m≤100000，n表示一共有n座山，m表示老师想查询的数目。

第2行是n个整数，代表n座山的喜恶度，绝对值均小于10000。

以下m行每行有a，b两个数，1≤a≤j≤b≤m，表示第a座山到第b座山。

 

【输出】

一共有m行，每行有3个数i，j，s，表示从第i座山到第j座山总的喜恶度为s。显然，对于每个查询，有a≤i≤j≤b，如果有多组解，则输出i最小的，如果i也相等，则输出j最小的解。

 

【输入样例】

5 3

5 -6 3 -1 4

1 3

1 5

5 5

【输出样例】

1 1 5

3 5 6

5 5 4

solution：

　　　　这个题就是一个裸地线段树，只不过在维护的时候有一些麻烦。需要维护有以下几个域，最大左子串（一定由区间最左端开始），右子串（一定由区间右子串开始），中间的字串（左右端点一点不在区间的左右端点），整个区间的sum，以及对应前三个域的左右边界，pushup的时候把以上几个变量更新在更新以下对应的左右边界即可，但要注意的是顺序，此题要求i、j都最小，在最后输出时先判断左子串，然后sum，然后mid，然后右子串。

　　　　

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define inf 0x7fffffff
  7 int n,m;
  8 struct node {
  9     int sum,l,r,mid;
 10     int l1,r1,l2,r2,l3,r3;
 11     int ll,rr;
 12     node() {
 13         sum=l=r=mid=-inf;
 14     }
 15 } tree[4*100001],null;
 16 int a[100005];
 17 void pushup(int x) {
 18     tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
 19     if(tree[x<<1].l>=tree[x].l) {
 20         tree[x].l=tree[x<<1].l;
 21         tree[x].l1=tree[x<<1].l1;
 22         tree[x].r1=tree[x<<1].r1;
 23     }
 24     if(tree[x<<1].sum>tree[x].l) {
 25         tree[x].l=tree[x<<1].sum;
 26         tree[x].l1=tree[x<<1].ll;
 27         tree[x].r1=tree[x<<1].rr;
 28     }
 29     if(tree[x<<1].sum+tree[x<<1|1].l>tree[x].l) {
 30         tree[x].l=tree[x<<1].sum+tree[x<<1|1].l;
 31         tree[x].l1=tree[x<<1].ll;
 32         tree[x].r1=tree[(x<<1|1)].r1;
 33     }
 34     if(tree[x<<1|1].sum+tree[x<<1].r>=tree[x].r) {
 35         tree[x].r=tree[x<<1|1].sum+tree[x<<1].r;
 36         tree[x].l2=tree[x<<1].l2;
 37         tree[x].r2=tree[x<<1|1].rr;
 38     }
 39     if(tree[x<<1|1].sum>tree[x].r) {
 40         tree[x].r=tree[x<<1|1].sum;
 41         tree[x].l2=tree[x<<1|1].ll;
 42         tree[x].r2=tree[x<<1|1].rr;
 43     }
 44     if(tree[x<<1|1].r>tree[x].r) {
 45         tree[x].r=tree[x<<1|1].r;
 46         tree[x].l2=tree[(x<<1|1)].l2;
 47         tree[x].r2=tree[x<<1|1].r2;
 48     }
 49     if(tree[x<<1].mid>=tree[x].mid) {
 50         tree[x].mid=tree[x<<1].mid;
 51         tree[x].l3=tree[x<<1].l3;
 52         tree[x].r3=tree[x<<1].r3;
 53     }
 54     if(tree[x<<1].r>tree[x].mid) {
 55         tree[x].mid=tree[x<<1].r;
 56         tree[x].l3=tree[x<<1].l2;
 57         tree[x].r3=tree[x<<1].r2;
 58     }
 59     if(tree[x<<1|1].l+tree[x<<1].r>tree[x].mid) {
 60         tree[x].mid=tree[x<<1|1].l+tree[x<<1].r;
 61         tree[x].l3=tree[x<<1].l2;
 62         tree[x].r3=tree[x<<1|1].r1;
 63     }
 64     if(tree[x<<1|1].l>tree[x].mid) {
 65         tree[x].mid=tree[x<<1|1].l;
 66         tree[x].l3=tree[x<<1|1].l1;
 67         tree[x].r3=tree[x<<1|1].r1;
 68     }
 69     if(tree[x<<1|1].mid>tree[x].mid) {
 70         tree[x].mid=tree[x<<1|1].mid;
 71         tree[x].l3=tree[x<<1|1].l3;
 72         tree[x].r3=tree[x<<1|1].r3;
 73     }
 74 }
 75 void build(int i,int le,int ri) {
 76     if(le==ri) {
 77         tree[i].sum=tree[i].l=tree[i].r=tree[i].mid=a[le];
 78         tree[i].ll=tree[i].rr=le;
 79         tree[i].l1=tree[i].r1=tree[i].l2=tree[i].r2=tree[i].l3=tree[i].r3=le;
 80         return ;
 81     }
 82     tree[i].ll=le;
 83     tree[i].rr=ri;
 84     int mid=le+ri>>1;
 85     build(i<<1,le,mid);
 86     build(i<<1|1,mid+1,ri);
 87     pushup(i);
 88 }
 89 node query(int i,int L,int R,int l,int r) {
 90     if(l>r) {
 91         return null;
 92     }
 93     if(l<=L&&R<=r) {
 94         return tree[i];
 95     }
 96     int mid=L+R>>1;
 97     node ans1,ans2;
 98     if(l<=mid) {
 99         ans1=query(i<<1,L,mid,l,r);
100     }
101     if(r>mid) {
102         ans2=query(i<<1|1,mid+1,R,l,r);
103     }
104     node ans;
105     if(ans1.sum<=-2147483645&&ans2.sum<=-2147483645) {
106         return ans1;
107     }
108     if(ans1.sum<=-2147483645) {
109         return ans2;
110     }
111     if(ans2.sum<=-2147483645) {
112         return ans1;
113     }
114     ans.sum=ans1.sum+ans2.sum;
115     if(ans1.l>=ans.l) {
116         ans.l=ans1.l;
117         ans.l1=ans1.l1;
118         ans.r1=ans1.r1;
119     }
120     if(ans1.sum>ans.l) {
121         ans.l=ans1.sum;
122         ans.l1=ans1.ll;
123         ans.r1=ans1.rr;
124     }
125     if(ans1.sum+ans2.l>ans.l) {
126         ans.l=ans1.sum+ans2.l;
127         ans.l1=ans1.ll;
128         ans.r1=ans2.r1;
129     }
130     if(ans2.sum+ans1.r>=ans.r) {
131         ans.r=ans2.sum+ans1.r;
132         ans.l2=ans1.l2;
133         ans.r2=ans2.rr;
134     }
135     if(ans2.sum>ans.r) {
136         ans.r=ans2.sum;
137         ans.l2=ans2.ll;
138         ans.r2=ans2.rr;
139     }
140     if(ans2.r>ans.r) {
141         ans.r=ans2.r;
142         ans.l2=ans2.l2;
143         ans.r2=ans2.r2;
144     }
145     if(ans1.mid>=ans.mid) {
146         ans.mid=ans1.mid;
147         ans.l3=ans1.l3;
148         ans.r3=ans1.r3;
149     }
150     if(ans1.r>ans.mid) {
151         ans.mid=ans1.r;
152         ans.l3=ans1.l2;
153         ans.r3=ans1.r2;
154     }
155     if(ans2.l+ans1.r>ans.mid) {
156         ans.mid=ans2.l+ans1.r;
157         ans.l3=ans1.l2;
158         ans.r3=ans2.r1;
159     }
160     if(ans2.l>ans.mid) {
161         ans.mid=ans2.l;
162         ans.l3=ans2.l1;
163         ans.r3=ans2.r1;
164     }
165     if(ans2.mid>ans.mid) {
166         ans.mid=ans2.mid;
167         ans.l3=ans2.l3;
168         ans.r3=ans2.r3;
169     }
170     ans.ll=min(ans1.ll,ans2.ll);
171     ans.rr=max(ans1.rr,ans2.rr);
172     return ans;
173 }
174 int main() {
175     freopen("hill.in","r",stdin);
176     freopen("hill.out","w",stdout);
177     scanf("%d%d",&n,&m);
178     for(int i=1; i<=n; i++) {
179         scanf("%d",&a[i]);
180     }
181     build(1,1,n);
182     for(int i=1,a,b; i<=m; i++) {
183         scanf("%d%d",&a,&b);
184         node ans=query(1,1,n,a,b);
185         if(ans.l>=ans.sum&&ans.l>=ans.r&&ans.l>=ans.mid) {
186             printf("%d %d %d\n",ans.l1,ans.r1,ans.l);
187             continue;
188         }
189         if(ans.sum>=ans.l&&ans.sum>=ans.r&&ans.sum>=ans.mid) {
190             printf("%d %d %d\n",ans.ll,ans.rr,ans.sum);
191             continue;
192         }
193         if(ans.mid>=ans.sum&&ans.mid>=ans.l&&ans.mid>=ans.r) {
194             printf("%d %d %d\n",ans.l3,ans.r3,ans.mid);
195             continue;
196         }
197         if(ans.r>=ans.sum&&ans.r>=ans.l&&ans.r>=ans.mid) {
198             printf("%d %d %d\n",ans.l2,ans.r2,ans.r);
199             continue;
200         }
201     }
202     return 0;
203 }

 

cogs 775 山海经


联系
我们