AmerM

A. Кролики

ограничение по времени на тест

2 секунды

ограничение по памяти на тест

256 мегабайт

ввод

стандартный ввод

вывод

стандартный вывод

У Айбара есть сад, который состоит из KK подряд идущих грядок. В саду живут nn кроликов. Каждый кролик находится в одной из грядок. Иногда кролики могут переходить в соседние грядки. Также, иногда Айбару нужно узнать количество кроликов, которые находятся на каком-то отрезке, чтобы их покормить. Айбару дано qq запросов, которые надо обработать. Они бывают следующих типов:

• Кролик номер x(1≤x≤n)x(1≤x≤n) перешел на одну грядку налево или направо. При этом гарантируется, что кролик не выйдет за пределы сада
• Посчитать количество кроликов на отрезке от грядки ll до грядки rr (1≤l≤r≤K)(1≤l≤r≤K) включительно.

Входные данные

В первой строке входных данных даны два числа - nn и KK. Далее во второй строке указаны nn чисел - изначальное положение каждого кролика. Затем в отдельной строке следует число qq и qq строк описывающих запросы. Запросы задаются в следующем формате:

• L xL x - сдвинуть кролика номер xx на одну грядку налево
• R xR x - сдвинуть кролика номер xx на одну грядку направо
• G lrG lr - Посчитать и вывести количество кроликов на отрезке от грядки ll до грядки rr включительно.

Выходные данные

В выходные данные выведите по одному числу для каждого запроса третьего типа в отдельной строке.

Система оценки

Подзадача 1 (20 баллов) — 1≤n, K, q≤10001≤n, K, q≤1000

Подзадача 2 (20 баллов) — 1≤n, K, q≤5∗1051≤n, K, q≤5∗105, отсутствуют запросы сдвига кролика

Подзадача 3 (60 баллов) — 1≤n, K, q≤5∗105

как можно решить задачу? Я пробовал через дерево отрезков но зашло только на 20 баллов

Akezhan_Askar

Какой у тебя код?

1 ответ

Zhabka

Что именно ты пробовал, распиши

1 ответ

AmerM

#include <bits\stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
// solve it
const ll mod = 1e9 + 7;

ll n, k;
ll a[100001]={};
ll t[400001];

void build(ll v=1, ll tl=1, ll tr=k) {
if(tl == tr) {
if(a[tl] > 0) t[v]=a[tl];
} else {
ll tm = (tl + tr) / 2;
build(v+v, tl, tm);
build(v+v+1, tm+1, tr);
t[v] = t[v+v] + t[v+v+1];
}
}

ll get(ll l, ll r, ll v=1, ll tl=1, ll tr=k) {
if(tl > r || tr < l) {
return 0;
} else if(l <= tl && tr <= r) {
return t[v];
}
ll tm = (tl+ tr) / 2;
return get(l, r, v+v, tl, tm) + get(l, r, v+v+1, tm+1, tr );
}

int main() {
cin >> n >> k;
int b[n+1];
for(int i=1; i<=n; i++) {
cin >> b[i];
a[b[i]]++;
}
build();
ll q;
cin >> q;
while(q–) {
char s;
cin >> s;
if(s == ‘L’) {
ll x;
cin >> x;
a[b[х]]–;
b[х]–;
a[b[х]]++;
build();
} else if(s == ‘R’) {
ll x;
cin >> x;
a[b[х]]–;
b[х]++;
a[b[х]]++;
build();
} else {
ll l, r;
cin >> l >> r;
cout << get(l, r) << endl;;
}
}

}

1 ответ

Akezhan_Askar

Каждый запрос на сдвиг кролика влево или в право работает за klogk

AmerM

В массиве а[v] записал число кроликов в каждой норке и в массиве t[v] сделал дерево отрезков.
когда надо было сдвинуть кроликов в другую норку я отнимал на 1 число кроликов в текущей норке и смотря на направление прибавлял на 1 в соседней и активировал процедуру build еще раз. А при выводе выбирал с дерево блоки которые входили в отрезок l и r.

1 ответ

Akezhan_Askar

Пересчитывание дерева отрезков работает слишком долго. Заметь что при каждом запросе на сдвиг кролика меняются не все вершины а только 2. Можно создать новый запрос который прибавляет какое то число в точке.

1 ответ

fractal

И теперь вопрос, зачем тут ДО?

1 ответ

AmerM

Чтобы быстрее считать число кроликов на отрезках

1 ответ

ershuku

можно написать сумму на префиксе и поскольку кролики сдвигаются только на одну позицию можно изменить просто 2 соседних позиции на префикс сумме.