Wataru

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

Однако, скорее всего вам не надо считать это количество для одной заданной вершины, а просуммировать по всем (задача вроде - найти сколько в графе треугольников).

В таком случае есть более эффективное решение (хоть и с такой же кубической асимптотикой). Суть в том, чтобы перебирать не вершину треугольника, а ребро. Тогда вопрос будет подсчитать, сколько вершин связанны с заданными двумя. Что равносильно: Найти в скольких столбцах матрицы смежности стоят единицы в двух заданных строках. Это линейный проход, но его можно в 64 раза ускорить, если использовать битовое сжатие. Храните матрицу смежности в битах 64-битных чисел. Т.е. один столбец long long матрицы будет отвечать за 64 столбца. В таком виде можно с-AND'ить два числа и потом подсчитать, сколько в числе единичных бит (что тоже можно сделать сильно быстрее, чем за 64 операции).

Есть за O(n log m) решение, но оно технически сложноватое. Реализуется через балансированное бинарное дерево поиска с неявным ключем. Грубо говоря, если в каждой вершине балансированного дерева хранить сколько всего вершин в поддереве, то в такой структуре можно искать вершину по номеру. Можно так же в это дерево вставлять вершину на заданную позицию.

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

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

При расшифровке - прочитанное число указывает на порядковый номер вершины в дереве. Находите вершину, ее значение пишите в ответ, удаляете вершину и добавляете в начало.

Edit: тут было неправильное решение через недо-skip-list.

Есть чуть более простое в реализации решение, но на той же идее. Вместо бинарного дерева поиска используйте дерево отрезков.

Заведите отрезок на n+m элементов. Кадому символу в алфавите будет соответствовать еденица где-то в этом отрезке. Изначально они занимают n самых правых позиций. Их порядок - это будет та самая перестановка из условия. Дервево отрезков будет считать сумму. В таком дереве можно за логарифм найти k-ую еденицу (рекурсивный спуск) и узнать какой по порядку является данная еденица (запрос на сумму на отрезке 0..i-1). Еще для каждого символа алфавита храните, где именно на отрезке лежит соответствующая ему еденица, а для каждого элемента на отрезке, какому символу он соответствует.

При шифровании вы находите еденицу для символа алфавита, считаете какая она по порядку и выводите это число. потом перемещаете эту еденицу левее всех едениц. Это делается просто - на i-ой операции надо втыкать еденицу в позицию m-i+1.

При дешифровании вы находите к-ую еденицу, выводите соответствующий ей символ и перемещаете еденицу левее остальных.

Похоже, на строке "abcdef" у вас выдаст d=0, а может и вообще d не напишет.

Проблема в том, что вы пытаетесь считать параллельно для правой и левой половины. Логично, коэффициенты там симметричные будут, но можно сделать ошибку. И ускорения ваша оптимизация практически не несет. В 2 раза меньше итераций, делающих в 2 раза больше + дополнительная проверка каждый раз. На компилируемых языках может быть еще и медленнее наивного цикла от 0 до n-1. В питоне - не знаю. Уж точно не в 2 раза быстрее, как можно было бы подумать.

Еще, я бы вместо последовательного обновления коэффициента в previous считал его явно. i-ый символ встречается ровно в (i+1)*(n-i) подстроках.

Не понимаю, в чем проблема вообще. Забудьте, что это строки или числа. Все что нужно для бинпоиска - это уметь спрашивать < или = искомая штука и штука в массиве по заданной позиции.

В питоне есть массивы (доступ по индексу) и строки он сравнивает автоматом через операторы == и <.

Т.е. можно написать тот же абсолютно код, что и для бинпоиска по числам и он будет работать на строках. Правда, надо помнить, что сложность у бинпоиска по строкам будет не O(log n), а O(L log n), где L - максимальная длина строк.

Попробуйте читать через scanf.

Я вижу, вы делаете через sync_with_stdio(0), но я не уверен, что это 100% помогает.

Потом, вместо set vis достаточно передавать в dfs предыдущую вершину и не ходить в нее.

А еше у вас ошибка, при делении ребра пополам нельзя делить пополам cnt*w. Если cnt четное, а w нечетное, вы потереяете округление. Надо пихать в кучу пару cnt, w, и брать максимальное cnt*ceil(w/2). И еще, вы пихаете в кучу цену ребра, помноженную на количество листьев по этому ребру и всем предыдущем в текущей вершине! Надо там не cur брать, а значение dfs.

И еще, оно скорее всего виснет из-за переполнения. При умножении cur*c.second может получиться отрицательное число, вы же int-ы перемножаете, и только потом к long long приводите.

Во-первых, перенесите центр системы координат в центр элипса - вычтите его из всех координат точек касания. В самом конце надо будет сделать обратный переход и подставить x=x-x0, y=y-y0 в уравнение.

При выборе правильной системы координат, эллипс становится окружностью, ведь его уравнение x^2/a^2+y^2/b^2=1. Все остальное - это от переноса центра координат и поворота эллипса.

Давайте переобразуем нашу систему координат, повернув на какой-то угол и сжав вдоль оси X, чтобы получить круг.

с- cos(угол), s=sin(угол) k- коэффициент сжатия.

Тогда новая система координат - {kc,ks}, {s,-c}. Преобразуем в эту систему координат тички касания и вектора касательных. Они так и останутся касающимися нашего эллипса, ведь преобразования поворота и сжатия оставит прямые прямыми, а эллипс - эллипсом (или кругом).

Если x1,y1 - точка касания, а {xv, yv} - вектор касательной, то:

x1' = x1*kc+y1*ks

y1' = x1*s-y1*c

xv' = xv*kc+yv*ks

yv' = xv*s-yv*c

Это просто формулы перобразования между системами координат. Аналогично можно сделать для x2', y2', xw,' yw'.

Теперь составим уравнения. Мы же хотим найти преобразование, в котором наш эллипс будет окружностью. Во-первых, расстояния до точек касания должны быть одинаковыми. Во-вторых, касательные вектора должны быть перпендикулярны векторам из начала координат к точкам касания.

Если аккуратно расписать x1'*x1'+y1'*y1'-x2'*x2'-y2'*y2' = 0, и заменить c^2=1-s^2, то будет:

(y1*y1-y2*y2-x1*x1+x2*x2)*kkss + (2*x1*y1-2*x2*y2)kkcs + (x1*x1-x2*x2-y1*y1+y2*y2)ss +(2*x2*y2-2*x1*y1)*cs +(x1*x1-x2*x2)*kk+(y1*y1-y2*y2)=0

Советую не верить мне тут с коэффициентами, а пепроверить их самостоятельно.

Аналогичные уравнения для касательных x1'*xv'+y1'*yv' = 0:
(y1*yv-x1*xv)*kkss + (x1*yv+y1*xv)kkcs + (x1*xv-y1*yv)ss +(-x1*yv-y1*xv)*cs +(x1*xv)*kk-y1*yv=0

Важно заметить, что у нас тут 3 уравнения вида:

A*kkss+B*kkcs-Ass-Bcs+Ckk+D=0, где константые коэффициенты A,B,C,D (разные в трех уравнениях) и 3 переменные k,s,c. Еще есть дополнительное условие s*s+c*c=1, это же синусы/косинусы угла, и k!=0. k может быть и отрицательным, это означало бы отражение и сжатие системы координат. Под наши цели подходит.

Обратите внимание, 3-е и 4-ое слагаемые идут с теми же коээфициентами, что и 1-е и 2-е, но с обратными знаками. Можно подобрать такие коээфициенты для первых двух уравнений, что если их прибавить к тертьему уравнению, то коэффициенты перед kkss,kkcs,ss,cs - все станут равны нулю. Это надо решить систему из двух линейных уравнений.
Пусть коээфициенты в уравнениях A1,A2,A3,B1,B2,B3,C1 и т.д. (напоминаю, это константы, вычеслимые через заданные координаты точек и векторов касания). Введем 2 переменные x, y - коээфециенты, с какими прибавлять первые 2 уравнения к тертьему. Условия: A1*x+A2*y+A3=0, B1*x+B2*y+B3=0. Решив эту систему уравнений, найдя коээфициенты и прибавив первые 2 уравнения к тертьему, вы получите уравнение вида

C4*k*k+D4=0

Элементарно решив его, вы найдете k. Подставив его в 2 предыдущих уравнения вы получите 2 уравнения вида:

A4*ss+B4*cs + D4 = 0

Это тригонометрическое уравнение можно решить, дописав множитель cc+ss к D4, получив уравнение вида:

(A4+D4)*ss+B5*cs+D4*cc = 0.

Теперь осталось поделить обе части на с^2 и решить квадратное уровнение для tan(). Еще, правда, надо рассмотреть подходит ли c=0,s=1 (s=-1 рассматривать не надо, Ведь без разницы, в какую сторону вращать на 90 градусов - все равно ось сжатия будет одна и та же).

Теперь зная тангенс найдите косинус и синус (школьные тригонометрические формулы, вроде c=sqrt(1/(1+t^2)).

Все, мы знаем k,c,s. Подставив их в формулы для x1',y1' мы узнаем радиус окрудности (расстояние до нуля). Пусть радиус будет r.

Теперь уравнение эллипса x'^2+y'^2 = r^2.

Подставляем преобразование:

x'=x*k*s+y*k*c, y' = x*s-y*c. Потом не забываем сделать замену x<-x-x0, y<-y-y0, чтобы верунть центр эллипса в заданное место.

Все эти замены надо аккуратно подставить и раскрыть скобки в уравнении x'^2+y'^2 = r^2 и получить ваши коээфициенты в уравнении Ax2+ Bxy + Cy2 + Dx + Ey = F. Потом поделите обе части на F.

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

Edit:

Тут есть потенциальная проблема - надо решить систему линейных уравнений и 2 квадратных уравнения в процессе решения. Я не могу доказать, но верю всей душой, что, если эллипс существует, то все эти уравнения будут решатся в вещественных числах, без делений на 0 и квадратных корней из отрицательных чисел.

Проверка на малых числах не всегда работает. там фибоначи, квадрат и черт знает что похожи.

Если у вас там что-то вроде for "i=1...n do for j = i..n do" или каике-то еще 2 вложенных цикла, где внутренняя переменная бежит от или до внешней переменной, то точное количество итераций будет n(n+1)/2, что есть O(N^2).

Ваше последнее суждение - верно.

Вы говорите, что пытаетесь брать числа, чтобы "портить" меньшие биты, но ведь это может быть не так.
Если у вас числа 4,4,4,4,5,6,1,1 - то выгодно брать именно 6, потому что оно сделает второй бит единицей, что никак невозможно сделать, взяв 5.
У вас неправильное решение задачи.

Правильное решение такое: Найдите самый старший бит, в котором нечетное количество единиц в массиве a.

Если таких нет - то ответ Draw. Потому что, если в каком-то разряде единиц четное количество, и x из них достанется первому игроку, то второму достанется 2k-x, что будет иметь ту же четность, что и x. А значит в этом разряде итоговые значения отличаться не могут вообще. Как числа не распределяй, даже если игроки могут делать разное количество ходов.

Теперь мы знаем, что в этом разряде различие точно будет. Потому что нельзя нечетное количество единиц распределить на 2 группы с одинаковой четностью. Победа определяется только этим разрядом, ведь он самый старший из различий. Теперь у нас есть 2k+1 чисел c 1 в этом разряде и n-2k-1 чисел с 0 в этом разряде. На биты дальше смотреть не надо - кто возьмет нечетное количество чисел из 2*k+1 - тот победил.

Т.е. вам дальше надо решить совсем простую задачу: Дана пара чисел (i,j), i - нечетно, есть i нужных объектов и j ненужных, игроки по-очереди берут объекты. Кто возьмет нечетное количество нужных объектов - тот и победил.

Тут для вывода решения можно написать динамическое программирование, которое для пары (i,j) - будет говорить, сможет ли игрок взять четное/нечетное количество нужных чисел, если их i, и еще есть j ненужных. При расчете перебирайте варианты, какой из типов объектов берется и смотрите, а сможет ли оппонент вам четность испортить на меньшей задаче.

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

Мне лень решать дальше задачу, но похоже, что при i=1 ответ - WIN, при i>0 - ответ Win, если i+j=n - четно. Иначе - Lose.

У вас неправильно в коде - надо считать count() не на всем массиве, а только между low и high.

Тогда сложность всего алгоритма будет O(n log n). То, что у вас сейчас сделано будет иметь сложность O(n^2).

Избавиться от подсчета в данном решении никак нельзя.

Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

Нужно придумать какой-то паттерн, как компактно расположить все запросы в промежутке от 1 до n без повторений.

Детали зависят от конкретной реализации, но обычно все основано на leaky bucket.

В целом, роутер считает, сколько байт он пропустил, и если видит, что байт слишком много в еденицу времени, лишние пакеты просто дропаются (отбрасываются без пересылки их дальше). А дальше уже источник трафика как-то подстраивается. Если трафик TCP - то отправитель замечая потери будет снижать скорость отправления пока потери не прекратятся. Если же используется UDP, и приложение не надстроило над ним каких-то rate-control механизмов, то так и будет посылать лишние пакеты, которые будут уничтожатся роутером. До него трафик будет без ограничения скорости, а дальше пойдет уже ограниченный.

Обычное k-d дерево, как по ссылке у freeExec тут будет работать неплохо и будет потреблять сравнительно мало памяти. Но оно не дает гарантию времени выполнения. Может так получится, что вы обойдете почти все вершины в дереве (то же O(n), n - количество точек), даже если в прямоугольник не попала ни одна точка. Правда для этого нужно иметь весьма специфическую конфигурацию точек и очень прямоугольник с большим периметром. Я думаю, этот вариант вам лучше всего подходит, если точки более менее случайно разбросаны и экран занимает лишь маленькую, более менее квадратную область.

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

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

Дерево отрезков, оно же segment tree - это структура данных, которая делит все пространство координат на половинки, пока не получит в листах по одной координате.

Дерево поиска - это сбалансированное двоичное дерево поиска. Типа avl, красно-черных или декартовых деревьев. Возможно стандартный Set из JS или его аналог тут подойдет.

Суть решения такая - вы разбиватете все пространство по одной координате (скажем, y) деревом отрезков. Каждая вершина этого дерева отвечает за некоторую горизонтальную полосу c фиксированными y координатами и ханит в себе Set всех точек, которые в эту полосу попадают. В Set храните какие-то ссылки на точки (допустим, их id в массиве всех точек), упорядоченные по x координате, а потом по y координате, а потом по id.

Это фактически 2D дерево отрезков, но наивная реализация требовала бы MaxW*MaxH памяти, что слишком много. Замена внутренних деревьев отрезков на Set позволяет сильно сэкономить в памяти.

При добавлении/удалении точки надо в дереве отрезков найти все вершины, которые покрывают ее y координату (их будет Log MaxH) и в их сетах удалить/добавить вершину с заданными (x,y) координатами.

Важно, что set упорядочен по x координате, не той же по которой упорядочено дерево отрезков.

Для получения всех точек в прямоугольнике стандартным обходом дерева отрезков найдите log(MaxH) вершин покрывающих прямоугольник по y координате. Теперь для каждого из найденных Set() найдите upper_bound левой границы. Теперь обойдите точки в Set, начиная с этой, пока не выйдете за правую границу прямоугольника и рисуйте их.

Эта структрура данных найдет все точки в прямоугольнике за O(k + log(MaxW) * log N), где k - количество точек в прямоугольнике, MaxW - высота пространства, N - общее количество точек. При этом каждая точка будет хранится ровно log(MaxW) раз, т.е. по памяти эта структура данных не такая и прожорливая - O(n log(MaxW)).

Единственная проблема: похоже стандартный Set в JS не умеет делать upper_bound. Если точки не меняются часто, то можно вместо Set хранить массив точек отсортированный по x и бинарным поиском искать левую границу при обходе прямоугольника. Иначе же используйте вместо Set более продвинутую реализацию дерева поиска, которая поддерживает upper_bound. Возможно даже есть что-то стандартное в JS или есть готовые библиотеки - я не специалист.

Вам обязательно отвечать на вопрос об электричесвте в конкретном доме по мере добавления ребер/вершин в граф?
Если вам только тесты надо делать, то можно сначала создать весь мир, а потом поспрашивать его о статусах домов. При чем сами вычисления (обход графа) можно сделать только один раз, получить данные по всем домам и потом их проверить.

В этом случае надо, как вы и предположили, хранить массив "посещенности" домов. Можно совместить его с массивом-ответом или статусами домов. Ваш метод уже не принимает конкретный дом как параметр, а просто считатет для всех домов. Он изначально заполняет массив для всех домов и электростанций нулями, что значит, что электричества в доме нет. Потом выполняется DFS (обзод в глубину) или BFS (обход в ширину) от электростанций, которые активны. При этом все посещенные вершины помечаются 1 в массиве. В уже помеченные вершины вы не ходите, поэтому алгоритм незациклиться.

Если же вам обязательно надо узнавать статус домов после каждого изменения графа, то можно делать все тоже самое, но это будет медленно, ведь после каждого изменения вы будете обходить весь граф.

Можно сделать гораздо быстрее. Если связи между домами только добавляются (но ни в коем случае не удаляются), то можно использовать систему непересекающихся множеств (DSU). Изначально каждый дом и электростанция - сами себе множество. В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1). Это просто в реализации: у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества. Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов. Точно также в вики по ссылке выше поддерживатеся rank.

При добавлении провода вы должны слить 2 множества. При этом пересчитайте счетчик (прибавьте счетчик нижнего множества к счетчику верхнего множества).

При запросе на статус дома возьмите счетчик активных станций для его множества и проверьте, что он положителен. При выключении/включении электростанции измените счетчик соответствующего множества на +1 или на -1.

Это решение будет фактически работать за O(1) при каждом запросе и добавлении ребра (если использовать эвристику сжатия путей).
Наивное же решение с полным обходом графа каждый раз было бы O(1) при добавлении ребра и O(n) при запросе.