CodeForces1208D-蒲公英云

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:\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back #define ls ( rt << 1 ) #define rs ( rt << 1 | 1 ) #define mid ( ( l + r ) >> 1 )   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 ; }