DDOSvoid's Blog

CF 455D Serega and Fun

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/CF455D

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，每次操作将区间 $[l,r]$ 的数字循环右移，$a[r]$ 移动到 $l$，或者给定 $l,r,k$ 查询区间 $[l,r]$ 的 $k$ 的出现次数

$n,m\le 10^5$

Solution

注意到操作的本质就是双端队列扔掉队尾，然后 $push$ 到队首

我们考虑分块，每个块维护一个 $deque$ 和块内某个值的个数

修改和查询都是 $O(\sqrt n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <deque>
#include <cmath>
#define maxn 100010
#define maxb 400
#define ll long long
using namespace std;

int n, m, a[maxn];

int blo, num, l[maxb], r[maxb], d[maxb][maxn], bl[maxn];
deque<int> Q[maxb];
void init_blo(int n) {
    blo = sqrt(n); num = (n + blo - 1) / blo;
    for (int i = 1; i <= num; ++i) {
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo;
    } r[num] = n;
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
    for (int i = 1; i <= n; ++i) ++d[bl[i]][a[i]], Q[bl[i]].push_back(a[i]); 
}

void build(int k) {
    for (int i = r[k]; i >= l[k]; --i) {
        a[i] = Q[k].back();
        Q[k].pop_back();
        Q[k].push_front(a[i]);
    }
}

void rebuild(int k) {
    Q[k].clear(); 
    for (int i = l[k]; i <= r[k]; ++i) Q[k].push_back(a[i]); 
} 

void update(int L, int R) {
    int Bl = bl[L], Br = bl[R]; 
    if (Bl == Br) {
        build(Bl); int v = a[R]; 
        for (int i = R; i > L; --i) a[i] = a[i - 1];
        a[L] = v; rebuild(Bl); return ; 
    } build(Bl); build(Br); int v = a[r[Bl]]; 
    for (int i = Bl + 1; i < Br; ++i) {
        Q[i].push_front(v); ++d[i][v];
        v = Q[i].back(); 
        Q[i].pop_back(); --d[i][v];
    }
    --d[Bl][a[r[Bl]]]; ++d[Bl][a[R]];
    for (int i = r[Bl]; i > L; --i) a[i] = a[i - 1];
    a[L] = a[R];
    --d[Br][a[R]]; ++d[Br][v];
    for (int i = R; i > l[Br]; --i) a[i] = a[i - 1];
    a[l[Br]] = v; 
    rebuild(Bl); rebuild(Br); 
}

int query(int L, int R, int k) {
    int Bl = bl[L], Br = bl[R], ans = 0; 
    if (Bl == Br) {
        build(Bl); 
        for (int i = L; i <= R; ++i) ans += a[i] == k;
        return ans;
    }
    for (int i = Bl + 1; i < Br; ++i) ans += d[i][k];
    build(Bl); build(Br);
    for (int i = L; i <= r[Bl]; ++i) ans += a[i] == k;
    for (int i = l[Br]; i <= R; ++i) ans += a[i] == k;
    return ans;
} 

int lans;
inline void solve_1() {
    int x, y; cin >> x >> y;
    x = (x + lans - 1) % n + 1; y = (y + lans - 1) % n + 1;
    if (x > y) swap(x, y); 
    update(x, y); 
}

inline void solve_2() {
    int x, y, z; cin >> x >> y >> z;
    x = (x + lans - 1) % n + 1; y = (y + lans - 1) % n + 1; z = (z + lans - 1) % n + 1;
    if (x > y) swap(x, y); 
    cout << (lans = query(x, y, z)) << "\n"; 
} 
 
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    init_blo(n); cin >> m;
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2();
    } 
    return 0;
}