Блог

Итак, задача такова: вам предоставляется массив Arr размером n. элементы массива варьируются от 1 до n. у вас есть два типа запросов:

1. (l, r) — выполните циклический сдвиг в подмассиве Arr[l, r] с обоих концов включительно.
2. (l, r, k) — выведите количество элементов в диапазоне [l, r], которые равны k;

Ссылка на исходную проблему: https://codeforces.com/contest/455/problem/D

Я решил сделать так: давайте разделим массив Arr на блоки sqrt (n). давайте сохраним значения sqrt (n) (C STL deque). также давайте сохраним массивы счетчиков sqrt (n), где cnt[i][j] — это количество раз, когда число j встречается в i-м блоке

первый запрос может быть выполнен за O (sqrt (n)) времени, если мы просто обновим deque соответствующих блоков с помощью pop_back и push_front, а также обновим массивы счетчиков.

Второй запрос можно выполнить, просто вычислив сумму cnt[i] [k] по соответствующим блокам i.

Я получаю WA4, реализующий эту идею, я не могу найти ошибку в своем коде, поэтому это заставило меня задуматься, может быть, идея неверна. Что вы думаете?

это мое представление

 int n;

void decode(int amp;l, int amp;r, int lastans) {
    l = ((l   lastans - 1) % n);
    r = ((r   lastans - 1) % n);
    if (l > r)
        swap(l, r);
}

void decode(int amp;l, int amp;r, int amp;k, int lastans) {
    decode(l, r, lastans);
    k = ((k   lastans - 1) % n) 1;

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n; 

    vector<int> a(n);
    for (int i = 0; i < n; i  )
        cin >> a[i];

    int sqt = sqrt(n   .2)   1;
    vector<deque<int> > b(sqt);
    vector<vector<int> > cnt(sqt, vector<int> (n 1));
    for (int i = 0; i < n; i  ) {
        int blok = i / sqt;

        b[blok].push_back(a[i]);
        cnt[blok][a[i]]  ;
    }

    int q;
    cin >> q; 
    int lastans = 0;

    while (q--) {
        int l, r, k, t;
        cin >> t;

        if (t == 1) {
            cin >> l >> r; 
            decode(l, r, lastans);

            int b1, b2;
            b1 = l / sqt;
            b2 = r / sqt;

            if (b1 == b2) {
                int temp = b[b2][r%sqt];

                for (int g = r % sqt; g > l%sqt; g--) {
                    b[b2][g] = b[b2][g - 1];
                }
                b[b1][l%sqt] = temp;
            }
            else {
                int temp = b[b2][r%sqt];
                cnt[b2][temp]--;

                for (int g = r % sqt; g > 0; g--) {
                    b[b2][g] = b[b2][g - 1];
                }
                cnt[b2][b[b2].front()]--;
                b[b2][0] = b[b2 - 1].back();
                cnt[b2][b[b2].front()]  ;

                for (int g = b2 - 1; g > b1; g--) {
                    cnt[g][b[g].back()]--;
                    b[g].pop_back();
                    b[g].push_front(b[g - 1].back());
                    cnt[g][b[g].front()]  ;
                }
                cnt[b1][b[b1].back()]--;

                for (int g = (int)b[b1].size()-1; g > l%sqt; g--) {
                    b[b1][g] = b[b1][g - 1];
                }
                b[b1][l%sqt] = temp;
                cnt[b1][temp]  ;
            }
        }
        else {
            cin >> l >> r >> k; 
            decode(l, r, k, lastans);

            int b1 = l / sqt;
            int b2 = r / sqt;

            if (b1 == b2) {
                int ans = 0;

                for (int g = l % sqt; g <= r % sqt; g  ) {
                    ans  = b[b1][g] == k ? 1 : 0;
                }

                lastans = ans;
                cout << lastans << 'n';
            }
            else {
                int ans = 0;
                for (int g = l % sqt; g < b[b1].size(); g  ) {
                    ans  = b[b1][g] == k ? 1 : 0;
                }
                for (int g = b1   1; g < b2; g  ) {
                    ans  = cnt[g][k];
                }
                for (int g = 0; g <= r % sqt; g  )
                    ans  = b[b2][g] == k ? 1 : 0;
                lastans = ans;

                cout << lastans << 'n';
            }
        }
    }
}