Zadanie

Usáma a Maru sa rozhodli, že spravia tú najokázalejšiu svadbu, akú kedy Trojsten videl. Rozhodli sa preto, že každý hosť dostane ručne šitého motýlika alebo mašľu do vlasov. Výhodou je, že pri objednávaní to netreba rozlišovať, lebo je to vlastne to isté, len inak nazvané. V krajčírskej firme J&P1 si teda objednali zákazku na \(n\) motýlikov.

Jano je veľký motýlikový umelec a na tejto zákazke sa vybláznil, preto je každý motýlik iný a originálny. Ako však vieme, nie každý originálny nápad dopadne úspešne a teda nie všetky motýliky vyzerajú rovnako dobre. Každému motýliku preto Usáma a Maru priradili číslo zodpovedajúce jeho kráse.

Situácia sa však skomplikovala. Nie sú si totiž istí, koľko pozvaných hostí naozaj príde. Chceli sa preto s Janom dohodnúť, že keď zistia počet hostí \(k\), ktorí prídu na svadbu, zoberú si \(k\) najkrajších motýlikov. To im však Jano zakázal, zoradil motýliky podľa poradia ušitia a povedal, že si budú môcť vybrať iba súvislý úsek dĺžky \(k\).

V tom okamihu sa rozpútala hádka2. Usáma chcel, ako správny egoista, získať najkrajší motýlik pre seba a chcel preto úsek s čo najväčším maximom krásy. Maru je ale štedrá osoba a páči sa jej rozmanitosť, preto chcela maximalizovať bitový OR krás všetkých motýlikov, ktoré budú vo vybranom úseku.

Nakoniec sa dohodli sa dohodli na kompromise3 a rozhodli sa maximalizovať súčet maximálneho prvku a bitového ORu všetkých krás v úseku. Stále však nevedia, koľko hostí príde na svadbu, preto by chceli vedieť dopredu, ktorý úsek vybrať pre všetky možné \(k\).

Úloha

Na vstupe dostanete postupnosť kladných celých čísiel dĺžky \(n\). Vašou úlohou bude pre každé \(k\) od \(1\) po \(n\) nájsť taký súvislý úsek dĺžky \(k\) v tejto postupnosti, že súčet maxima v tomto úseku a bitového ORu prvkov tohoto úseku je najväčší možný.

Formát vstupu

Na prvom riadku sa nachádza číslo \(n\) (\(1 \leq n \leq 100\,000\)), ktoré označuje počet vyrobených motýlikov. Nasleduje \(n\) čísel, ktoré predstavujú krásy jednotlivých motýlikov v poradí, v akom boli vytvorené. Krásy motýlikov sú kladné celé čísla neprevyššujúce \(10^9\).

Formát výstupu

Vypíšte \(n\) čísel na samostatné riadky, kde \(k\)-te z nich predstavuje najväčší možný súčet požadovaných vlastností pre úseky dĺžky \(k\).

Príklad

Input:

3
1 0 2

Output:

4
4
5

  1. Jano a podšívky.

  2. V skutočnosti to tak nebolo. Maru rozhodla, ktorý úsek zoberú a Usáma nemal na výber. Takýto scenár by však nevytvoril zaujímavé zadanie.

  3. Čo je v manželstve veľmi dôležité.

Osobne sa musím priznať, že sa mi táto úloha veľmi páčila. Jej riešenie je totiž také skladačkové, treba spraviť zopár správnych aj nesprávnych pozorovaní, ale výsledok je o to krajší. A ako ste mali začať? No predsa tak, že ste naprogramovali jednoduché \(n^2\) riešenie, ktoré postupne skúšalo všetky možné úseky a zisťovalo ich maximum a bitový or. A aj keď to vyzerá ako riešenie so zložitosťou \(O(n^3)\), určite ho dokážete ľahko zredukovať, keď si uvedomíte, že z výsledku pre jeden úsek viete jednoducho vypočítať výsledok pre úsek o jedno dlhší.

Samozrejme, takéto jednoduché riešenie nie je až také zaujímavé. Potrebujeme vymyslieť niečo rádovo rýchlejšie. Dobrým postupom je hľadať, čoho môže byť v zadaní málo, a poprípade si fixovať nejaké prvky napevno. Začnime druhým prípadom, skúsime si dopredu určiť maximum úseku. Prečo práve maximum? Lebo to sa aj naozaj nachádza v poli. Pre ľubovoľný úsek bude jeho maximum len jeden z prvkov poľa, zatiaľčo bitový or môže byť takmer ľubovoľné číslo.

Vyberieme si teda nejaký prvok na \(m\)-tej pozícii a budeme sa pozerať na všetky úseky, ktoré ho obsahujú. Naviac budeme predpokladať, že tento prvok je maximum pre všetky tieto úseky. Samozrejme, niečo také platí iba pre najväčší prvok poľa. Ak si ako náš prvok zvolíme inú hodnotu, pravdepodobne niektoré úseky budú obsahovať väčšie číslo. To budeme ale potichu ignorovať a budeme sa tváriť, že nech je na \(m\)-tej pozícii hocijaké číslo, je maximom pre všetky úseky, ktoré ho obsahujú. Naším cieľom bude pre tieto úseky rátať or čísel v nich a pomocou toho zisťovať výslednú hodnotu.

A hoci naše vybrané číslo nemusí byť skutočné maximum každého podúseku, hodnota, ktorú vďaka tomu vypočítame, nebude väčšia ako naozajstné maximum súčtu maxima a bitového or-u v tomto úseku. A tú správnu hodnotu zarátame, keď si ako \(m\)-tý prvok zvolíme to správne číslo1.

Maximum máme určené, pozerajme sa teraz na bitový or. Ten má tú peknú vlastnosť, že toto číslo neklesá, keď sa k úseku pridávajú ďalšie prvky, pretože sa môže len zväčšiť priorovaním nového bitu, ktorý sa v ňom dovtedy nevyskytoval.

Zoberme si napríklad všetky úseky, kde je \(m\)-tý prvok najľavším v tomto úseku a pozrime sa na bitové ory ich čísel. Hodnota tohoto oru sa zmení vždy len vtedy, keď sa pridá prvok, ktorý obsahuje nejaký “nový” bit, taký, ktorý doposiaľ nebol v našom ore. Ale toto sa môže stať najviac \(31\) krát, lebo práve toľko bitov má najväčšie možné číslo \(10^9\).

Je len \(31\) zaujímavých úsekov, čo sú také úseky, kde sa zmení hodnota oru. To platilo pre úseky zľava zarovnané na \(m\)-tý prvok. Ale to isté sa dá povedať aj opačným smerom a dokopy nám to dá najviac \(31^2\) zaujímavých úsekov, čo dostaneme ako všetky možnosti začiatkov a koncov zarovnaných zaujímavých úsekov. A to je pomerne málo.

Otázka ale je, že čo s úsekmi, ktoré nie sú zaujímavé. A čo s ostatnými dĺžkami postupností? Všimnime si, že naše zaujímavé úseky sú naviac najkratšie možné, lebo zaujímavé sú práve tým, že sa niečo zmenilo. A druhá dôležitá vlastnosť je, že ak máme úsek dĺžky \(d\) so súčtom maxima a oru rovným \(l\), tak všetky úseky dĺžky viac ako \(d\) majú súčet maxima a oru rovný aspoň \(l\). Prečo? Lebo zoberieme ten úsek dĺžky \(d\), pridáme nejaké prvky a je jasné, že ani maximum ani or prvkov sa nám zmenšiť nemohol.

Zhrnieme si teraz riešenie. Pre každý prvok \(m\) poľa vyrátame dve pomocné polia (v programe označené ako \(Ml\) a \(Mr\)). Tie hovoria o každom možnom bite, kde naľavo (poprípade napravo) sa nachádza najbližšie číslo obsahujúce tento bit. Pričom prvok je sám sebe naľavo (aj napravo). Toto vieme spraviť jedným prechodom. Tieto dve polia si utriedime podľa vzdialenosti. Každá dvojica, kde jeden prvok je zľava a druhý sprava, nám určuje jeden zaujímavý úsek obsahujúci daný prvok \(m\). O prvku \(m\) predpokladáme, že je maximom svojich zaujímavých úsekov, a or čísel zaujímavého úseku vyrátame ľahko, lebo presne vieme, ktoré bity boli pridané dovtedy (predchádzajúce prvky v \(Ml\) a \(Mr\)). Do poľa výsledkov si preto zaznačíme, že úsek tejto dĺžky má aspoň takýto súčet maxima a oru, pričom si pamätáme zatiaľ videné maximum.

Niektoré prvky poľa výsledkov sú nevyplnené, lebo neexistuje zaujímavý úsek danej dĺžky. V takom prípade bude odpoveď maximum súčtu pre nejaký menší zaujímavý úsek. Môže sa dokonca stať, že máme dlhý zaujímavý úsek, ktorý má menší súčet ako nejaký iný menší zaujímavý úsek. Aby sme toto všetko napravili, toto pole výsledkov upravíme tak, že na \(i\)-tom políčku je maximum z úsekov dlhých najviac \(i\). Toto pole určuje výsledok.

Čo sa týka zložitosti, označme si \(M\) maximálny prvok postupnosti zo vstupu. Pamäťová zložitosť je potom \(O(n\log M)\), lebo pre každý prvok si pamätáme informáciu o \(\log M\) bitoch. A časová zložiťosť je \(O(n \log^2 M)\), lebo musíme vyskúšať všetky zaujímavé úseky.

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define For(i, n) for (int i = 0; i < (int) n; ++i)
#define SIZE(x) ((int) (x).size())
#define mp(a, b) make_pair(a, b)
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    int n;
    scanf("%d",&n);
    vector<int> A; A.resize(n);
    For(i,n) scanf(" %d",&A[i]);
    int moc=1;
    For(i,n) while((1<<moc)<=A[i]) moc++;
    vector<int> P; P.resize(moc,-1);
    vector<vector<pii> > Ml; Ml.resize(n);
    vector<vector<pii> > Mr; Mr.resize(n);
    For(i,n) {
        For(j,moc) if((A[i]&(1<<j))!=0) P[j]=i;
        //popridavaj do Ml
        For(j,moc) {
            if(P[j]==-1) continue;
            Ml[i].push_back(mp(i-P[j],j));
        }
    }
    P.clear(); P.resize(moc,-1);
    for(int i=n-1; i>=0; i--) {
        For(j,moc) if((A[i]&(1<<j))!=0) P[j]=i;
        //popridavaj do Mr
        For(j,moc) {
            if(P[j]==-1) continue;
            Mr[i].push_back(mp(P[j]-i,j));
        }
    }
    For(i,n) {
        sort(Ml[i].begin(),Ml[i].end());
        sort(Mr[i].begin(),Mr[i].end());
    }
    vector<int> Vys;
    Vys.resize(n,-1);
    //prejdi vsetko
    For(i,n) {
        if(A[i]==0) continue;
        int p1=0;
        For(i1,Ml[i].size()+1) {
            if(i1!=0) p1|=(1<<Ml[i][i1-1].second);
            int p2=0;
            For(i2,Mr[i].size()+1) {
                if(i2!=0) p2|=(1<<Mr[i][i2-1].second);
                int vzd=0;
                if(i1!=0) vzd+=Ml[i][i1-1].first;
                if(i2!=0) vzd+=Mr[i][i2-1].first;
                Vys[vzd]=max(Vys[vzd],A[i]+(p1|p2));
            }
        }
    }
    if(Vys[0]==-1) Vys[0]=0;
    for(int i=1; i<n; i++) Vys[i]=max(Vys[i],Vys[i-1]);
    For(i,n) printf("%d\n",Vys[i]);
}

  1. Možno sa pokúste trochu rozdýchať to, čo som sa tu snažil naznačiť a uvedomte si, že naozaj je to v pohode.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.