专栏文章

莫队1

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

文章操作

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

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

基础

如果要求 [2,4][2,4] 的和，可以看成 [2,5]−a5[2,5]-a_5，莫队的基本模版就是这种思路对于每个询问进行加或者减的操作。
发现对于每个询问进行改变的距离和就是曼哈顿距离的和。、
为了让这个值尽可能小。如果在一个块内那么就按有边界排序；否则是左边界。

例题

P3901 数列找不同

用数组记录是否出现过，用变量记录即可。
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 ;
};
int n , q ;
int len ;
int a[kMaxN] , ans[kMaxN] , cnt[kMaxN] , res ;
struct node
{
  int l , r , id ;
}Node[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)
{
	cnt[a[x]]++ ;
	if(cnt[a[x]] == 1) res++ ;
} 
void SUB(int x)
{
	cnt[a[x]]-- ;
	if(cnt[a[x]] == 0) res-- ;
} 
bool cmp(node x , node y)
{
	if(x.l / len == y.l / len) return x.r < y.r ;
	return x.l < y.l ;
}
void work()
{
	cin >> n >> q ;
	len = sqrt(n) ;
	for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
	for( int i = 1 ; i <= q ; i++ )
	{
		cin >> Node[i].l >> Node[i].r ;
		Node[i].id = i ;
	}
	sort(Node + 1 , Node + q + 1 , cmp) ;
	int l = 1 , r = 0 ;
	for( int i = 1 ; i <= q ; i++ )
	{
		while(l < Node[i].l) SUB(l++) ;
		while(l > Node[i].l) ADD(--l) ;
		while(r < Node[i].r) ADD(++r) ;
		while(r > Node[i].r) SUB(r--) ;
		ans[Node[i].id] = (res == Node[i].r - Node[i].l + 1) ;
	}
	for( int i = 1 ; i <= q ; i++ ) cout << (ans[i] ? "Yes\n" : "No\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 ;
}

P2709 小B的询问

与上体相似，改变时先减再加。
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 ;
};
int n , q , k ;
int len ;
int a[kMaxN] , ans[kMaxN] , cnt[kMaxN] , res ;
struct node
{
  int l , r , id ;
}Node[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)
{
	res -= cnt[a[x]] * cnt[a[x]] ;
	cnt[a[x]]++ ;
	res += cnt[a[x]] * cnt[a[x]] ;
} 
void SUB(int x)
{
	res -= cnt[a[x]] * cnt[a[x]] ;
	cnt[a[x]]-- ;
	res += cnt[a[x]] * cnt[a[x]] ;
} 
bool cmp(node x , node y)
{
	if(x.l / len == y.l / len) return x.r < y.r ;
	return x.l < y.l ;
}
void work()
{
	cin >> n >> q >> k ;
	len = sqrt(n) ;
	for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
	for( int i = 1 ; i <= q ; i++ )
	{
		cin >> Node[i].l >> Node[i].r ;
		Node[i].id = i ;
	}
	sort(Node + 1 , Node + q + 1 , cmp) ;
	int l = 1 , r = 0 ;
	for( int i = 1 ; i <= q ; i++ )
	{
		while(l < Node[i].l) SUB(l++) ;
		while(l > Node[i].l) ADD(--l) ;
		while(r < Node[i].r) ADD(++r) ;
		while(r > Node[i].r) SUB(r--) ;
		ans[Node[i].id] = res ;
	}
	for( int i = 1 ; i <= 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 ;
}

P1494 [国家集训队] 小 Z 的袜子

推式子：(a2+b2+c2+⋯+x2−(R−L+1))/((R−L+1)×(R−L))(a ^ 2 + b ^ 2 + c ^ 2+\cdots+x ^ 2 - (R - L + 1)) / ((R - L + 1) \times (R - L))。
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 = 5e4 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
int n , q ;
int len ;
int a[kMaxN] , cnt[kMaxN] , res ;
struct Node
{
	int a , b ;
}ans[kMaxN] ;
struct node
{
  int l , r , id ;
}Node[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)
{
	res -= cnt[a[x]] * cnt[a[x]] ;
	cnt[a[x]]++ ;
	res += cnt[a[x]] * cnt[a[x]] ;
} 
void SUB(int x)
{
	res -= cnt[a[x]] * cnt[a[x]] ;
	cnt[a[x]]-- ;
	res += cnt[a[x]] * cnt[a[x]] ;
} 
bool cmp(node x , node y)
{
	if(x.l / len == y.l / len) return x.r < y.r ;
	return x.l < y.l ;
}
void work()
{
	cin >> n >> q ;
	len = sqrt(n) ;
	for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
	for( int i = 1 ; i <= q ; i++ )
	{
		cin >> Node[i].l >> Node[i].r ;
		Node[i].id = i ;
	}
	sort(Node + 1 , Node + q + 1 , cmp) ;
	int l = 1 , r = 0 ;
	for( int i = 1 ; i <= q ; i++ )
	{
		while(l < Node[i].l) SUB(l++) ;
		while(l > Node[i].l) ADD(--l) ;
		while(r < Node[i].r) ADD(++r) ;
		while(r > Node[i].r) SUB(r--) ;
		if(Node[i].l == Node[i].r)
		{
			ans[Node[i].id] = {0 , 1} ;
            continue ;
		}
		ans[Node[i].id] = {res - (Node[i].r - Node[i].l + 1) , (Node[i].r - Node[i].l + 1) * (Node[i].r - Node[i].l)} ;
		int gcd = __gcd(res - (Node[i].r - Node[i].l + 1) , (Node[i].r - Node[i].l + 1) * (Node[i].r - Node[i].l)) ;
		ans[Node[i].id].a /= gcd ;
		ans[Node[i].id].b /= gcd ;
	}
	for( int i = 1 ; i <= q ; i++ ) cout << ans[i].a << "/" << ans[i].b << "\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 ;
}

P4462 [CQOI2018] 异或序列

发现答案是 sumrxorsuml−1sum_rxor sum_{l - 1}，所以记录现在的异或值的个数即可。
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 ;
};
int n , q , k ;
int len ;
int a[kMaxN] , ans[kMaxN] , cnt[kMaxN] , res ;
struct node
{
  int l , r , id ;
}Node[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)
{
	res += cnt[a[x] ^ k] ;
	cnt[a[x]]++ ;
} 
void SUB(int x)
{
	cnt[a[x]]-- ;
	res -= cnt[a[x] ^ k] ;
} 
bool cmp(node x , node y)
{
	if(x.l / len == y.l / len) return x.r < y.r ;
	return x.l < y.l ;
}
void work()
{
	cin >> n >> q >> k ;
	len = sqrt(n) ;
	for( int i = 1 ; i <= n ; i++ ) 
	{
		cin >> a[i] ;
		a[i] ^= a[i - 1] ;
	}
	for( int i = 1 ; i <= q ; i++ )
	{
		cin >> Node[i].l >> Node[i].r ;
		Node[i].id = i ;
	}
	sort(Node + 1 , Node + q + 1 , cmp) ;
	int l = 1 , r = 0 ;
	cnt[0] = 1 ;
	for( int i = 1 ; i <= q ; i++ )
	{
		while(l < Node[i].l) SUB(l++ - 1) ;
		while(l > Node[i].l) ADD(--l - 1) ;
		while(r < Node[i].r) ADD(++r) ;
		while(r > Node[i].r) SUB(r--) ;
		ans[Node[i].id] = res ;
	}
	for( int i = 1 ; i <= 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 条评论，欢迎与作者交流。

正在加载评论...