题解：P12646 [KOI 2024 Round 1] 升序

_gghack_ · 2025-11-16 17:03:26 · 题解

前言：

竞选最抽象做法。赛场上写了一坤时才写完，只能说这个做法实现起来有点吃操作，而且这个做法很抽象，感觉这题真的不好做。

分析：

首先暴力你肯定是会写的，就是乘以二一直乘到比前面一个数大为止。但是可能存不下这么大的数，所以可以存一下上一个数末尾加了多少个零。

然后更新的时候就分别讨论：设当前为 X_i，上一个是 X_{i-1}，这里都是原序列的数。

• 若 X_i 的二进制位长度小于 X_{i-1}，那么意味着需要补齐和 X_{i-1} 之间差的位数，再补齐 X_{i-1} 多加的零，最后讨论是否多加一个零。

• 若相等，不需要补齐，剩下照搬上面的即可。

• 若大于，则要么 X_{i-1} 加上之前补的零没 X_{i} 大，即不需要补零。要么位数相同但是补完零之后大于 X_{i}，多加一个零。要么位数超过了，直接补到位数相同再讨论是否多加一个零即可。

对每个询问这样做一遍，就是暴力做法。

// 这里从1位置开始，nn指的就是X_{i-1}。
for ( int i = 2 ; i <= n ; ++ i ) {
      int nnb = getbit ( nn ) , ib = getbit ( a[i] ) , pj = 0 ; 
      if ( ib < nnb ) {
          int p = a[i] << ( nnb - ib ) ; 
          if ( p >= nn ) tag[i] = ( nnb - ib ) + nowl ; 
          else tag[i] = ( nnb - ib ) + nowl + 1 ; 
          nowl = ( nnb - ib ) + nowl + ( p < nn ) ; 
      }
      else if ( ib == nnb ) { 
          int p = a[i] ; 
          if ( p >= nn ) tag[i] = nowl ; 
          else tag[i] = nowl + 1 ; 
          nowl += ( p < nn ) ; 
      }
      else {
          int p = a[i] ; 
          if ( nnb + nowl < ib ) nowl = 0 , tag[i] = 0 ; 
          else if ( nnb + nowl == ib ) {
              nn <<= nowl ; 
              if ( p < nn ) nowl = 1 , tag[i] = 1 ; 
              else nowl = 0 , tag[i] = 0 ; 
          }
          else { 
              nowl -= ( ib - nnb ) ;
              nn <<= ( ib - nnb ) ; 
              if ( p < nn ) ++ nowl ; 
              tag[i] = nowl ; 
          }
          nn = a[i] ; 
      }
      sum[i] = sum[i - 1] + tag[i] , nn = a[i] ; 
  }

接下来考虑怎么优化这个过程：发现每次跑一遍有点多余，我们可以考虑只跑一遍整个序列的结果，求出每个数的修改次数。

做完这件事，你惊奇的发现，这个东西貌似可以前缀和相减求答案，因为修改加零貌似会导致后边整体偏移，所以只需要把 [1,l-1] 多加的零扣掉即可，即去掉偏移量。

那么，这是对的吗？好吧其实错了。

对拍发现，你中间可能不需要加那么多零（某个数可能原来很大，不需要怎么修改，然后导致后边的数修改的次数由于它一起变少）。

那么修改一下做法：取出一个严格递减的子序列，然后，对于子序列两个相邻的数在原数列出现的位置 a,b，这里满足 a 位置的操作次数大于 b 位置的操作次数。我们只需要将 [a,b) 的所有位置的操作次数减去 a 位置的操作次数，再求和即可。

好的，那么现在就有了一个很有前途的做法。

考虑怎么优化：发现你从 a 跳跃到 b 的过程，好似一段段链拼接，事实上，如果将找不到 b 的 a 的 b 设置为 n+1，再连边，则会形成一颗以 n+1 为根的树。

看到这里，你想到了什么？当然是树上倍增求答案！只要没跳出询问区间，就一直往后跳，最后不完整的一段单独计算即可。

最终时间复杂度是 \mathcal{O(n\log n)}，但是我不会 \mathcal{O(1)} 求解一个数二进制最高位，所以是 \log V 的，反正能过。

# include <bits/stdc++.h>
# define int long long 
# define pb push_back
using namespace std ;
constexpr int N = 3e5 + 5 ;  
int n , q , a[N] , cnt[N] , sum[N] , tag[N] , s[N] , nxt[N] ;
int find ( int x ) { return s[x] == x ? x : s[x] = find ( s[x] ) ; } 
void merge ( int a , int b ) {
    int fx = find ( a ) , fy = find ( b ) ; 
    if ( fx == fy ) return ; 
    s[fx] = fy ; return ; 
}
int getbit ( int x ) {
    for ( int j = 32 ; ~ j ; -- j ) 
    if ( x >> j & 1 ) return j ; 
}
int st[N][30] , faa[N][30] ; 
vector < int > g[N] ; 
void dfs ( int u , int fa ) {
    faa[u][0] = fa ; 
    st[u][0] = ( sum[nxt[u] - 1] - sum[u - 1] ) - tag[u] * ( nxt[u] - 1 - u + 1 ) ; 
    for ( int j = 1 ; j < 19 ; ++ j ) 
    faa[u][j] = faa[faa[u][j - 1]][j - 1] ,
    st[u][j] = st[faa[u][j - 1]][j - 1] + st[u][j - 1] ; 
    for ( auto x : g[u] ) {
        if ( x == fa ) continue ; 
        dfs ( x , u ) ; 
    }
    return ; 
}
signed main () {
    ios::sync_with_stdio ( false ) , cin.tie ( 0 ) , cout.tie ( 0 ) ;
    cin >> n >> q ; for ( int i = 1 ; i <= n ; ++ i ) cin >> a[i] , s[i] = i ; 
    int nn = a[1] , nowl = 0 ;
    for ( int i = 2 ; i <= n ; ++ i ) {
        int nnb = getbit ( nn ) , ib = getbit ( a[i] ) , pj = 0 ; 
        if ( ib < nnb ) {
            int p = a[i] << ( nnb - ib ) ; 
            if ( p >= nn ) tag[i] = ( nnb - ib ) + nowl ; 
            else tag[i] = ( nnb - ib ) + nowl + 1 ; 
            nowl = ( nnb - ib ) + nowl + ( p < nn ) ; 
        }
        else if ( ib == nnb ) { 
            int p = a[i] ; 
            if ( p >= nn ) tag[i] = nowl ; 
            else tag[i] = nowl + 1 ; 
            nowl += ( p < nn ) ; 
        }
        else {
            int p = a[i] ; 
            if ( nnb + nowl < ib ) nowl = 0 , tag[i] = 0 ; 
            else if ( nnb + nowl == ib ) {
                nn <<= nowl ; 
                if ( p < nn ) nowl = 1 , tag[i] = 1 ; 
                else nowl = 0 , tag[i] = 0 ; 
            }
            else { 
                nowl -= ( ib - nnb ) ;
                nn <<= ( ib - nnb ) ; 
                if ( p < nn ) ++ nowl ; 
                tag[i] = nowl ; 
            }
            nn = a[i] ; 
        }
        sum[i] = sum[i - 1] + tag[i] , nn = a[i] ; 
    }
    stack < int > stk ; stk.push ( n + 1 ) ; 
    for ( int i = n ; i >= 1 ; -- i ) {
        while ( !stk.empty () && tag[stk.top()] > tag[i] ) stk.pop () ; 
        if ( !stk.empty() ) nxt[i] = stk.top() ;
        stk.push ( i ) ; 
    }
    for ( int i = 1 ; i <= n ; ++ i ) g[i].pb ( nxt[i] ) , g[nxt[i]].pb ( i ) ;
    dfs ( n + 1 , n + 1 ) ; 
    while ( q-- ) {
        int l , r ; cin >> l >> r ; 
        int ccc = 0 ;
        for ( int j = 18 ; ~ j ; -- j ) {
            if ( faa[l][j] > r ) continue ; 
            ccc += st[l][j] , l = faa[l][j] ; 
        }
        ccc += sum[r] - sum[l - 1] - tag[l] * ( r - l + 1 ) ; 
        cout << ccc << '\n' ;
    }
    return 0 ;
}   
// 你妈的mivik的神力就是这个套路
// ok 单调栈跳出来了，尼玛活了