Здесь представлены темы заключительного этапа Республиканской Олимпиады (Казахстан) по информатике. (просмотреть)

Олимпиада пройдет с 24 по 28 марта 2024 года в Алматы.

Republic Olympiad Topics for preparation

====== lvl 1 | basic knowledge =====

Introductory lesson

math (formulas, basic mathematic operations)

if/else

loop

string, array

asymptotics

sort (bubble, merge)

STL, map, set

======= lvl 2 | pre-intermediate =====

Two pointers

Binary Search/Ternary Search

prefix sum

sliding window

functions / recursion (prime)

Bruteforce

Greedy

scan line

permutation

========= lvl 3 | intermediate ===============

prime, factorization, number theory

dp basic

graph, dfs, bfs

Sieve

combinatorics

modular arith

Hash

========= lvl 4 | upper-intermediate ==========

fenwick tree

sqrt decomposition

Segment Tree

Sparse Table

TopSort

Eulerian cycle, path

Finding path algos

dsu, mst

bitmasks and dp bitmasks

Mo's Algo

digit dp

DP on substring

invariant, monovariant, dirichlet

======== lvl 5 | advanced ========

Cut vertices, edges

SCC

lca

Z algo/Prefix func

trie

meet in the middle

small to large

dp on trees

Inclusion-Exclusion, Probability

Expected val

segment tree lazys

======== lvl 6 | proficient ======

Nim

Persistent Data Structures

Maximum bi-partition (Kuhn's algo)

Matrixes

Author: bash

По условию задачи, есть 2 вида запросов:

1) Вывести количество элементов на отрезке $$$[l,r]$$$, то есть от позиции $$$l$$$ до позиции $$$r$$$ количество таких $$$a_i$$$, что $$$a_i$$$ $$$\ge$$$ $$$c$$$.

2) Поменять значение на позиции $$$pos$$$ на $$$val$$$.

Как будем хранить элементы массива?

Используем метод Sqrt-декомпозиции. Это такой метод (структура данных), которая позволяет нам работать над массивами большущих размеров. Итак, давайте разобьем массив на $$$k$$$ блоков длины $$$n/k$$$. Будем хранить $$$k$$$ векторных массивов, то есть

vector<int>b[k];

Далее, при инициализации элементов массива $$$a$$$, будем добавлять $$$a_i$$$ в блок с номером $$$b[i/k]$$$. Затем, после добавления всех элементов, отсортируем каждый блок по неубыванию. Массив $$$a$$$ должен быть нулевой индексации.

Отвечаем на запросы на готовом упрощенном массиве.

1-й вид запросов На тех блоках, которые полностью входят в наш отрезок $$$[a,b]$$$, мы будем просто делать бинарный поиск. И $$$(n/k)-cnt(good)$$$ будет ответом на один из блоков, где $$$cnt(good)$$$ — количество не подходящих нам чисел, то есть тех, которые меньше $$$c$$$. Если же блок полностью не входит в отрезок, мы там просто в лоб пройдемся от позиции $$$a$$$ до позиции $$$(l1+1)*k-1$$$, где это первая позиция, относящаяся самому первому блоку слева. Аналогично сделаем и справа, где блок стоит правее, чем конечная позиция последнего блока.

2-й вид запросов Для выполнения такого запроса мы просто поменяем значение сначала $$$b[block][i]$$$, которое равно числу, стоящему на позиции $$$pos$$$ в массиве $$$a$$$, на значение $$$val$$$. $$$block$$$ — это номер блока, в котором находится $$$a_{pos}$$$. Затем меняем само значение $$$a_{pos}$$$ , и сортируем изменившийся блок.

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

КОД:

#include <bits/stdc++.h>
using namespace std;
const long long maxn=5e5+1;
int n,q,a[maxn],k=400;
vector<int>b[maxn];
int main(){
       cin>>n;
       for(int i=0;i<n;i++){
              cin>>a[i];
              b[(i/k)].push_back(a[i]);
       }
       for(int i=0;i<(n/k);i++){
              sort(b[i].begin(),b[i].end());
       }
       cin>>q;
       while(q--){
              int t;
              cin>>t;
              if(t==1){
                     int pos,val;
                     cin>>pos>>val;
                     pos--;
                     int bl=pos/k;
                     for(int i=0;i<b[bl].size();i++){
                            if(b[bl][i]==a[pos]){
                                   b[bl][i]=val;
                                   break;
                            }
                     }
                     a[pos]=val;
                     sort(b[bl].begin(),b[bl].end());
              } else{
                     int l,r,val;
                     cin>>l>>r>>val;
                     l--,r--;
                     int b1=l/k,b2=r/k,res=0;
                     if(b1==b2){
                            for(int i=l;i<=r;i++){
                                   if(a[i]>=val) res++;
                            }
                     }
                     else{
                            for(int i=b1+1;i<b2;i++){
                                   int pos=lower_bound(b[i].begin(),b[i].end(),val)-b[i].begin();
                                   res+=(b[i].size()-pos);
                            }
                            for(int i=l;i<=((b1+1)*k)-1;i++){
                                   if(a[i]>=val) res++;
                            }
                            for(int i=b2*k;i<=r;i++){
                                   if(a[i]>=val) res++;
                            }
                     }
                     cout<<res<<'\n';
              }
       }
}

Ислам Сипатталов ( каз. Ислам Даниярұлы Сипатталов, род. 28 сент. 2008, Актобе, Казахстан) — ученик Актюбинского областного специализированного лицея-интерната "Білім-Инновация" для одарённых юношей.

Краткая биография

Ислам родился 28 сентября 2008 (воскресенье) в обычной казахской семье. В 2011 году родители сдали его в детский садик, который был неподалёку от дома. В 2013 году он зачисляется в Городской Художественный Лицей города Актобе, в детскую группу. Первый звонок прозвенел для Ислама в сентябре 2015 года. Он учился в СШЛ №27 города Актобе. Затем, когда его любимая классная руководительница переехала в Россию, в классе началась делёжка, новый руководитель не пришёлся по душе родителям, участились скандалы. Незадолго после начала второго класса, Ислам переходит в СШГ №9 города Актобе. Там он проучился 5 лет. С 2017 по 2021 года ходил в лингвистический центр "DARINA", на английский язык. В апреле 2021 года он успешно сдал и прошел экзамен в БИЛ, а затем в конце мая в НИШ. Пред ним стал трудный выбор, но вскоре он решился пойти учиться в БИЛ.

  Творчеством Ислам занимается ещё с раннего детства. Как говорилось ранее, Ислам учится в Художественном Лицее города Актобе с 2013 года (11 лет). Он пошёл туда по инициативе мамы, будучи ещё в садике. До 5 класса учился в детской группе. Как правило, при переходе в 5-й класс общеобразовательной школы, он перешёл в 0-й класс в Художественном Лицее. Сейчас учится в 4-м классе, на заключительном этапе художественного образования.