CodeForces1208D
也是挺吓人的一道题,我一开始以为给的是每个数字前比它小的数字有几个,然后我就苦苦看不懂样例…
然后我冷静了一下,重新分析,读题,发现给的是每个数字前比它小的数字的和.
这下看懂样例了,可咋做啊?
如果你仔细思考一下,你会发现有个特殊的存在$1$,它无论在哪一个位置,给定的数字一定是$0$.
但$0$可能并不只有一个,那么我们就要考虑哪一个$0$才应该是$1$.
你考虑有两个$0$,一个的位置是$i$,另一个是$j$,且满足$i < j$.
这时候,如果说$i$这个位置本来是$1$,那么给定的$j$这个位置的数字一定不会是$0$,与题设矛盾,所以一定是$j$是$1$.
那么我们可以把这个结论推广为:有多个$0$存在时,最左边的$0$一定是当前最小的数字.
为什么不直接说是$1$而说最小的数字呢?看完下面你就明白了.
那么我们继续推广,当确定了$1$的时候,就相当于$2$的地位和之前的$1$一样,于是此时,最右边的$0$应当是$2$,以此类推.
至于最右边的$1$,随便找个什么数据结构维护一下就好了.
我这里是采用了线段树,维护区间最小值,同时维护最小值的位置.
至于怎么找最右边的也很简单,每次遇到相等的就右边走就行了.
$Code:$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
template < class T >
inline T read () {
T x = 0 , f = 1 ; char ch = getchar () ;
while ( ch < '0' || ch > '9' ) {
if ( ch == '-' ) f = - 1 ;
ch = getchar () ;
}
while ( ch >= '0' && ch <= '9' ) {
x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
ch = getchar () ;
}
return f * x ;
}
const int N = 2e5 + 100 ;
const int inf = 1e12 ;
struct seg { int left , right , data , pos , tag ; } t[(N<<2)] ;
int n , v[N] ;
inline void pushup (int rt) {
t[rt].data = min ( t[ls].data , t[rs].data ) ;
if ( t[ls].data < t[rs].data ) t[rt].pos = t[ls].pos ;
else t[rt].pos = t[rs].pos ;
return ;
}
inline void build (int rt , int l , int r) {
t[rt].left = l ; t[rt].right = r ; t[rt].tag = 0 ;
if ( l == r ) { t[rt].data = v[l] ; t[rt].pos = l ; return ; }
build ( ls , l , mid ) ; build ( rs , mid + 1 , r ) ;
pushup ( rt ) ; return ;
}
inline void pushdown (int rt) {
t[ls].tag += t[rt].tag ; t[rs].tag += t[rt].tag ;
t[ls].data += t[rt].tag ; t[rs].data += t[rt].tag ;
t[rt].tag = 0 ; return ;
}
inline pii query (int rt , int ll , int rr) {
int l = t[rt].left , r = t[rt].right ;
if ( ll == l && r == rr ) return { t[rt].data , t[rt].pos } ;
if ( t[rt].tag != 0 ) pushdown ( rt ) ;
if ( rr <= mid ) return query ( ls , ll , rr ) ;
else if ( ll > mid ) return query ( rs , ll , rr ) ;
else {
pii lans = query ( ls , ll , mid ) ;
pii rans = query ( rs , mid + 1 , rr ) ;
if ( lans.X < rans.X ) return lans ;
else return rans ;
}
}
inline void update (int rt , int ll , int rr , int val) {
int l = t[rt].left , r = t[rt].right ;
if ( ll == l && r == rr ) { t[rt].tag += val ; t[rt].data += val ; return ; }
if ( t[rt].tag != 0 ) pushdown ( rt ) ;
if ( rr <= mid ) update ( ls , ll , rr , val ) ;
else if ( ll > mid ) update ( rs , ll , rr , val ) ;
else { update ( ls , ll , mid , val ) ; update ( rs , mid + 1 , rr , val ) ; }
pushup ( rt ) ; return ;
}
signed main (int argc , char * argv[] ) {
n = rint () ; rep ( i , 1 , n ) v[i] = rint () ;
build ( 1 , 1 , n ) ; int idx = 0 ;
while ( true ) {
pii tmp = query ( 1 , 1 , n ) ;
v[tmp.Y] = ++ idx ;
update ( 1 , tmp.Y , n , - idx ) ;
update ( 1 , tmp.Y , tmp.Y , inf ) ;
if ( idx >= n ) break ;
}
rep ( i , 1 , n ) printf ("%I64d " , v[i] ) ;
return 0 ;
}