【多校训练2】HDU 6047 Maximum Sequence

http://acm.hdu.edu.cn/showproblem.php?pid=6047

【题意】

• 给定两个长度为n的序列a和b,现在要通过一定的规则找到可行的a_n+1.....a_2n,求sum{a_n+1.....a_2n}的最大值
• 每次从序列b中选择一个数bk,那么构造的ai就是max{aj -j},其中bk<=j<i
• 每个bk最多用一次

【思路】

• 首先我们需要的是aj-j
• 可以贪心，即对于当前要构造的数ai,尽可能找bk使得能够取得最大的aj-j
• 线段树区间查询最优值+单点更新
• 把b排个序，对于每个b查询b[i]~n+i-1的最大值

【Accepted】

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<algorithm>

 #include<cmath>

 #define lson (i<<1)

 #define rson (i<<1|1)

 #include<vector>

 #include<map>

 using namespace std;

 const int maxn=(25e4+)*;

 typedef long long ll;

 const ll mod=1e9+;

 const int inf=0x3f3f3f3f;

 long long val[maxn];

 int a[maxn];

 int b[maxn];

 int n;

 struct Seg

 {

     int l,r,lazy,val;

 }tree[maxn<<];

 void push_up(int i)

 {

     tree[i].val=max(tree[lson].val,tree[rson].val);

 }

 void push_down(int i)

 {

     if(tree[i].lazy==-)

     {

         return;

     }

     tree[lson].lazy=tree[lson].val=tree[i].lazy;

     tree[rson].lazy=tree[rson].val=tree[i].lazy;

     tree[i].lazy=-;

 }

 void Build(int l,int r,long long i=)

 {

     tree[i].l=l;

     tree[i].r=r;

     tree[i].lazy=-;

     if(l==r)

     {

         tree[i].val=val[l];

         return;

     }

     push_down(i);

     int mid=(tree[i].l+tree[i].r)>>;

     Build(l,mid,lson);

     Build(mid+,r,rson);

     push_up(i);

 }

 int Query(int l,int r,int i=)

 {

     if(tree[i].l==l&&tree[i].r==r)

     {

         return tree[i].val;

     }

     push_down(i);

     int mid=(tree[i].l+tree[i].r)>>;

     if(r<=mid)

     {

         return Query(l,r,lson);

     }

     else if(l>mid)

     {

         return Query(l,r,rson);

     }

     else

     {

         return max(Query(l,mid,lson),Query(mid+,r,rson));

     }

 }

 void Setval(int l,int r,int x,int i=)

 {

     if(tree[i].l==l&&tree[i].r==r)

     {

         tree[i].lazy=tree[i].val=x;

         return;

     }

     push_down(i);

     int mid=(tree[i].l+tree[i].r)>>;

     if(r<=mid)

     {

         Setval(l,r,x,lson);

     }

     else if(l>mid)

     {

         Setval(l,r,x,rson);

     }

     else

     {

         Setval(l,mid,x,lson);

         Setval(mid+,r,x,rson);

     }

     push_up(i);

  }

 int main()

 {

     while(~scanf("%d",&n))

     {

         for(int i=;i<=*n;i++)

         {

             val[i]=-inf;

         }

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

             val[i]=a[i]-i;

         }

         Build(,*n);

         for(int i=;i<=n;i++)

         {

             scanf("%d",&b[i]);

         }

         sort(b+,b++n);

         ll ans=;

         b[]=;

         for(int i=;i<=n;i++)

         {

             int mmax=Query(b[i],n+i-);

             ans=(ans+(ll)mmax)%mod;

             Setval(n+i,n+i,mmax-(n+i));

         }

         cout<<ans<<endl;

     }

     return ;

  }

线段树区间查询最优值+单点修改