自动搬运

查看原文

来自洛谷，原作者为

	lilong AFOed on 2025/4/29 || 互关喵qwq

搬运于2025-08-24 23:11:10，当前版本为作者最后更新于2025-02-15 11:53:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}