Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### Wsl_F's blog

By Wsl_F, history, 7 months ago, translation, ,

Hi there! Rules of div 2 only contests were updated recently (allowing to participate purple in div 2 only rounds). I'm curious does this have an influence on the rating system. So. I've split all participants of this round by divisions and calculated rating change for them independently. You could find this results via following links: div1 only, div2 only. .

Let's define average rating change in the division as a sum of all rating changes of each contestant from this division divided by the number of participants in this division.

Division Average rating change
div. 1 only -8.09
div. 2 only -10.68

Let's calculate average rating change for the official result (rating calculates without separating by divisions)

Division Average rating change
div. 1 +3.86
div. 2 -12.21
both -10.81

As we can see, in combined round average purple contestants gain almost 12 additional rating points. In my opinion, this is quite unfair. Your thoughts?

•
• +43
•

By Wsl_F, history, 12 months ago, translation, ,

I was wondering if codeforces community might be able to give me some advice.

I'm doing the second year of my master's degree and need to write diploma project. I have created CF-Predictor for the previous course project. I would be really happy if I could exceed it for more scientific direction. Unfortunately, I have no idea what should it be. Could you please give me any advice for developing CF-Predictor in the more scientific way. May you know any other service (not too easy & not too hard for diploma project) that could make codeforces better? :)

•
• +96
•

By Wsl_F, history, 14 months ago, ,

В Украине достаточно давно (1 июня 2017г.) заблокировали доступ к куче российских компаний в том чисе Яндекс и Mail.Ru, Codeforces тоже перестал быть доступным в тот день, я так понимаю, из-за того, что хостится на серверах Mail.Ru.

Для свободного доступа к Codeforces я просто в настройках роутера убрал DNS сервер провайдера и поставил гугловский DNS (8.8.8.8). И все было хорошо до 16 сентября. В этот день неожиданно Codeforces стал доступен со всех мобильных операторов (Vodafone, Lifecell, Kyivstar) и стал ОЧЕНЬ МЕДЛЕННО грузится в универе и у меня дома :(

Я не большой специалист по сетям, попробовал пропинговать CF, вроде все нормально:

>ping codeforces.com
PING codeforces.com (212.193.33.27) 56(84) bytes of data.
64 bytes from codeforces.ptr.sgu.ru (212.193.33.27): icmp_seq=1 ttl=56 time=35.4 ms
64 bytes from codeforces.ptr.sgu.ru (212.193.33.27): icmp_seq=2 ttl=56 time=36.8 ms
64 bytes from codeforces.ptr.sgu.ru (212.193.33.27): icmp_seq=3 ttl=56 time=35.7 ms
64 bytes from codeforces.ptr.sgu.ru (212.193.33.27): icmp_seq=4 ttl=56 time=37.3 ms
^C
--- codeforces.com ping statistics ---
4 packets transmitted, 4 received, 0% packet loss, time 3002ms
rtt min/avg/max/mdev = 35.499/36.340/37.343/0.761 ms



Я пока вижу 2 способа решения проблемы:

1) открывать CF через опера впн, но тут минус в том, что флеш не грузится и делать взломы во время раунда не получится

2) раздавать интернет с мобильного, но тоже как-то не удобно каждый раз переподключаться к сети, когда решишь зайти на CF.

Кто-нибудь еще испытывает такую проблему? Может есть какие-нибудь более удачные способы решения?

•
• -4
•

By Wsl_F, history, 22 months ago, ,
UPD 2 Sep 2018

Hi guys! As I mentioned on previous contest I'm working on tool that predicts rating changes. I'm happy to present it now!

A huge amount of your nerve cells die every time when you wait for a rating update on Codeforces. Stop this! From now you could use this service, it calculates approximate rating changes for every contestant.

The most interested thing for you is extension. It partly modifies the contest standings page and shows approximate rating changes for every contestant. It is available for three browsers:

Extension in work:

Also you could find more detailed information (seed, rank, expected delta, etc.) here.

A project still in beta, so predictions are not very accurate. Average mistake around 5 points, but for the contestants at the back of standings it could be greater up to a few hundreds.

Tech details

I'd like to thank Rubanenko and all other members of NBHEXT developers team for your shared sources and MikeMirzayanov for the great Codeforces platforms with shared API & ratings formulas.

AWESOME UPD

Prediction for todays contest (cf #399) is absolutely matching real rating changes! Thanks for AlexDmitriev! He was close to find my bug in rating calculation:)

UPD

Thanking KieranHorgan now CF-Predictor has a new design. Check it out:)

•
• +187
•

By Wsl_F, history, 3 years ago, translation, ,

Hi guys!

First of all, sorry for my poor english and short translation:)

Now everyone could access rating formulas, and there is some not obvious mathematic formulas. So, I decided to check probability formula(probability that the i-th participant has better result than the j-th participant):

There was a lot of rating codeforces rounds, so it's easy to calculate this value by existing results. I choose cf rounds №200 — №350 (separately for each division). To solve this problem I wrote java program (sources). After getting results I copy/paste it to Excel and get plots:

for first division

for second division

Looks good, but lets try found something better:)

Unfortunately this formula doesn't look scientific, so I a little bit change it:

Now, lets build plots again

for first division

for second division

Now it's closer:)

•
• +269
•

By Wsl_F, history, 3 years ago, ,

UPD: Уже решено.

Всем привет! Встретилась задача и я не догадываюсь как ее решать((

Условие:

Есть взвешенное дерево из N (N <= 150 000) вершин Q (Q <= 75 000) запросов: найти кратчайшее расстояние между парой вершин.

Мои скудные соображения: 1. Традиционный поиск в ширину/глубину дает сложность O( N*Q ) — слишком много. 2. Алгоритм Флойда-Уоршелла дает O ( N^3 + Q) — еще хуже. 3. Мне кажеться, что должен быть какой-то препроцессинг за O(N * logN) или O(N^1.5) и выполнение запросов за O(log N) или O(N^0.5). На этом все((

Задача не с олимпиады или соревнования, нам показали пример вступительных билетов в магистратуру. Фото (на украинском) ниже:

•
• -29
•

By Wsl_F, history, 3 years ago, ,

Всем привет! Сегодня наткнулся на новость: "Сделка года: Snapchat купил одесский стартап Looksery за $150 млн". И вспомнил, что на кф есть организация, которая точно так же называется. Очень рад за них, это еще один пример на пользу олимпиадного программирования. Основатели популярного мобильного приложения Snapchat для обмена сообщениями в 2012 году отказались от$3 млрд, которые им предлагал Марк Цукерберг за проект. А в 2015 году Snapchat помог украинской команде совершить пока что самый крупный экзит в истории украинских стартапов. Редакции AIN.UA стало известно, что одесский Looksery стал частью Snapchat. CEO Looksery Виктор Шабуров и сотрудники компании от комментариев отказались. Сумма сделки, по данным редакции, составила около \$150 млн. По слухам, вся команда разработки украинского приложения из Одессы переедет в США.

Отдельное приложение Looksery исчезло из AppStore, став частью приложения Snapchat — если во время записи видеозвонка тапнуть по изображению своего лица, на экране появятся знакомые фильтры от Looksery.

источник

•
• +227
•

By Wsl_F, 4 years ago, ,

Здравствуйте! Не мог бы кто-нибудь подсказать, где найти portable версию gcc 4.9.2 для win 32?

Мы решили обновить версию компилятора на Киевской городской олимпиаде (и отборах) и попутно добавить поддержку С++11. Версию 4.9.2 выбрал, потому что на КФ такая)) Компьютеров для участников много, поэтому не хотелось бы проводить установку на каждый компьютер по отдельности.

Заранее спасибо

•
• +10
•

By Wsl_F, 4 years ago, translation, ,

I've finally received t-shirt from Russian code cup 2014! It seems that this is impossible (because of political situation between Russian and Ukraine) but mail.ru did it!

•
• +107
•

By Wsl_F, 4 years ago, translation, ,

On topcoder 1st december is tuesday...

•
• +42
•

By Wsl_F, 4 years ago, ,

Недавно я с удивлением узнал, что алгоритм, которым я пользовался для нахождения минимального пути в графе от одной вершины до остальных, не совпадает с классической дейстрой описанной на википедии или e-maxx. Теперь напишу, как я ищу минимальный путь.

1. Создаем линейный массив cost в котором будем хранить минимальное расстояние до каждой вершины. Инициализируем его БОЛЬШИМИ значениями, а для стартовой вершины запишем 0.
2. Создаем сет интов s, в него мы будем помещать вершины, которые стоит посетить. Изначально s содержит только стартовую вершину.
3. Пока s не пустой выполняем следующее
• берем вершину с начала s, обозначим ее через u, удаляем из сета;
• проходимся по всем ребрам идущим из u. Пусть текущее ребро соединяет вершину u с вершиной v и имеет вес w. Если cost[u]+w < cost[v] тогда обновляем значение для cost[v]= cost[u]+w и добавляем в s вершину v, так как мы нашли до нее "более короткий" путь.

В массиве cost содержаться минимальные расстояния до каждой вершины.

код:

const int inf= INT_MAX/2;
const int MaxN= 2000;
vector<pii> a[MaxN+5]; // список смежности.
//a[i][j].vartex – номер вершины смежной с i-ой,
//a[i][j].weight – вес ребра, соединяющего эти вершины.
int cost[MaxN+5];
...
int u,w;
int from; //номер стартовой вершины.

// заполняем массив БОЛЬШИМИ значениями
for (int i=0; i<=MaxN; i++)
cost[i]= inf;

set<int> s;
s.clear();
// кладем в начало сета "стартовую вершину" и ставим расстояние до нее 0
s.insert(from); cost[from]= 0;
int c;

while (!s.empty()) //пока сет не пустой
{
u= *s.begin(); c= cost[u];
s.erase(s.begin());
for (int i=a[u].size()-1; i>=0; i--)
{// проходимся по всем вершинам смежным с u
if (cost[a[u][i].vartex]>c+a[u][i].weight)
{// если до текущей вершины путь через u "короче"
cost[a[u][i].vartex]= c+a[u][i].weight; // обновляем значение в массиве
s.insert(a[u][i].vartex); // добавляем в сет
}
}
}



Я пока что точно не оценил сложность алгоритма, но надеюсь на что-то вроде O(E logV), где V – количество вершин, а E – количество ребер в графе. Из возможных преимуществ данного алгоритма можно считать: чуть более краткий код, корректность работы при отрицательном весе ребер.

И собственно вопрос)) можно ли этот алгоритм считать модификацией Дейкстры или он как-то по-другому называется? Или это вообще не ясно что?))

UPD Как уже написали хорошие люди, этот алгоритм неэффективный. так что лучше им не пользововаться

•
• +11
•

By Wsl_F, 4 years ago, ,

Данный пост продолжение этого
Для решения будет использоваться мой код класса дерево отрезков единичная модификация.

## 1. Дима и массив

Мама подарила мальчику Диме массив длины n. Массив этот не простой, а особенный. Дима может выбрать два числа i и d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000), и элемент с индексом i магически становится равным d. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от f до t? Дима легко справился с этими вопросами, сможете ли Вы?

### Технические условия

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

В первой строке находятся два целых числа n и q (1 ≤ n ≤ 5•105, 1 ≤ q ≤ 105) — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано n чисел a1, a2, ..., an (−1000 ≤ ai ≤ 1000) — начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может быть = или ?. Если строка начинается с =, то это операция присваивания. Далее следуют i и d, ограничения на которые описаны в условии. Если строка начинается с ?, то это запрос. Далее следуют числа f и t(1 ≤ f, t ≤ n).

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

Для каждого запроса выведите сумму чисел в массиве с индексами от f до t, по одному результату в строке.

#### Решение.

Это одна из классических задач на ДО. В качестве функции используется сумма.

#### Код

const int MaxN= 5*100*1000;
int a[MaxN+5];

int main()
{
ios::sync_with_stdio(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

int n,q;
cin>>n>>q;
for (int i=0; i<n; i++)
cin>>a[i];

SegmentTree<int> st(n,a);
char c;
int l,r;
int i,d;
for (int Q=0; Q<q; Q++)
{
cin>>c;
if (c=='?')
{
cin>>l>>r;
cout<<st.query(l-1,r-1)<<endl;
}
else
{ //c== '='
cin>>i>>d;
st.update(i-1,d);
}
}
return 0;
}


## 2. В стране невыученных уроков

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа l и r, и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от l до r включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие. Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.

### Технические условия

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

Первая строка содержит количество элементов n (1 ≤ n ≤ 105) в массиве. Во второй строке находится n чисел – элементы ai (1 ≤ ai ≤ 109) массива. В третьей строке находится количество запросов m (1 ≤ m ≤ 105). Далее в m строках находятся по три числа q, l, r (1 ≤ l ≤ r ≤ n). Если q = 1, требуется посчитать НОД элементов на промежутке [l, r], если q = 2, то надо заменить элемент в позиции l на число r.

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

Для каждого запроса с номером 1 в отдельной строке выведите ответ на запрос. Подсказка. Тут все просто:)

#### Решение.

Просто напишем функцию наибольшего общего делителя и передадим ее в качестве ассоциативной функции для ДО.

#### Код.

int gcd(int a, int b)
{
if (a==0) return b;
return gcd(b%a,a);
}

const int MaxN= 5*100*1000;
int a[MaxN+5];

int main()
{
ios::sync_with_stdio(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

int n,q;

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

SegmentTree<int> st(n,a,gcd);
char c;
int l,r;
int i,d;
for (int Q=0; Q<q; Q++)
{
cin>>c;
if (c=='1')
{
cin>>l>>r;
cout<<st.query(l-1,r-1)<<endl;
}
else
{ //c== '2'
cin>>i>>d;
st.update(i-1,d);
}
}
return 0;
}


## 3. Range Variation Query

Последовательность an задается следующей формулой: an = n2 mod 12345 + n3 mod 23456. Требуется много раз отвечать на запросы следующего вида: • найти разность между максимальным и минимальным значением среди элементов ai, ai+1, ...,aj; • присвоить элементу ai значение j.

### Технические условия

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

Первая строка содержит натуральное число k (k ≤ 100 000) — количество запросов. Следующиеk строк содержат запросы, по одному в строке. Запрос номер i описывается двумя целыми числамиxi, yi. Если xi > 0, то требуется найти разность между максимальным и минимальным значением среди элементов axi...ayi. При этом 1 ≤ xi ≤ yi ≤ 100 000. Если xi < 0, то требуется присвоить элементу a-xi значение yi. При этом -100 000 ≤ xi ≤ -1 и |yi| ≤ 100 000.

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

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

#### Подсказка.

Создать 2 дерева отрезков.

#### Решение.

В одном будем хранить максимум на отрезке, в другом – минимум. Нам понадобиться лишь написать функции минимума и максимума и передать в качестве 0 для минимума ОЧЕНЬ большое число, для максимума ОЧЕНЬ маленькое.

#### Код.

 int Max(int a, int b)
{
return max(a,b);
}

int Min(int a, int b)
{
return min(a,b);
}

const int MaxN= 100000;
const int inf= 1000*1000*1000;
int a[MaxN+5];

int main()
{

ios_base::sync_with_stdio(0);
cin.tie(0);
srand(__rdtsc());

for (LL i=0; i<=MaxN; i++)
a[i]= i*i % 12345 + i*i*i % 23456;

SegmentTree<int> stMin(MaxN,a+1,Min,inf);
SegmentTree<int> stMax(MaxN,a+1,Max,-inf);

int x,y,k;
cin>>k;
for (int i=0; i<k; i++)
{
cin>>x>>y;
if (x>0) cout<<(stMax.query(x-1,y-1)-stMin.query(x-1,y-1))<<endl;
else
{
stMin.update(-x-1,y);
stMax.update(-x-1,y);
}
}

return 0;
}



## 4. Можете ли Вы ответить на эти вопросы — 3

Задана последовательность целых чисел a1, a2, ..., an (|ai| ≤ 10000 , 1 ≤ n ≤ 50000). Над ней Вам следует выполнить m (m ≤ 50000) операций: • модифицировать i-ый элемент последовательности • для заданных x и y вывести MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

### Технические условия

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

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность a1, a2, ..., an. Третья строка содержит число m. Следующие m строк содержат запросы вида: • 0 x y: изменить ax на y (|y| ≤ 10000). • 1 x y: вывести MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

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

Для каждого запроса вывести ответ как требуется в задаче.

#### Подсказка.

Создадим структуру из 4 элементов: сумма на отрезке, максимальная сумма на отрезке (ответ на запрос), максимальная сумма начинающаяся с начала отрезка, максимальная сумма заканчивающаяся в конце отрезка.

#### Решение.

Создадим на этой структуре ДО. Функцию нужно задать следующим образом: сумма на отрезке, очевидно, равна сумме всех чисел; левая сумма – максимум среди [левая сумма левого отрезка], [сумма всех чисел левого отрезка и левая сумма правого отрезка]; правая сумма – максимум среди [правая сумма правого отрезка], [сумма всех чисел правого отрезка и правая сумма левого отрезка]; максимальная сумма – максимум среди [максимальная сумма левого отрезка, максимальная сумма правого отрезка, правая сумма левого отрезка+левая сумма правого отрезка]

#### Код.

const int inf= 16000;

class Four
{
public:
int leftSum,rightSum,maxSum,sum;
Four()
{
leftSum= -inf;
rightSum= -inf;
maxSum= -inf;
sum= 0;
}

Four(int a, int b, int c, int d)
{
leftSum= a;
rightSum= b;
maxSum= c;
sum= d;
}
};

Four maxSum(Four a, Four b)
{
Four res;
res.leftSum= max(a.leftSum,a.sum+b.leftSum);
res.rightSum= max(b.rightSum,b.sum+a.rightSum);
res.maxSum= max(a.maxSum,max(b.maxSum,a.rightSum+b.leftSum));
res.sum= a.sum+b.sum;
return res;
}

const int MaxN= 50000;
Four a[MaxN+5];

int main()
{

ios_base::sync_with_stdio(0);
cin.tie(0);
srand(__rdtsc());

int n;
cin>>n;
{
int t;
for (int i=0; i<n; i++)
{
cin>>t;
a[i]= Four(t,t,t,t);
}
}

Four zero(-inf,-inf,-inf,0);
SegmentTree<Four> st(n,a,maxSum,zero);

int x,y,m,q;
cin>>m;
Four t;
for (int i=0; i<m; i++)
{
cin>>q>>x>>y;
if (q==1)
{
t= st.query(x-1,y-1);
cout<<t.maxSum<<endl;
}
else
{
st.update(x-1,Four(y,y,y,y));
}
}

return 0;
}


•
• +7
•

By Wsl_F, 4 years ago, ,

Тема данного поста — не нова, но, наверняка, кому-нибудь пригодится:) Начнём с примера задачи, в которой используется дерево отрезков.

Имеется массив из n (n≤10^5) целых чисел, нужно находить сумму на отрезке от l до r (0≤l,r≤n-1) и изменять значение i-го
(0≤i≤n-1) элемента. Количество запросов m (m≤10^5).

Очевидно, что наивное решение работает за O(n*m), а дерево отрезков дает возможность решать данную задачу с асимптотикой O(m*log2n).

Существует множество разных видов деревьев отрезков. В данной статье дерево отрезков – структура данных, которая по имеющейся последовательности из n чисел умеет выполнять быстро (за логарифмическое время) 2 вида запросов:

1) Изменить значение i-го элемента
2) Вычислить значение некоторой фиксированной ассоциативной функции на отрезке от l до r.

Что же собой представляет дерево отрезков(ДО)? ДО – бинарное дерево (обычно, для удобства дополняют до полного нулевыми элементами), в котором листьями являются элементы исходного массива, а в каждой вершине записано значение функции f от двух сыновей. То есть в листах записано значение функции на отрезке длинной 1, в родителе записано значение функции на отрезке длинны 2, в родителе которого – 4… таким образом, в каждой вершине записано значение функции на некотором отрезке, что и послужило поводом для такого названия.

Для нашего примера задачи функция f – сумма, тогда ДО для четырех элементов будет выглядеть следующим образом:

Если же у нас количество элементов (n) не является степенью двойки, то мы дополним их нулями. (В общем случае, когда мы работает с типом данных Т и функцией f, то ноль — такое значение, что для любого x из T верно f(x,ноль)=x.) Например, ДО сумм для 3 элементов будет выглядеть так:

Как же хранить ДО? Существует 2 способа:
• структуры на указателях;
• линейный массив.

На сколько мне известно, первый способ используют только для персистентных ДО. Мы же пока разбираем самую обычную и простую модификацию ДО, поэтому воспользуемся вторым способом. Создадим линейный массив a из 2*nMax элементов, где nMax – наименьшая степень двойки, которая не превосходит n. В первом элементе (a[1]) будем хранить корень дерева, а для каждой вершины i её сыновья хранятся в ячейках с номерами 2*i (левый сын), 2*i+1 (правый сын). Почему для хранения достаточно 2*nMax элементов? Мы имеем nMax листов, у них nMax/2 родителей, у них nMax/4 … и 1 корень, очевидно, что эта сумма (1+2+4+…+ nMax/4+ nMax/2+ nMax) равняется 2*nMax-1.

На рисунке проставим возле каждой вершины ее индекс в массиве:

А в массив дерево будет уложено следующим образом:

Теперь определим, какие операции мы хотим выполнять с нашим ДО:
1) построить ДО;
2) узнать значение i-го элемента;
3) изменить значение i-го элемента;
4) найти значение функции на отрезке от l до r.

### Разберем по очереди все операции.

#### 1 Построить дерево отрезков.

Пусть у нас есть массив b из n элементов. Для начала нам нужно найти nMax (наименьшая степень двойки, которая не превосходит n). Это можно реализовать как через формулу:

nMax = (1 << (int)(log2(1.0*(n-1)) + 1);


так и простеньким циклом:

nMax= 1;
while (nMax<n) nMax<<= 1;


Далее нужно заполнить массив a нулями (соответствующего типа) и заполнить листы ДО значениями из массива b (мы помним, что в ДО индексы листьев от nMax до 2*nMax-1):

for (int i=0; i<n; i++)
a[nMax+i]= b[i];


На данный момент имеем:

Теперь осталось только заполнить значения во всех родителях. Это можно сделать за один линейный проход (помним, что у i-ой вершины сыновья с индексами 2*i и 2*i+1, а в вершине мы храним значение функции от двух сыновей):

        for (int i=nMax-1; i>0; i--)
a[i]= f(a[2*i],a[2*i+1]);


Таким образом мы построили ДО с асимптотикой O(nMax) = O(n).

#### 2 Узнать значение i-го элемента.

Как уже писалось ранее у нашего ДО листья имеют индексы от nMax до 2*nMax-1, поэтому значение i-го элемента элемента находиться в ячейке с индексом nMax+i: return a[nMax+i] Очевидно, что данный запрос выполняется за константу.

#### 3 Изменить значение i-го элемента.

Если мы изменим значение в листе дерева, то все значения на пути к корню от данного листа перестанут соответствовать действительности, поэтому их нужно пересчитать, в остальных же останутся корректные значения. Как известно, глубина полного бинарного дерева из m вершин равна log2m, поэтому мы должны выполнить данную операцию за логарифмическое время. Например, изменим a2 на a2 I :

Красным цветом выделены вершины, в которых нужно изменить значения.

Что бы «обновить» ДО нам нужно записать в лист новое значение, а затем подняться до корня, каждый раз пересчитывая значение функции в вершине. Изменить значение в листе очень просто (вспомним, что индексы листьев от nMax до 2*nMax-1). Значение i-го листа имеет индекс nMax+i :

       a[nMax+i]= newValue;


Теперь осталось подняться до корня, это можно сделать с помощью цикла:

        while (i>1)
{
i/= 2;
a[i]= f(a[2*i],a[2*i+1]);
}


#### 4 Найти значение функции на отрезке от l до r.

Наконец-то, мы добрались до самого интересного запроса. Стоит отметить, что частный случай, когда l=r разобран в пункте 2 и выполняется за константу, в общем же случае асимптотика логарифмическая.

Введем определения.

Фундаментальный отрезок – такой отрезок, для которого существует вершина в дереве, хранящая значение функции на данном отрезке.

Уровень. Уровень корня – 1, а для каждого сына уровень на единицу больше, чем у родителя.

Для того, что бы вычислить значение функции на отрезке, нам необходимо разбить его на МИНИМАЛЬНОЕ количество фундаментальных отрезков. Что бы найти значение для любой вершины (кроме листа), нам нужно знать значения для сыновей. Мы будем спускаться по ДО. Изначально встаем в корень. Пусть мы находимся в какой-то вершине. Рассмотрим 3 возможных случая: отрезок [l..r] совпадает с отрезком, соответствующим текущей вершине, отрезок [l..r] полностью принадлежит одному из сыновей, отрезок принадлежит обоим сыновьям. В первом случае просто возвращаем посчитанное значение из ДО, во-втором – спускаемся в данного сына, в-третьем же случае разобьем данный отрезок на два: [l..правый конец левого сына] и [левый конец правого сына..r]. Рекурсивно вычислим значения для каждого из них.

Рассмотрим на примере. Пусть у нас есть ДО для 8 элементов, запишем, какой отрезок соответствует каждой вершине:

А теперь посмотрим, как будет выполняться запрос для отрезка [1..5].

Сначала встаем в корень — наш отрезок принадлежит обоим сыновьям. Значит, нам нужно разбить его на 2 отрезка: [1..3] и [4..5]. Для каждого из них рекурсивно вычислить значение. Далее отрезок [1..3] опять принадлежит 2 сыновьям, разбиваем его на 2 отрезка: [1..1] и [2..3]. Отрезок [1..1] принадлежит только правому сыну, спускаемся в него и видим, что отрезок [1..1] – фундаментальный. Берем для него значение из вершины, и поднимаемся до 2 уровня (вершина [0..3]). Для левого сына мы уже рекурсивно посчитали, теперь посчитаем для правого: спускаемся в него. Отрезок [2..3] – фундаментальный, берем значение из вершины. Возвращаемся в [0..3] и уже можем вычислить значение для отрезка [1..3], так как значение функции уже вычислили для обеих его частей. Возвращаемся в корень и спускаемся в правого сына [4..7], наш подотрезок ([4..5]) принадлежит только одному левому сыну, спускаемся в него. Вершине соответствует отрезок [4..5], следовательно, он — фундаментальный, берем из вершины значение. Возвращаемся в корень и вычисляем ответ.

Почему этот запрос выполниться за логарифмическое время? Как известно, глубина (количество уровней) дерева из n вершин равняется log2n, кроме того, утверждается, что на каждом уровне мы посетим не более 4 вершин, таким образом, мы посетим O (log2n) вершин. Рассмотрим код. Для вычисления значения на отрезке нам понадобится вызвать рекурсивную функцию от 5 аргументов, для удобства напишем функцию, которая по 2 аргументам (границы отрезка для запроса) вызывает функцию 5-и аргументов и возвращает значение:

T query(int l, int r)
{// return value function f on the segment [l;r]
return query(l,r,0,nMax-1,1);
}


Теперь наша рекурсивная функция:

T query(int l, int r, int leftPosition, int rightPosition, int v)
{// return value function f on the intersection segments [l;r] and [leftPosition;rightPosition]
// l – левая граница запроса
// r – правая граница запроса
// v – текущая вершина дерева отрезков
// [leftPosition; rightPosition] – отрезок соответствующий v

if (r<l) return zero;
//если отрезок не существует, то возвращаем ноль.
if (l==leftPosition && r==rightPosition) return a[v];
// если отрезок фундаментальный,то возвращаем значение из вершины
// раз мы дошли сюда, то отрезок принадлежит сыновьям
int middle= (leftPosition+rightPosition)/2;
// вычисляем правую границу левого сына
return f(query(l,min(middle,r),leftPosition,middle,v*2),
query(max(l,middle+1),r,middle+1,rightPosition,v*2+1));
// рекурсивно вычисляем запросы для сыновей
}


Мой код класса дерево отрезков единичная модификация.

Скоро выложу несколько примеров задач с решениями с использованием опубликованного класса.

P.S. Буду рад конструктивным замечаниям/предложениям по написанию статьи/кода

UPD: вот примеры

•
• +57
•

By Wsl_F, 4 years ago, ,

Я, конечно, не в праве требовать, но все же интересно, почему вчера целый день не работал кодефорсес?))

•
• +32
•

By Wsl_F, 5 years ago, ,

26 апреля 2014 года пройдет I этап ACM 2014/15 в Украине. разные документы/приказы по этому поводу.

Всем удачи и больших квот:)

•
• +11
•

By Wsl_F, 5 years ago, ,

Здравствуйте! Появилась следующая проблема. Решаю задачу с e-olimp, и мое решение проходит только первый тест. Подобрать вручную тест, который не пройдет мне не удалось. Тогда я вспомнил про стресс тесты (моя первая попытка), написал лобовое решение, генератор и батник. запустил все это дело и за 2 часа так и не удалось найти тест, на котором программы работают по-разному. Подскажите, пожалуйста, как лучше писать стресс тесты? или может я что-то не так понимаю?

@ echo off
:1
echo good
gener.exe
brut.exe
2.exe
fc /L output.txt output_brut.txt
if %errorlevel% == 0 goto 1
echo NeSovpalo
pause



спасибо за помощь

UPD новое лобовое решение + в генераторе изменил количество тесто на 10 000. запустил, жду...