P11894 「LAOI-9」Update
題意十分甚至有九分的簡單，但是這個東西似乎是不好做的，我想不出來任何已知的 log 數(shù)據(jù)結(jié)構(gòu)維護它。
突然發(fā)現(xiàn)這個東西增長是緩慢的，我于是乎寫了個程序驗證，最后發(fā)現(xiàn)答案最多是 1e6 左右的一個數(shù)。
果然有的時候觀察答案上下界有奇效。
我們發(fā)現(xiàn)可以使用差分轉(zhuǎn)化為對于每個點跳多少次。
因為這個跳的值域是很小的，而且有 2 次冪的可劃分性，所以我們上倍增就行了。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int MN=2e6+216;
int lg[MN], jump[MN][22];
int n, m, d[MN], a[MN];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
lg[0]=-1; for(int i=1; i<MN; ++i) lg[i]=lg[i>>1]+1;
cin>>n>>m; for(int i=1; i<=n; ++i) cin>>a[i];
for(int i=1; i<MN; ++i) jump[i][0]=i+lg[i];
for(int j=1; j<=21; ++j){
for(int i=1; i<MN; ++i){
jump[i][j]=jump[jump[i][j-1]][j-1];
}
}
for(int i=1; i<=m; ++i){
int l, r; cin>>l>>r;
d[l]++; d[r+1]--;
}
for(int i=1; i<=n; ++i) d[i]+=d[i-1];
for(int i=1; i<=n; ++i){
int res=a[i];
for(int j=0; j<=21; ++j){
if(d[i]&(1<<j)){
res=jump[res][j];
}
}
cout<<res<<' ';
}
return 0;
}
浙公網(wǎng)安備 33010602011771號