分块2
个人记录
基础
一般来说，分块的复杂度优化是在整块的部分，但是今天的一些题，需要对部分块进行一些优化。
例题
P2801 教主的魔法
这题和做题的模版题相似，就是进行排序，找值即可。
//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 = 1e6 + 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] ;
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 ;
}
G[p].clear() ;
for( int i = L[p] ; i <= R[p] ; i++ ) G[p].push_back(a[i]) ;
sort(G[p].begin() , G[p].end()) ;
}
else
{
for( int i = l ; i <= R[p] ; i++ )
{
a[i] += c ;
}
G[p].clear() ;
for( int i = L[p] ; i <= R[p] ; i++ ) G[p].push_back(a[i]) ;
sort(G[p].begin() , G[p].end()) ;
for( int i = L[q] ; i <= r ; i++ )
{
a[i] += c ;
}
G[q].clear() ;
for( int i = L[q] ; i <= R[q] ; i++ ) G[q].push_back(a[i]) ;
sort(G[q].begin() , G[q].end()) ;
for( int i = p + 1 ; i < q ; i++ )
{
lazy[i] += c ;
}
}
}
int query(int l , int r , int x)
{
int p = pos[l] , q = pos[r] , cnt = 0 ;
if(p == q)
{
for( int i = l ; i <= r ; i++ )
{
cnt += (a[i] + lazy[p] < x) ;
}
}
else
{
for( int i = l ; i <= R[p] ; i++ )
{
cnt += (a[i] + lazy[p] < x) ;
}
for( int i = L[q] ; i <= r ; i++ )
{
cnt += (a[i] + lazy[q] < x) ;
}
for( int i = p + 1 ; i < q ; i++ )
{
cnt += lower_bound(G[i].begin() , G[i].end() , x - lazy[i]) - G[i].begin() ;
}
}
return cnt ;
}
void work()
{
cin >> n >> q ;
for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
init(n) ;
for( int i = 1 ; i <= q ; i++ )
{
char op ;
cin >> op ;
if(op == 'M')
{
int l , r , c ;
cin >> l >> r >> c ;
update(l , r , c) ;
}
else
{
int l , r , x ;
cin >> l >> r >> x ;
cout << (r - l + 1) - query(l , r , x) << "\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 ;
}
P3793 由乃救爷爷
题目给定随机数生成器，求答案。
发现纯 ST 表行不通，考虑在块内进行。
因为数据比较水，部分块直接枚举即可。
正解是需要优化的。
//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 = 3e7 + 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 , m ;
unsigned s ;
int a[kMaxN] ;
int lg[kMaxN] , p[kMaxN] , q[kMaxN] ;
int st[5005][13] ;
int L[5005] , R[5005] , pos[kMaxN] ;
int num = 0 ;
ull ans = 0 ;
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 ;
}
namespace GenHelper
{
unsigned z1,z2,z3,z4,b;
unsigned rand_()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
using namespace GenHelper;
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
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++ )
{
st[i][0] = max(st[i][0] , a[j]) ;
pos[j] = i ;
}
p[L[i]] = a[L[i]] ;
q[R[i]] = a[R[i]] ;
for( int j = L[i] + 1 ; j <= R[i] ; j++ )
{
p[j] = max(p[j - 1] , a[j]) ;
}
for( int j = R[i] - 1 ; j >= L[i] ; j-- )
{
q[j] = max(q[j + 1] , a[j]) ;
}
}
for( int i = 2 ; i <= num ; i++ ) lg[i] = lg[i >> 1] + 1 ;
for( int j = 1 ; (1 << j) <= num ; j++ )
{
for( int i = 1 ; i + (1 << j) - 1 <= num ; i++ )
{
st[i][j] = max(st[i][j - 1] , st[i + (1 << j - 1)][j - 1]) ;
}
}
}
int query(int l , int r)
{
if(l > r) return 0 ;
int k = lg[r - l + 1] ;
return max(st[l][k] , st[r - (1 << k) + 1][k]) ;
}
void work()
{
cin >> n >> m >> s ;
srand(s) ;
for( int i = 1 ; i <= n ; i++ ) a[i] = read() ;
init() ;
for( int i = 1 ; i <= m ; i++ )
{
int l = read() % n + 1 , r = read() % n + 1 ;
if(l > r) swap(l , r) ;
int x = pos[l] , y = pos[r] ;
int tmp = 0 ;
if(x == y)
{
for( int i = l ; i <= r ; i++ )
{
tmp = max(tmp , a[i]) ;
}
}
else
{
tmp = query(x + 1 , y - 1) ;
tmp = max(tmp , max(q[l] , p[r])) ;
}
ans += tmp ;
}
cout << ans ;
}
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 ;
}
P4879 ycz的妹子
这道对于每个情况改变和即可，当然有可能现在是 0，所以需要数组标记。
#include<bits/stdc++.h>
#define int long long
using namespace std ;
int n , m ;
int a[1000005] ;
int x[1000005] , y[1000005] , pos[1000005] ;
int sum[1000005] ;
int gs[1000005] , num , len ;
bool vis[1000005] ;
void init()
{
len = sqrt(n) ;
num = n / len ;
if(n % len != 0)
{
num++ ;
}
for( int i = 1 ; i <= num ; i++ )
{
x[i] = (i - 1) * len + 1 ;
y[i] = i * len ;
}
y[num] = n ;
for( int i = 1 ; i <= num ; i++ )
{
for( int j = x[i] ; j <= y[i] ; j++ )
{
pos[j] = i ;
sum[i] += a[j] ;
if(vis[j]) gs[i]++ ;
}
}
return ;
}
void change(int l , int r , int c)
{
int p = pos[l] ;
int q = pos[r] ;
if(p == q)
{
for( int i = l ; i <= r ; i++ )
{
if(!vis[i]) continue ;
a[i] += c ;
}
sum[p] += (r - l + 1) * c ;
return ;
}
else
{
for( int i = l ; i <= y[p] ; i++ )
{
if(!vis[i]) continue ;
a[i] += c ;
sum[p] += c ;
}
for( int i = x[q] ; i <= r ; i++ )
{
if(!vis[i]) continue ;
a[i] += c ;
sum[q] += c ;
}
return ;
}
}
int check(int l , int r)
{
int p = pos[l] ;
int q = pos[r] , ans = 0 ;
if(p == q)
{
for( int i = l ; i <= r ; i++ )
{
ans += a[i] ;
}
return ans ;
}
else
{
for( int i = l ; i <= y[p] ; i++ )
{
ans += a[i] ;
}
for( int i = x[q] ; i <= r ; i++ )
{
ans += a[i] ;
}
p++ ;
q-- ;
for( int i = p ; i <= q ; i++ )
{
ans += sum[i] ;
}
return ans ;
}
}
void cc(int l , int c)
{
int p = pos[l] ;
sum[p] -= a[l] ;
a[l] = c ;
sum[p] += c ;
if(!vis[l])
{
gs[p]++ ;
}
vis[l] = 1 ;
}
void ch(int l)
{
int ans = 0 ;
for( int i = 1 ; i <= num ; i++ )
{
ans += gs[i] ;
if(ans >= l)
{
ans -= gs[i] ;
for( int j = x[i] ; j <= y[i] ; j++ )
{
if(vis[j])
{
ans++ ;
}
if(ans == l)
{
vis[j] = 0 ;
sum[i] -= a[j] ;
a[j] = 0 ;
gs[i]-- ;
break ;
}
}
break ;
}
}
}
void work()
{
cin >> n >> m ;
for( int i = 1 ; i <= n ; i++ )
{
cin >> a[i] ;
vis[i] = 1 ;
}
n = 5e5 ;
init() ;
while(m--)
{
char opt ;
int l , r , c ;
cin >> opt ;
if(opt == 'C')
{
cin >> l >> c ;
change(l , l , -c) ;
}
else if(opt == 'I')
{
cin >> l >> c ;
cc(l , c) ;
}
else if(opt == 'D')
{
cin >> l ;
ch(l) ;
}
else
{
cout << check(1 , n) << "\n" ;
}
}
}
signed main()
{
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
int t = 1 ;
// cin >> t ;
while(t--)
{
work();
}
return 0;
}