오름차순 (JUNGOL 7020)

https://jungol.co.kr/problem/7020

---

아이디어

diff_i를 다음과 같이 정의합시다.

diff_i=a_i^x>=a_i-1인 가장 작은 정수 x

 

그리고 res_i=a_i에 2를 곱하는 횟수 라고 정의합시다. 그러면 res_i=max(0,res_i-1+diff_i)라고 할 수 있습니다. 이떄 구간에 관계없이 diff값은 고정되어있으므로 어떠한 인덱스 i의 res값이 0이라면, i보다 크고 res값이 0이되는 최소의 j를 전처리할 수 있습니다. 물론 그러면 희소 배열을 이용해서 i보다 큰 인덱스중에서 res값이 0이되는 2^k번째로 작은 j를 찾을 수 있습니다.

 

그리고 구간 res값에 0이 없는 구간 [i,j]가 주어지면 solve(i,j)=(diff_j+2*diff_j-1+3*diff_j-2+...+(j-i+1)*diff_i값)을 O(1)에 구할 수 있습니다. 이를 확장시키면 res값이 0인 인덱스 i와 그 다음으로 res값이 0인 인덱스 j에 대하여 [i+1,j-1]의 값들을 모두 갱신시키는 최소 횟수는 solve(i+1,j-1)이 됩니다. 이 값 또한 희소 배열에 넣어주면 하나의 쿼리에 대해 O(log N)에 해결해줄 수 있습니다.

---

아이디어

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#define ll long long
using namespace std;

ll GetDiff(ll before,ll now)
{
    if (before<now)
    {
        ll cnt=0;
        while (before*2<=now)
        {
            cnt++;
            before*=2;
        }
        return -cnt;
    }
    else
    {
        ll cnt=0;
        while (now<before)
        {
            cnt++;
            now*=2;
        }
        return cnt;
    }
}

ll N;
ll Diff[252525]={0};
ll Next[252525][22]={0},val[252525][22]={0}; //Next[i][0]: Diff[i+1]+...+Diff[j]<=0인 최소의 j, 없으면 N+1
ll Suffix[252525]={0},MulSuffix[252525]={0};

ll solve(ll i,ll j)
{
    return (MulSuffix[i]-MulSuffix[j+1]-(N-j)*(Suffix[i]-Suffix[j+1]));
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll Q,i,a,b,before,now;

    cin>>N>>Q>>before;
    for (i=2;i<=N;i++)
    {
        cin>>now;
        Diff[i]=GetDiff(before,now);
        before=now;
    }

    ll sum=0;
    stack <pair <ll,ll> > stk;
    for (i=N;i>=1;i--)
    {
        while (stk.size() && stk.top().first<sum) stk.pop();
        if (stk.size()) Next[i][0]=stk.top().second;
        else Next[i][0]=N+1;

        for (ll j=1;j<=20;j++)
            Next[i][j]=Next[Next[i][j-1]][j-1];

        stk.push({sum,i});
        sum+=Diff[i];
    }
    for (i=N;i>=1;i--)
    {
        Suffix[i]=Suffix[i+1]+Diff[i];
        MulSuffix[i]=MulSuffix[i+1]+Diff[i]*(N-i+1);
    }
    /*
    cout<<"Diff: ";
    for (i=1;i<=N;i++)
    {
        cout<<Diff[i]<<' ';
    }
    cout<<"\nSuffix: ";
    for (i=1;i<=N;i++)
    {
        cout<<Suffix[i]<<' ';
    }
    cout<<"\nMulSuffix: ";
    for (i=1;i<=N;i++)
    {
        cout<<MulSuffix[i]<<' ';
    }
    cout<<"\nNext: ";
    for (i=1;i<=N;i++)
    {
        cout<<Next[i][0]<<' ';
    }
    cout<<"\n";

    for (i=1;i<=N;i++)
    {
        cout<<solve(i+1,Next[i][0]-1)<<' ';
    }
    cout<<"\n";
    */

    for (i=N;i>=1;i--)
    {
        val[i][0]=solve(i+1,Next[i][0]-1);
        for (ll j=1;j<=20;j++)
        {
            Next[i][j]=Next[Next[i][j-1]][j-1];
            val[i][j]=val[i][j-1]+val[Next[i][j-1]][j-1];
        }
    }
    
    for (i=0;i<Q;i++)
    {
        cin>>a>>b;

        ll res=0;
        for (ll j=20;j>=0;j--)
        {
            if (Next[a][j]!=0 && Next[a][j]<=b)
            {
                res+=val[a][j];
                a=Next[a][j];
            }
        }

        //cout<<a<<" -> "<<b<<"\n";
        res+=solve(a+1,b);

        cout<<res<<"\n";
    }
}