专栏文章

莫队3

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

文章操作

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

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

基础

对于每个莫队，基本上都不带修改，如果要修改，需要进行一些操作。
记录每个查询前面有几个修改，然后莫队时修改即可。

例题

P1903 [国家集训队] 数颜色 / 维护队列

记录每个询问之前改变的个数，询问时改变即可。
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 = 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

暴力求答案，看最小的值即可。
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 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 ;
}

评论

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

正在加载评论...