专栏文章

分块3

HHhy140516
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miojy91v
此快照首次捕获于
2025/12/02 20:26
3 个月前
此快照最后确认于
2025/12/02 20:26
3 个月前
查看原文

基础

今天的题目对于分快来说，都需要进行一些优化。比如说在二分时对于全部大或者全部小时的优化；二分上下界优化等等。
分块的复杂度是整块的个数加上 2n2\sqrt{n}，2n2\sqrt{n} 则是部分块的复杂度。

例题

P4109 [HEOI2015] 定价

发现这道题，就是对于一个较大的数，让它尽可能的有最多的后导 00，然后删除后最后一位尽可能是 55，所以可以想到，对于先在的位置，他肯定加上 1010 的 00 的个数次方最优。所以对于现在的数，计算贡献之后，每次加上 1010 的 00 的个数次方遍历即可。
CPP
//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] 由乃打扑克

对于 22 操作，我们肯定会做，但是 11 操作不会。
之前的教主的魔法其实和这题的 11 操作有联系，对于第 kk 小的数，一定有 kk 个数小于等于它，所以二分即可。
当然，二分的两界需要进行动态的修改；对于每个点块，只有查到时才排序；对于整块的二分时，特判全都大于或小于的情况
CPP
//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] 弹飞绵羊

非常水。
对于每个 kik_i，都进行预处理能到的点，查询时，模拟即可。
CPP
//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 ;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...