第一次寫題解，求贊求關注qwq
原題地址~
為了更好的理解題意我們可以看一下這個模擬：
假設一開始有 5 5 5 張牌，初始順序分別是 1 , 2 , 3 , 4 , 5 1,2,3,4,5 1,2,3,4,5。
第 1 1 1 次把最頂層的 1 1 1 依次拿到下面，順序變成 2 , 3 , 4 , 5 , 1 2,3,4,5,1 2,3,4,5,1；接著把最上面的 2 2 2 拿走，第一輪操作后的數(shù)列為 3 , 4 , 5 , 1 3,4,5,1 3,4,5,1。
第 2 2 2 次把最頂層的 3 , 4 3,4 3,4 依次拿到下面，順序變成 5 , 1 , 3 , 4 5,1,3,4 5,1,3,4；接著把最上面的 5 , 1 5,1 5,1 拿走，第一輪操作后的數(shù)列為 3 , 4 3,4 3,4。
最后一次需要進行 3 3 3 次操作，可是只有 2 2 2 個數(shù)，怎么辦呢？把 3 , 4 3,4 3,4 依次拿到下面三次，也就是 3 , 4 → 4 , 3 → 3 , 4 → 4 , 3 3,4 \rightarrow 4,3 \rightarrow 3,4 \rightarrow 4,3 3,4→4,3→3,4→4,3 。
最后的數(shù)列為 2 , 5 , 1 , 4 , 3. 2,5,1,4,3. 2,5,1,4,3.
而題目想讓你求的是使最后的數(shù)列單調上升，即最后的數(shù)列為 1 , 2 , 3 , 4 , 5 1,2,3,4,5 1,2,3,4,5.
我們再用樣例來測試一下， n = 5 n = 5 n=5，初始順序為 3 , 1 , 4 , 5 , 2 3,1,4,5,2 3,1,4,5,2.
第 1 1 1 次把最頂層的 3 3 3 依次拿到下面，順序變成 1 , 4 , 5 , 2 , 3 1,4,5,2,3 1,4,5,2,3；接著把最上面的 1 1 1 拿走，第一輪操作后的數(shù)列為 4 , 5 , 2 , 3 4,5,2,3 4,5,2,3。
第 2 2 2 次把最頂層的 4 , 5 4,5 4,5 依次拿到下面，順序變成 2 , 3 , 4 , 5 2,3,4,5 2,3,4,5；接著把最上面的 2 , 3 2,3 2,3 拿走，第一輪操作后的數(shù)列為 4 , 5 4,5 4,5。
最后一次把 4 , 5 4,5 4,5 依次拿到下面，也就是 4 , 5 → 5 , 4 → 4 , 5 4,5 \rightarrow 5,4 \rightarrow 4,5 4,5→5,4→4,5 。
最后的數(shù)列剛好為 1 , 2 , 3 , 4 , 5 1,2,3,4,5 1,2,3,4,5，符合題意。XD
理解了題意，我們看數(shù)據范圍：
n
≤
2
×
1
0
4
n \le 2 \times 10^4
n≤2×104 ，另一篇題解用
O
(
能
過
)
O(能過)
O(能過) 的暴力，很明顯運用了區(qū)間求和的操作，這時候我們會想到 前綴和/樹狀數(shù)組/線段樹。
因為我有強迫癥剛學樹狀數(shù)組，所以我就自然要用求和復雜度為
O
(
log
?
n
)
\mathcal{O} (\operatorname{log}n)
O(logn) 的樹狀數(shù)組解決啦~
附贈樹狀數(shù)組板子：
重慶分公司
重慶分公司
// P.S:f為樹狀數(shù)組
int lowbit(int i){return i&-i;
}
int getsum(int n){int ans = 0;
while(n>0){ans+=f[n];
n-=lowbit(n);
}
return ans;
}
void change(int i,int d,int n){while(i<=n){f[i]+=d;
i+=lowbit(i);
}
}通過題目得知最后的序列是單調上升的，還原時自然會想到復雜度為 O ( log ? n ) \mathcal{O}(\operatorname{log} n) O(logn) 的二分來處理前綴和。
int BinarySearch(int val,int n){int l = 1,r = n;
while(lint mid = (l+r)>>1;
if(getsum(mid)>=val) r = mid;
else l = mid+1;
}
return l;
} 所以這種做法總的時間復雜度是 O ( n l o g 2 ? n ) \mathcal{O}(n \operatorname{log^2} n) O(nlog2n)。
最后就是核心代碼啦，注釋都在代碼里。
void work(int n){memset(f,0,sizeof f);//多測不清空，抱靈兩行淚
int p = 0,c = n,pl,pr,step;//p是當前處理的元素（就是指針）
for(int i = 1;i<=n;i++){change(i,1,n);//將初始的1,2,3...n存入到樹狀數(shù)組中
}
for(int i = 1;i<=n;i++){step = (i+1)%c;//處理步數(shù)比元素多的情況
pl = getsum(p),pr = c-pl;//需要更改的范圍
int nxt;
nxt = (step<=pr)?step+pl:step-pr;二分范圍
if(nxt==0) nxt = c;
p = BinarySearch(nxt,n);
ans[p] = i;//填入答案
change(p,-1,n);//填完了~
c--;
}
for(int i = 1;i<=n;i++) cout<代碼就不提供了，主函數(shù)沒有什么東西了qwq
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
