CF455D 题解

Rubyonly · 2021-03-16 20:56:33 · 题解

看到楼上有平衡树做法，可惜我平衡树不会几个，用得也不熟

其实用分块套一下还是比较好写的

对于每个块维护一个双端队列，用来进行支持右移操作

同时维护一个桶，记录一下每个块内不同值的个数，便于查询

然后直接操作就行了，细节也不算很多，注意特殊处理 l 和 r 都在同一个块内时的情况，而且双端队列可以像 vector 一样进行下标查询，更加方便了我们的操作

#include <cstdio>
#include <algorithm>
#include <deque>
#include <cmath>

#define rint register int 

using namespace std;

const int maxn = 1e5 + 50;

inline int read () {
    rint x = 0, w = 1;
    char ch = getchar ();
    for (; ch < '0' || ch > '9'; ch = getchar ()) if (ch == '-') w = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar ()) x = x * 10 + ch - '0';
    return x * w;
}

int n, m, S, a[maxn], st[maxn];
int bel[maxn], L[maxn], R[maxn], buc[320][maxn];
deque <int> q[320];

inline void Init () {
    S = sqrt (n);
    for (rint i = 1; i <= n; i ++) a[i] = read();
    for (rint i = 1; i <= n; i ++) {
        bel[i] = (i - 1) / S + 1, R[bel[i]] = i;
        buc[bel[i]][a[i]] ++, q[bel[i]].push_back (a[i]);
        if (! L[bel[i]]) L[bel[i]] = i;
    }
}

inline void Modify (rint l, rint r, rint top = 0) {
    if (bel[l] == bel[r]) {
        rint now = bel[l];
        l -= L[now], r -= L[now], st[++ top] = q[now][r];
        for (rint i = l; i < r; i ++) st[++ top] = q[now][i];
        for (rint i = r; i >= l; i --) q[now][i] = st[top --];
        return;
    }
    rint cnt1 = R[bel[l]] - l + 1, cnt2 = r - L[bel[r]] + 1;
    while (cnt1 --) {
        rint x = q[bel[l]].back ();
        st[++ top] = x, buc[bel[l]][x] --, q[bel[l]].pop_back (); 
    }
    st[++ top] = q[bel[r]][cnt2 - 1];
    while (top > 1) {
        rint x = st[top];
        q[bel[l]].push_back (x), buc[bel[l]][x] ++, top --; 
    }
    for (rint i = bel[l] + 1; i <= bel[r] - 1; i ++) {
        rint x = st[top];
        q[i].push_front (x), buc[i][x] ++, top --;
        rint y = q[i].back ();
        st[++ top] = y, buc[i][y] --, q[i].pop_back();
    }
    while (cnt2 --) {
        rint x = q[bel[r]].front ();
        st[++ top] = x, buc[bel[r]][x] --, q[bel[r]].pop_front ();
    }
    top --;
    while (top > 0) {
        rint x = st[top];
        q[bel[r]].push_front (x), buc[bel[r]][x] ++, top --;
    }
}

inline int Query (rint l, rint r, rint k, rint ans = 0) {
    if (bel[l] == bel[r]) {
        rint now = bel[l];
        l -= L[now], r -= L[now];
        for (rint i = l; i <= r; i ++) ans += q[now][i] == k;   
        return ans;
    }
    rint cnt1 = R[bel[l]] - l + 1, cnt2 = r - L[bel[r]] + 1;
    for (rint i = q[bel[l]].size () - cnt1; i <= q[bel[l]].size () - 1; i ++) ans += q[bel[l]][i] == k;
    for (rint i = 0; i <= cnt2 - 1; i ++) ans += q[bel[r]][i] == k; 
    for (rint i = bel[l] + 1; i <= bel[r] - 1; i ++) ans += buc[i][k];
    return ans;
}

int main () {
    n = read(), Init (), m = read();
    rint last = 0;
    while (m --) {
        rint opt = read(), l = (read() + last - 1) % n + 1, r = (read() + last - 1) % n + 1, k;
        if (l > r) swap (l, r);
        if (opt == 1) Modify (l, r);
        else k = (read() + last - 1) % n + 1, printf ("%d\n", last = Query (l, r, k));
    }
    return 0;
}