HU 6047-M-Mximm Sequence（2017多校リーグC題）

【タイトルソース】：http://acm.hdu.edu.cn/showproblem.php?pid=6047 【題意】シーケンスaとシーケンスbを与え、全部n項があり、後n項の最大和を求めます。そして、a[x]=max(a[j]-j)、（b[k]==jはiより小さい）という関係を与えられました。b[k]は一回しか使えないので、a[j]-jという式の最大値を何度も利用して、どうやって複数回利用することができますか？a[j]の値に対するb[k]の影響を考慮しなければならない。例えば、例：8 11 8 5 3 1 4ここで、第1歩はb配列の中の2を取るので、a[2]….a[4]は全部使えますが、もちろん最大値をとるので、11-2を取り出します。つまりa[5]=9、第2部はb配列の中の1を取ります。この時、a[1].a[5]は全部使えます。もちろん、a[5]を加えましたが、a[2]は依然として最大です。つまり、最大の値をできるだけ多く利用することが、本題を解決する鍵となるのです。

//             ，      j      b[k]
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int mod=1e9+7;
typedef long long LL;
int b[250000+10];
int w[250000+10];
struct pp
{
    int index;
    int ans;
}a[250000+10];
struct cmp
{
    bool operator()(pp s,pp t)
    {
        if(s.ans==t.ans)
            return s.index>t.index;
        return s.ansvector,cmp> q;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        while(!q.empty()) q.pop();
        for(int i=1;i<=n;i++)
        {
            a[i].index=i;
            scanf("%d",&a[i].ans);
            a[i].ans-=i;
            q.push(a[i]);
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        memset(w,0,sizeof(w));
        for(int i=1;i<=n;i++)
            w[b[i]]++;
        LL sum=0;
        int pos=n;
        int d_m=0;
        while(1)
        {
            pp T_T=q.top();
            q.pop();
            LL num=0;
            if(T_T.index<=d_m)  continue;
            else
            {
                for(int i=d_m+1;i<=T_T.index;i++)
                    num+=w[i];
                d_m=T_T.index;
            }
            sum+=(num*T_T.ans)%mod;
            sum%=mod;
            pp x_s;
            x_s.index=pos+1;
            x_s.ans=T_T.ans-pos-1;
            q.push(x_s);
            pos+=num;
            if(pos==2*n) break;
        }
        printf("%lld
",sum);
    }
}