BZOJ4415: [Shoi2013]发牌 树状数组+二分

Description

假设一开始,荷官拿出了一副新牌,这副牌有N张不同的牌,编号依次为1到N。由于是新牌,所以牌是按照顺序排好的,从牌库顶开始,依次为1, 2,……直到N,N号牌在牌库底。为了发完所有的牌,荷官会进行N次发牌操作,在第i次发牌之前,他会连续进行R_i次销牌操作,R_i由输入给定。请问最后玩家拿到这副牌的顺序是什么样的?

举个例子,假设N = 4,则一开始的时候,牌库中牌的构成顺序为{1, 2, 3, 4}。

假设R1=2,则荷官应该连销两次牌,将1和2放入牌库底,再将3发给玩家。目前牌库中的牌顺序为{4, 1, 2}。

假设R2=0,荷官不需要销牌,直接将4发给玩家,目前牌库中的牌顺序为{1,2}。

假设R3=3,则荷官依次销去了1, 2, 1,再将2发给了玩家。目前牌库仅剩下一张牌1。

假设R4=2,荷官在重复销去两次1之后,还是将1发给了玩家,这是因为1是牌库中唯一的一张牌。

Input

第1行,一个整数N,表示牌的数量。第2行到第N + 1行,在第i + 1行,有一个整数R_i, 0≤R_i<N

Output

第1行到第N行:第i行只有一个整数,表示玩家收到的第i张牌的编号。

Sample Input

4
2
0
3
2

Sample Output

3
4
2
1

HINT

N<=70万

Solution

提供一个跑的贼慢的做法

在树状数组上二分

复杂度$O(nlognlogn)$

和权值线段树差不多的思路,但是好写啊

#include <bits/stdc++.h>

using namespace std ;

inline int lowbit( int x ) {
return x & -x ;
} #define N 700010 int n ;
int c[ N ] ; void add( int x , int val ) {
for( int i = x ; i <= n ; i += lowbit( i ) )
c[ i ] += val ;
} int query( int x ) {
int ans = ;
for( int i = x ; i ; i -= lowbit( i ) ) ans += c[ i ] ;
return ans ;
} int find( int x ) {
int l = , len = n ;
while( len ) {
int mid = l +( len >> ) ;
if( query( mid ) < x ) {
l = mid + ;
len = len - ( len >> | ) ;
} else len = len >> ;
}
return l ;
} int main() {
int now = ;
scanf( "%d" , &n ) ;
for( int i = ; i <= n ; i ++ ) add( i , ) ;
for( int i = ; i <= n ; i ++ ) {
int t ;
scanf( "%d" , &t ) ;
t = t % ( n - i + ) ;
now = ( now + t ) % ( n - i + ) ;
t = find( now + ) ;
printf( "%d\n" , t ) ;
add( t , - ) ;
}
return ;
}
上一篇:每日英语:The Risks of Big Data for Companies


下一篇:C++ 字符串指针与字符串数组