Решение задачи Туфурама с Codeforces

С пояснением   Просмотров: 962

Однажды Поликарп решил пересмотреть свою любимую серию известного сериала «Туфурама». Но к своему удивлению, в ответ на запрос «Туфурама 3 сезон 7 серия смотреть онлайн в хорошем качестве без регистрации и смс» он получил лишь предложения посмотреть 3 серию 7 сезона. Это очень сильно смутило Поликарпа — ведь если ему захочется пересмотреть весь сериал, поисковик будет очень часто выдавать не те серии и сезоны, которые он хочет посмотреть! Поликарп решил заранее посчитать, сколько же раз ему придётся искать требуемую серию каким-то другим способом.

Всего в сериале n сезонов (пронумерованных от 1 до n), в i-м сезоне a i серий (пронумерованных от 1 до a i). Поликарп считает, что если для некоторой пары чисел x и y ( x < y) существует и серия x сезона y, и серия y сезона x, то для одного из этих запросов поисковик будет выдавать совсем не то, что он искал. Поэтому Поликарп хочет подсчитать количество таких пар. Помогите ему!

Код 

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 9;

int n;
int a[N];
int f[N];
vector <int> v[N];

void upd(int pos, int d){
	for(; pos < N; pos |= pos + 1)
		f[pos] += d;
}

int get(int pos){
	int res = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		res += f[pos];
	return res;
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", a + i);
		--a[i];
	}
		
	for(int i = 0; i < n; ++i){
		if(a[i] < N)
			v[a[i]].push_back(i);
		upd(i, 1);
	}
	
	long long res = 0;
	for(int i = 0; i < n; ++i){
		int to = min(N - 1, a[i]);
		res += get(to);
		for(auto x : v[i])
			upd(x, -1);
	}
	
	for(int i = 0; i < n; ++i)
	    if(i <= a[i])
	        --res;
    assert(res % 2 == 0);
    
	cout << res / 2 << endl;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Во-первых, наличие в сезоне более n серий не влияет на ответ, то есть можно сделать a i = min(a i, n).

Для решения данной задачи будем поддерживать следующий инвариант: в момент рассмотрения i-го сезона будем поддерживать все сезоны, в которых  ≥ i серий, тогда количество пар (i, y) это просто количество сезонов, номера которых  ≤ a i. Один из самых простых способов поддерживать этот инвариант — для каждого количества серий a i сохранить список всех номеров сезонов, имеющих столько серий. Тогда, обработав i-й сезон, достаточно просто удалить все сезоны, в которых ровно i серий.

Поддерживать сезоны и подсчитывать их количество можно поддерживая единицы и нули в BIT.

Однако текущий ответ учитывает каждую пару (x < y) два раза, а также содержит некоторые валидные пары (x, x), поэтому надо сначала удалить из ответа количество пар (x, x) (где a x ≥ x), и потом поделить на два.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp