莫队3
基础
对于每个莫队，基本上都不带修改，如果要修改，需要进行一些操作。
记录每个查询前面有几个修改，然后莫队时修改即可。
例题
P1903 [国家集训队] 数颜色 / 维护队列
记录每个询问之前改变的个数，询问时改变即可。
//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 query
{
int l , r , id , t ;
}Q[kMaxN] ;
struct MODIFY
{
int pos , val ;
}M[kMaxN] ;
int n , t , res , len ;
int a[kMaxN] , vis[kMaxN * 10] , ans[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 ADD(int x)
{
vis[x]++ ;
if(vis[x] == 1) res++ ;
}
void SUB(int x)
{
vis[x]-- ;
if(vis[x] == 0) res-- ;
}
bool cmp(query x , query y)
{
if(x.l / len != y.l / len) return x.l < y.l ;
else if(x.r / len != y.r / len) return x.r < y.r ;
return x.t < y.t ;
}
void modify(int x , int t)
{
if(M[t].pos >= Q[x].l && M[t].pos <= Q[x].r)
{
SUB(a[M[t].pos]) ;
ADD(M[t].val) ;
}
swap(a[M[t].pos] , M[t].val) ;
}
void work()
{
cin >> n >> t ;
len = (int)(pow(n , 2.0 / 3.0)) ;
for( int i = 1 ; i <= n ; i++ )
{
cin >> a[i] ;
}
int cnt_r = 0 , cnt_q = 0 ;
while(t--)
{
char c ;
cin >> c ;
if(c == 'Q')
{
cnt_q++ ;
cin >> Q[cnt_q].l >> Q[cnt_q].r ;
Q[cnt_q].t = cnt_r ;
Q[cnt_q].id = cnt_q ;
}
else
{
cnt_r++ ;
cin >> M[cnt_r].pos >> M[cnt_r].val ;
}
}
sort(Q + 1 , Q + cnt_q + 1 , cmp) ;
int l = 1 , r = 0 , t = 0 ;
for( int i = 1 ; i <= cnt_q ; i++ )
{
while(l < Q[i].l) SUB(a[l++]) ;
while(l > Q[i].l) ADD(a[--l]) ;
while(r < Q[i].r) ADD(a[++r]) ;
while(r > Q[i].r) SUB(a[r--]) ;
while(t < Q[i].t) modify(i , ++t) ;
while(t > Q[i].t) modify(i , t--) ;
ans[Q[i].id] = res ;
}
for( int i = 1 ; i <= cnt_q ; i++ ) cout << ans[i] << "\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 ;
}
CF940F Machine Learning
暴力求答案，看最小的值即可。
//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 query
{
int l , r , id , t ;
}Q[kMaxN] ;
struct MODIFY
{
int pos , val ;
}M[kMaxN] ;
int n , t , res , len , now ;
int a[kMaxN] , cnt[kMaxN * 10] , vis[kMaxN * 10] , ans[kMaxN] , b[kMaxN * 3] ;
map<int , int> mp ;
void ADD(int x)
{
vis[cnt[x]]-- ;
cnt[x]++ ;
vis[cnt[x]]++ ;
}
void SUB(int x)
{
vis[cnt[x]]-- ;
cnt[x]-- ;
vis[cnt[x]]++ ;
}
bool cmp(query x , query y)
{
if(x.l / len != y.l / len) return x.l < y.l ;
else if(x.r / len != y.r / len) return x.r < y.r ;
return x.t < y.t ;
}
void modify(int x , int t)
{
if(M[t].pos >= Q[x].l && M[t].pos <= Q[x].r)
{
SUB(a[M[t].pos]) ;
ADD(M[t].val) ;
}
swap(a[M[t].pos] , M[t].val) ;
}
void work()
{
cin >> n >> t ;
len = (int)(pow(n , 2.0 / 3.0)) ;
for( int i = 1 ; i <= n ; i++ )
{
cin >> a[i] ;
b[++now] = a[i] ;
}
int cnt_r = 0 , cnt_q = 0 ;
while(t--)
{
int op ;
cin >> op ;
if(op == 1)
{
cnt_q++ ;
cin >> Q[cnt_q].l >> Q[cnt_q].r ;
Q[cnt_q].t = cnt_r ;
Q[cnt_q].id = cnt_q ;
}
else
{
cnt_r++ ;
cin >> M[cnt_r].pos >> M[cnt_r].val ;
b[++now] = M[cnt_r].val ;
}
}
sort(b + 1 , b + now + 1) ;
int len = unique(b + 1 , b + now + 1) - (b + 1) ;
for( int i = 1 ; i <= n ; i++ ) a[i] = lower_bound(b + 1 , b + 1 + len , a[i]) - b ;
for( int i = 1 ; i <= cnt_r ; i++ ) M[i].val = lower_bound(b + 1 , b + 1 + len , M[i].val) - b ;
sort(Q + 1 , Q + cnt_q + 1 , cmp) ;
int l = 1 , r = 0 , t = 0 ;
for( int i = 1 ; i <= cnt_q ; i++ )
{
while(l < Q[i].l) SUB(a[l++]) ;
while(l > Q[i].l) ADD(a[--l]) ;
while(r < Q[i].r) ADD(a[++r]) ;
while(r > Q[i].r) SUB(a[r--]) ;
while(t < Q[i].t) modify(i , ++t) ;
while(t > Q[i].t) modify(i , t--) ;
int now = 1 ;
while(vis[now]) now++ ;
ans[Q[i].id] = now ;
}
for( int i = 1 ; i <= cnt_q ; i++ ) cout << ans[i] << "\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 ;
}