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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #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
                
                 #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 ;}

转载于:https://www.cnblogs.com/Equinox-Flower/p/11447329.html

你可能感兴趣的文章