莫队1

Hhy140516 · 2025-08-04 10:48:39 · 个人记录

基础

如果要求 [2,4] 的和，可以看成 [2,5]-a_5，莫队的基本模版就是这种思路对于每个询问进行加或者减的操作。

发现对于每个询问进行改变的距离和就是曼哈顿距离的和。、

为了让这个值尽可能小。如果在一个块内那么就按有边界排序；否则是左边界。

例题

P3901 数列找不同

用数组记录是否出现过，用变量记录即可。

//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的询问

与上体相似，改变时先减再加。

//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 的袜子

推式子：(a ^ 2 + b ^ 2 + c ^ 2+\cdots+x ^ 2 - (R - L + 1)) / ((R - L + 1) \times (R - L))。

//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] 异或序列

发现答案是 sum_rxor sum_{l - 1}，所以记录现在的异或值的个数即可。

//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 ;
}