返回

hdu6047 Maximum Sequence【贪心+线段树】

发布时间:2022-11-28 18:18:52 199
# php

题目链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=6047​​​
题意:给你一个序列a,和一个序列b,让你构造n(an~an+1)个数出来,使得这n个数的和最大,构造出来的数满足ai<={aj-j | bk<=j

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
typedef long long LL;
typedef long long ll;
const int maxn = 5e5+100;
struct node
{
int l,r;
int maxx;
}tree[4*maxn];
int a[maxn],b[maxn];
void push_up(int i)
{
tree[i].maxx = max(tree[i<<1].maxx,tree[i<<1|1].maxx);
}
void build(int i,int l,int r)
{
tree[i].l = l,tree[i].r = r;
tree[i].maxx = 0;
if(l==r)
{
tree[i].maxx = a[l];
return ;
}
int mid = (l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
push_up(i);
}
void update(int i,int pos,int val)
{
int l = tree[i].l;
int r = tree[i].r;
if(l==pos && r==pos)
{
tree[i].maxx = val;
return ;
}
int mid = (l+r)>>1;
if(mid>=pos)
update(i<<1,pos,val);
else
update(i<<1|1,pos,val);
push_up(i);
}
int query(int i,int l,int r)
{
int L = tree[i].l;
int R = tree[i].r;
if(l<=L && R<=r)
return tree[i].maxx;
int mid = (L+R)>>1;
int ans = 0;
if(mid<r)
ans = max(ans,query(i<<1|1,l,r));
if(mid>=l)
ans = max(ans,query(i<<1,l,r));
return ans;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i] -= i;
}
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
sort(b+1,b+n+1);
build(1,1,2*n);
ll ans = 0,r = n;
for(int i = 1;i<=n;i++)
{
ll mm = query(1,b[i],r);
r++;
update(1,r,mm-r);
ans = (ans+mm)%1000000007;
}
printf("%I64d\n",ans);
}
return 0;
}

 

特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(0)
按点赞数排序
用户头像
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争,网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线
下一篇
hdu6108 小C的倍数问题 2022-11-28 17:49:36