Настройки поиска

Хм. помоему не 4n а 2n-1 вершин должно быть. все вершины кроме листьев - разделяют элементы - их столько же сколько можно поставить перегородок между n элементами = n-1. ну и плюс листья - n штук. если еще для удобства добавить нулевой элемент - будет 2n.
Более того опыт показывает (http://e-maxx.ru/algo/segment_tree - скопировал просто отсюда код и потестил) что половина массива t - нули. даже если n = (2^k)+1. получается не полное двоичное дерево.. в чем нет ничего плохого при такой реализации (если делим пополам массив нечетной длины то "большая половина" будет левой частью).

какую структуру данных на массиве лучше взять чтоб быстро выполнять операции типа взять две соседние подстроки ([ai..aj] и [a{j+1} ... ak]) и поменять местами? в просто массиве долго переставлять, а в списке - долго искать iй элемент.. если еще какоето дерево сверху посторить то в нем нада еще чето менять.. вощем чето я не понимаю.

на прошлом 1/4ть финале асма была такая задача - нужно было выполнять много циклических сдвигов подстрок. фактически циклический сдвиг на к - это и есть поменять две соседние подстроки. Мы тогда эту задачу решили на прямую просто классом string - и прокатило.. но жури потом заявило что у них прост почему-то не было большего теста...

Ним в поддавки - тотже ним, только кто берет последний камень - проигрывает.. граф игры практически совпадает с графом ним, вот только положение 1 - проигрышное.. а вот 0 какое? точно не проигрышное, иначе 1 - выигрышное.. значит 0 - выигрышное. получается что есть выигрышное состояние, из которого нет переходов.. и что делать? это противоречит части того (про выигрышные и проигрышные состояния) что написано тут http://e-maxx.ru/algo/sprague_grundy ... Хотя игра вроде равноправная.. Или я чето не так понимаю? в любом случае если мы пытаемся посчитать функцию Гранди она получается такойже как у обычного ним. но тогда скажем три кучки по одному камню - ним - выигрываем, а ним в поддавки - проигрываем - не сходится... Так равноправная ли это игра?

Как решать немного по другому вроде понятно, но интересно, как эта задача соотносится с теорией Шпрага-Гранди.

Я чет не понял зачем сложный if.. онж по сути добавляет итерацию цикла лишнюю после каждого срабатывания n&1

while (n)
        if (n & 1) {
            res *= a;
            --n;
        }
        else {
            a *= a;
            n >>= 1;
        }

не прощели так? прост проходимся по числам вида n^(2^k) , если нужно - домножаем

while(n) {
    if(n & 1)
        res *= a;
    a *= a;
    n = n >> 1;
}