CF455D-Serega and Fun

2021-01-05 约 998 字预计阅读 2 分钟次阅读

CF455D-Serega and Fun

题目:

题目描述:

Serega loves fun. However, everyone has fun in the unique manner. Serega has fun by solving query problems. One day Fedor came up with such a problem.

You are given an array $ a $ consisting of $ n $ positive integers and queries to it. The queries can be of two types:

Make a unit cyclic shift to the right on the segment from $ l $ to $ r $ (both borders inclusive). That is rearrange elements of the array in the following manner: $ a[l],a[l+1],…,a[r-1],a[r]→a[r],a[l],a[l+1],…,a[r-1]. $
Count how many numbers equal to $ k $ are on the segment from $ l $ to $ r $ (both borders inclusive).

Fedor hurried to see Serega enjoy the problem and Serega solved it really quickly. Let’s see, can you solve it?

输入格式:

The first line contains integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of elements of the array. The second line contains $ n $ integers $ a[1],a[2],…,a[n] $ ( $ 1<=a[i]<=n $ ).

The third line contains a single integer $ q $ ( $ 1<=q<=10^{5} $ ) — the number of queries. The next $ q $ lines contain the queries.

As you need to respond to the queries online, the queries will be encoded. A query of the first type will be given in format: $ 1 $ $ l’{i} $ $ r’{i} $ . A query of the second type will be given in format: $ 2 $ $ l’{i} $ $ r’{i} $ $ k’{i} $ . All the number in input are integer. They satisfy the constraints: $ 1<=l’{i},r’{i},k’{i}<=n $ .

To decode the queries from the data given in input, you need to perform the following transformations:

$ l_{i}=((l’_{i}+lastans-1) mod n)+1; r_{i}=((r’_{i}+lastans-1) mod n)+1; k_{i}=((k’_{i}+lastans-1) mod n)+1. $ Where $ lastans $ is the last reply to the query of the 2-nd type (initially, $ lastans=0 $ ). If after transformation $ l_{i} $ is greater than $ r_{i} $ , you must swap these values.

输出格式:

For each query of the 2-nd type print the answer on a single line.

样例:

样例输入1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
7
6 6 2 7 4 2 5
7
1 3 6
2 2 4 2
2 2 4 7
2 2 2 5
1 2 6
1 1 4
2 1 7 3

样例输出1:

样例输入2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
8
8 4 2 2 7 7 8 8
8
1 8 8
2 8 1 7
1 8 1
1 7 3
2 8 8 3
1 1 4
1 2 7
1 4 5

样例输出2:

思路:

实现:

 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
// Problem: CF455D Serega and Fun
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF455D
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
int s, n, q;
const int maxb = 355, maxn = 1e5 + 5;
deque<int> a[maxb];
int ans;
void di(int &x) { x = (x + ans - 1) % n + 1; }
int c[maxb][maxn];
int main()
{
    yin >> n;
    s = sqrt(n);
    for (int i = 0; i < n; i++)
    {
        int x;
        yin >> x;
        a[i / s].push_back(x);
        c[i / s][x]++;
    }
    yin >> q;
    while (q--)
    {
        int opt, x, l, r;
        yin >> opt >> l >> r;
        di(l), di(r);
        if (l > r)
            swap(l, r);
        l--;
        int L = l / s, R = r / s;
        // cerr << l << " " << r << " " << L << " " << R << endl;
        if (opt == 2)
        {
            int k;
            yin >> k;
            di(k);
            ans = 0;
            if (L == R)
                for (int i = l % s; i < r % s; i++)
                    ans += a[L][i] == k;
            else
            {
                for (int i = L + 1; i < R; i++)
                {
                    ans += c[i][k];
                }
                for (int i = l % s; i < a[L].size(); i++)
                {
                    ans += a[L][i] == k;
                }
                for (int i = 0; i < r % s; i++)
                {
                    ans += a[R][i] == k;
                }
            }
            yout << ans << endl;
        }
        else
        {
            if (L == R)
            {
                r = r % s - 1, x = a[R][r];
                a[R].erase(a[R].begin() + r);
                a[L].insert(a[L].begin() + l % s, x);
            }
            else
            {
                for (int i = L; i < R;)
                {
                    x = a[i].back(), a[i].pop_back();
                    c[i][x]--;
                    i++;
                    a[i].push_front(x), c[i][x]++;
                }
                r = r % s, x = a[R][r];
                a[R].erase(a[R].begin() + r);
                c[R][x]--;
                a[L].insert(a[L].begin() + l % s, x);
                c[L][x]++;
            }
        }
    }
    return 0;
}

目录

CF455D-Serega and Fun

CF455D-Serega and Fun

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入1:

样例输出1:

样例输入2:

样例输出2:

思路:

实现: