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