「LAOI-9」Update

· · 题解

A 性质

首先使用差分维护每个 a_i 的操作次数。

不难发现由于数的种类很少，因此直接用一个数组记录每个数 i 操作 j 次后的值。预处理完后，记 A 为 a_i 的最大值，则时间复杂度 O(mA)。

for( int i = 1 ; i <= 100 ; i ++ )
{
    f[i][0] = i;
    for( int j = 1 ; j <= m ; j ++ )
        f[i][j] = f[i][j - 1] + lg[f[i][j - 1]];
}

正解

其实我们可以从 A 性质出发继续思考。当值域达到 10^5 时，我们需要寻找一个能平衡时间空间的做法。如果一次能够完成不止一次操作，那么运行效率将得到提高。不难想到可以倍增，记 f_{i,j} 表示从 i 进行 2^j 次操作得到的数，则 f 是好预处理的。同时 i 的上界也是确定的，由于 10^5 \times 20 < 2^{21}，故 \log_2i 不超过 20，即修改后的 i 不超过 2.1 \times 10^6。剩下的就不难了。

令 A=2.1 \times 10^6，则总时间复杂度 O(n+m+(n+A)\log m)，可以通过。

#include <iostream>
#include <cstdio>

using namespace std;

int N = 2100010;
int n,m,a[200001],l,r,d[200001],f[2400001][19],lg[2400001];

int g( int x , int y )
{
    for( int i = 18 ; i >= 0 ; i -- )
        if( y & ( 1 << i ) )
            x = f[x][i];
    return x;
}

int read( void )
{
    int x = 0,f = 1;
    char ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = x * 10 + ch - '0',ch = getchar();
    return x * f;
}

void write( int x )
{
    if( x <= 9 )
    {
        putchar( x + '0' );
        return;
    }
    write( x / 10 );
    putchar( x % 10 + '0' );
    return;
}

int main()
{
    cin >> n >> m;
    lg[1] = 0,f[1][0] = 1;
    for( int i = 2 ; i <= N ; i ++ )
        lg[i] = lg[i >> 1] + 1,f[i][0] = i + lg[i];
    for( int j = 1 ; j <= 18 ; j ++ )
        for( int i = 1 ; i <= N ; i ++ )
            f[i][j] = f[f[i][j - 1]][j - 1];
    for( int i = 1 ; i <= n ; i ++ )
        a[i] = read();
    while( m -- )
    {
        l = read(),r = read();
        d[l] ++,d[r + 1] --;
    }
    for( int i = 1 ; i <= n ; i ++ )
    {
        d[i] += d[i - 1];
        write( g( a[i] , d[i] ) );
        putchar( ' ' );
    }
    return 0;
}

有一种实际效率更高的解法。大致思路是考虑当前需要多少次操作才能使当前 \lfloor \log_2 a_i \rfloor 增加 1，显然这个操作次数为 \lceil \dfrac{2^{\lfloor \log_2 a_i \rfloor+1}-a_i}{\lfloor \log_2 a_i \rfloor} \rceil。将其与剩余操作次数比较并计算即可，注意特判 \lfloor \log_2 a_i \rfloor=0 的情况。时间复杂度也是线性对数。以下给出这种解法的实现。

#include <iostream>
#include <cstdio>
#include <cmath>
#define N 200001

using namespace std;

int n,a[N],d[N],m,l,r,k,tt;

int main()
{
    cin >> n >> m;
    for( int i = 1 ; i <= n ; i ++ )
        cin >> a[i];
    while( m -- )
    {
        cin >> l >> r;
        d[l] ++,d[r + 1] --;
    }
    for( int i = 1 ; i <= n ; i ++ )
    {
        d[i] += d[i - 1];
        m = d[i];
        k = int( log2( a[i] ) );
        if( k == 0 )
        {
            cout << a[i] << ' ';
            continue;
        }
        while( m )
        {
            tt = ( ( 1 << ( k + 1 ) ) - a[i] ) / k;
            if( ( ( 1 << ( k + 1 ) ) - a[i] ) % k ) tt ++;
            if( tt >= m )
            {
                a[i] += m * k;
                m = 0;
            }
            else
            {
                a[i] += tt * k;
                m -= tt;
            }
            k ++;
        }
        cout << a[i] << ' ';    
    }
    return 0;
}