分块3

· · 个人记录

基础

今天的题目对于分快来说，都需要进行一些优化。比如说在二分时对于全部大或者全部小时的优化；二分上下界优化等等。

分块的复杂度是整块的个数加上 2\sqrt{n}，2\sqrt{n} 则是部分块的复杂度。

例题

P4109 [HEOI2015] 定价

发现这道题，就是对于一个较大的数，让它尽可能的有最多的后导 0，然后删除后最后一位尽可能是 5，所以可以想到，对于先在的位置，他肯定加上 10 的 0 的个数次方最优。所以对于现在的数，计算贡献之后，每次加上 10 的 0 的个数次方遍历即可。

//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 5e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
    int u , w ;
};
struct Edgeve
{
    int v , w ;
};
struct node
{
  int x , y , id ;
}Node[kMaxN] ;
int l , r ;
inline ll ksm(ll a , ll b)

{
    ll mul = 1 ;
    while(b)
    {
        if(b & 1) mul *= a , mul %= MOD ;
        a *= a ;
        a %= MOD ;
        b >>= 1 ;
    }
    return mul ;
}
void work()
{
  cin >> l >> r ;
  int minn = 1e18 , ans ;
  while(l <= r)
  {
    int x = l , cnt = 0 ;
    while(x % 10 == 0)
    {
        x /= 10 ;
        cnt++ ;
        }
        int y = x , len = 0 ;
        while(y)
    {
        y /= 10 ;
        len++ ;
        }
        int res = 2 * len ;
        if(x % 10 == 5) res-- ;
        if(res < minn)
        {
            minn = res ;
            ans = l ;
        }
        l += ksm(10 , cnt) ;
    }
    cout << ans << "\n" ;
}
signed main()
{
//  freopen(".in" , "r" , stdin) ;
//  freopen(".out" , "w" , stdout) ;
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  cin >> t ;
  while(t--) work() ;
  return 0 ;
}

P5356 [Ynoi Easy Round 2017] 由乃打扑克

对于 2 操作，我们肯定会做，但是 1 操作不会。

之前的教主的魔法其实和这题的 1 操作有联系，对于第 k 小的数，一定有 k 个数小于等于它，所以二分即可。

当然，二分的两界需要进行动态的修改；对于每个点块，只有查到时才排序；对于整块的二分时，特判全都大于或小于的情况

//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 1e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
    int u , w ;
};
struct Edgeve
{
    int v , w ;
};
struct Edge
{
    int v , nxt ;
}edge[kMaxN] ;
struct node
{
  int u , v ;
}Node[kMaxN] ;
int n , q ;
int L[kMaxN] , R[kMaxN] , sum[kMaxN] , a[kMaxN] , pos[kMaxN] , lazy[kMaxN] ;
bool vis[kMaxN] ;
vector<int> G[kMaxN] ;
inline ll ksm(ll a , ll b)
{
    ll mul = 1 ;
    while(b)
    {
        if(b & 1) mul *= a , mul %= MOD ;
        a *= a ;
        a %= MOD ;
        b >>= 1 ;
    }
    return mul ;
}
void init(int n)
{
    int len = sqrt(n) ;
    int num = n / len ;
    if(n % len) num++ ;
    for( int i = 1 ; i <= num ; i++ )
    {
        L[i] = (i - 1) * len + 1 ;
        R[i] = i * len ;
    }
    R[num] = min(R[num] , n) ;
    for( int i = 1 ; i <= num ; i++ )
    {
        for( int j = L[i] ; j <= R[i] ; j++ )
        {
            G[i].push_back(a[j]) ;
            pos[j] = i ;
        }
        sort(G[i].begin() , G[i].end()) ;
    }
}
void update(int l , int r , int c)
{
    int p = pos[l] , q = pos[r] ;
    if(p == q)
    {
        for( int i = l ; i <= r ; i++ )
        {
            a[i] += c ;
        }
        vis[p] = 1 ;
    }
    else
    {
        for( int i = l ; i <= R[p] ; i++ )
        {
            a[i] += c ;
        }
        vis[p] = 1 ;
        for( int i = L[q] ; i <= r ; i++ )
        {
            a[i] += c ;
        }
        vis[q] = 1 ;
        for( int i = p + 1 ; i < q ; i++ )
        {
            lazy[i] += c ;
        }
    }
}
int check(int l , int r , int k)
{
    int p = pos[l] , q = pos[r] , ans = 0 ;
    if(p == q)
    {
        for( int i = l ; i <= r ; i++ )
        {
            if(a[i] + lazy[p] < k) ans++ ;
        }
    }
    else
    {
        for( int i = l ; i <= R[p] ; i++ )
        {
            if(a[i] + lazy[p] < k) ans++ ;
        }
        for( int i = L[q] ; i <= r ; i++ )
        {
            if(a[i] + lazy[q] < k) ans++ ;
        }
        for( int i = p + 1 ; i < q ; i++ )
        {
            if(G[i][0] >= k - lazy[i]) continue ;
            if(G[i][G[i].size() - 1] < k - lazy[i])
            {
                ans += R[i] - L[i] + 1 ;
                continue ;
            }
            ans += lower_bound(G[i].begin() , G[i].end() , k - lazy[i]) - G[i].begin() ;
        }
    }
    return ans ;
}
void EA(int p)
{
    G[p].clear() ;
    for( int i = L[p] ; i <= R[p] ; i++ )
    {
        a[i] += lazy[p] ;
        G[p].push_back(a[i]) ;
    }
    sort(G[p].begin() , G[p].end()) ;
    lazy[p] = vis[p] = 0 ;
}
int query(int l , int r , int k)
{
    int p = pos[l] , q = pos[r] , lt = INF , rt = -INF ;
    for( int i = p ; i <= q ; i++ )
    {
        if(vis[i])
        {
            EA(i) ;
        }
        lt = min(lt , G[i][0] + lazy[i]) ;
        rt = max(rt , G[i][G[i].size() - 1] + lazy[i]) ;
    }
    lt-- ;
    rt++ ;
    if(k > r - l + 1)
    {
        return -1 ;
    }
    while(lt + 1 < rt)
    {
        int mid = lt + rt >> 1 ;
        int tmp = check(l , r , mid) ;
        if(tmp > k - 1) rt = mid ;
        else lt = mid ;
    }
    return rt - 1 ;
}
void work()
{
  cin >> n >> q ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  init(n) ;
  for( int i = 1 ; i <= q ; i++ )
  {
    int op ;
    cin >> op ;
    if(op == 2) 
        {
            int l , r , k ;
            cin >> l >> r >> k ;
            update(l , r , k) ;
        }
    else 
        {
            int l , r , k ;
            cin >> l >> r >> k ;    
            cout << query(l , r , k) << "\n" ;
        }
    }
}
signed main()
{
//  freopen(".in" , "r" , stdin) ;
//  freopen(".out" , "w" , stdout) ;
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

P3203 [HNOI2010] 弹飞绵羊

非常水。

对于每个 k_i，都进行预处理能到的点，查询时，模拟即可。

//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
#define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 2e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
    int u , w ;
};
struct Edgeve
{
    int v , w ;
};
struct Edge
{
    int v , nxt ;
}edge[kMaxN] ;
struct node
{
  int u , v ;
}Node[kMaxN] ;
int n , q ;
int L[kMaxN] , R[kMaxN] , to[kMaxN] , a[kMaxN] , pos[kMaxN] , lazy[kMaxN] , step[kMaxN] ;
vector<int> G[kMaxN] ;
inline ll ksm(ll a , ll b)
{
    ll mul = 1 ;
    while(b)
    {
        if(b & 1) mul *= a , mul %= MOD ;
        a *= a ;
        a %= MOD ;
        b >>= 1 ;
    }
    return mul ;
}
void init()
{
    int len = sqrt(n) ;
    int num = n / len ;
    if(n % len) num++ ;
    for( int i = 1 ; i <= num ; i++ )
    {
        L[i] = (i - 1) * len + 1 ;
        R[i] = i * len ;
    }
    R[num] = min(R[num] , n) ;
    for( int i = 1 ; i <= num ; i++ )
    {
        for( int j = L[i] ; j <= R[i] ; j++ )
        {
            pos[j] = i ;
        }
    }
}
void update(int x , int y)
{
    a[x] = y ;
    for( int i = R[pos[x]] ; i >= L[pos[x]] ; i-- )
    {
        to[i] = i + a[i] ;
        if(to[i] > R[pos[i]]) step[i] = 1 ;
        else
        {
            step[i] = step[to[i]] + 1 ;
            to[i] = to[i + a[i]] ;
        }
    }
}
int query(int x)
{
    int ans = 0 ;
    while(x <= n)
    {
        ans += step[x] ;
        x = to[x] ;
    }
    return ans ;
}
void work()
{
  cin >> n ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  init() ;
  for( int i = n ; i >= 1 ; i-- )
  {
    to[i] = a[i] + i ;
    if(to[i] > R[pos[i]]) step[i] = 1 ;
        else
        {
            step[i] = step[to[i]] + 1 ;
            to[i] = to[i + a[i]] ;
        }
    }
  cin >> q ;
  while(q--)
  {
    int op , x , y ;
    cin >> op >> x ;
    x++ ;
    if(op == 1) cout << query(x) << "\n" ;
        else
        {
            cin >> y ;
            update(x , y) ;
        } 
    }
}
signed main()
{
//  freopen(".in" , "r" , stdin) ;
//  freopen(".out" , "w" , stdout) ;
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}