题解 CF911G 【Mass Change Queries】

· · 题解

看完题面 操作莫名熟悉

之后我们点开 这道题

诶 怎么修改操作一模一样啊

之后我们把那道题的AC记录xjb改改就过了

好吧上面当我没说

我们考虑分块 用并查集维护每个数的值

先想想整块怎么操作

假如我们在第i个块中 把值x的数改为y 如果值y在块中出现过 那么把$rt_{i,x}$的father设为$rt_{i,y}

如果没有出现过

就把rt_{i,y}赋值rt_{i,x} 并且把rt_{i,x}的值设为y

操作后 显然块内没有值为x的数 需把rt_{i,x}赋值为0

边角的时候

把块中的每个数都更新 重新做一遍rt数组

时间复杂度是熟悉的根号 而空间复杂度可以做到O(n)

边角暴力有个小优化 ：

我们更新的只是值为x和y的数 可以只把这两个子树拉出来重构 详见代码 

#include<bits/stdc++.h>  
#define rg register 
#define fp( i , x , y ) for( rg int i=(x); i<=(y); ++i ) 
#define fq( i , x , y ) for( rg int i=(y); i>=(x); --i )  
using namespace std ; 
const int N = 2e5+10 , B_P = 450 , V=105 ;    
int rt[B_P][V] , fa[N] , a[N] , n , blo ;   
int lef[B_P] , rig[B_P] , pos[N] , sta[B_P] ;  
int f( int x ) { return fa[x] == x ? x : fa[x] = f(fa[x]) ; } 
void prep( int p ) { 
  fp( i , lef[p] , rig[p] ) 
    if( !rt[p][a[i]] ) fa[i]=i , rt[p][a[i]]=i ; 
    else fa[i]=rt[p][a[i]] ;  
} 
void upd( int p , int lx , int rx , int x , int y ) {
  int l = lef[p] , r = rig[p] , top=0 ;
  rt[p][x] = rt[p][y] = 0 ; 
  fp( i , l , r ) { 
     a[i] = a[f(i)] ; 
     if( a[i] == x || a[i] == y ) sta[++top] = i ; 
  } 
  fp( i , lx , rx ) if( a[i] == x ) a[i] = y ; 
  fp( i , 1 , top ) fa[sta[i]] = sta[i] ; 
  fp( i , 1 , top ) 
    if( !rt[p][a[sta[i]]] ) rt[p][a[sta[i]]] = sta[i] ; 
    else fa[sta[i]] = rt[p][a[sta[i]]] ; 
} 
void modify( int l , int r , int x , int y ) { 
  if( x == y ) return ; 
  int lv = pos[l] , rv = pos[r] , tp , nw=0 ; 
  if( lv == rv ) { upd( lv , l , r , x , y ) ;  return ; } 
  upd( lv , l , rig[lv] , x , y ) ; 
  upd( rv , lef[rv] , r , x , y ) ; 
  fp( i , lv+1 , rv-1 ) { 
    if( !rt[i][x] ) continue ; 
    if( rt[i][y] ) fa[rt[i][x]] = rt[i][y] ; 
    else rt[i][y] = rt[i][x] , a[rt[i][x]] = y ; 
    rt[i][x] = 0 ; 
  } 
} 
signed main( ) { 
  ios::sync_with_stdio(false) ; 
  cin.tie(0) ; 
  int q , opt , l , r , x , y ; 
  cin >> n ;  
  blo = sqrt(n) ; 
  fp( i , 1 , n ) cin >> a[i] , fa[i]=i ;   
  fp( i , 1 , n ) pos[i] = (i-1)/blo+1 ; 
  fq( i , 1 , n ) lef[pos[i]] = i ; 
  fp( i , 1 , n ) rig[pos[i]] = i ; 
  fp( i , 1 , pos[n] ) prep( i ) ; 
  cin >> q ; 
  while( q -- ) {  
    cin >> l >> r >> x >> y ; 
    modify( l , r , x , y ) ; 
  } 
  fp( i , 1 , n ) a[i] = a[f(i)] , cout << a[i] << ' ' ;  
  cout << '\n' ; 
  return 0 ; 
}

跑的很优秀 不需要任何卡常即可1.5s过题