Симетрична конструкція (Розбір)

Рішення

Зверніть увагу, що їхня умова "симетричний" насправді стосується парних сум всередині підмасиву: для $a[l..r]$ нам потрібно, щоб a[l+i] + a[r-i] було однаковим для всіх допустимих $i$. Напишіть рівняння для двох послідовних $i$: a[l+i] + a[r-i] = S та a[l+i+1] + a[r-i-1] = S. Віднімемо їх, і ви отримаєте a[l+i+1] - a[l+i] = a[r-i] - a[r-i-1].

Тепер нехай d[i] = a[i+1] - a[i] для 1 \le i \le n-1, тоді ця залежність є точною d[l+i] = d[r-1-i].

Отже, вся симетрична умова на $a[l..r]$ зводиться до: сегмент d[l..r-1] повинен бути паліндромом. А запити тепер кажуть: для кожного $[L,R]$ на $a$ нас цікавить [l, r] = [L, R-1] на $d$. Якщо x = 1, сегмент $d[l..r]$ повинен бути паліндромним, якщо x = 0, він не повинен бути. Як тільки ми призначимо будь-який узгоджений d[1..n-1], ми можемо відновити $a$ (до постійного зсуву) за допомогою префіксних сум, тому достатньо побудувати $d$.

Тоді зверніть увагу, що "$d[l..r]$ є паліндромом" є те ж саме, що "$d[l..r]$ дорівнює своєму зворотному". Тож давайте з'єднаємо $d$ з його зворотною копією в одній індексній області: позиції 1..n-1 є оригінальним $d$, а позиції n..2n-2 концептуально представляють $d$, перевернуте. Для кожного $i$ ми знаємо, що вперед індекс $i$ та його зворотний відповідник (місце, де $d[i]$ з'являється в зворотній копії) завжди повинні бути рівними, тому ми одразу об'єднуємо ці дві позиції.

Тепер для запиту [L, R, x] на $a$, після перетворення в $d$ ми отримуємо [l, r] = [L, R-1] та \text{len} = r - l + 1. Зворотний сегмент, що відповідає $d[l..r]$, починається з деякого індексу $\text{rev}$ у цьому подвоєному масиві, тому "$d[l..r]$ є паліндромом" просто означає "сегмент довжини $\text{len}$, що починається з $l$, дорівнює сегменту довжини $\text{len}$, що починається з $\text{rev}$" всередині цього подвоєного масиву. Ми зменшили кожен запит x = 1 до купи обмежень рівності сегментів на одному 1D масиві розміру 2 \cdot (n-1).

Це можна звести до DSU на сегментах: ми хочемо накласти обмеження "сегмент [L..L+\text{len}-1] дорівнює сегменту [R..R+\text{len}-1]", при цьому зможемо пізніше перевірити, чи вже накладено рівність для іншої пари сегментів попередніми обмеженнями. Якщо ми наївно спробуємо об'єднати всі позиції за запитом, ми отримаємо $O(nq)$, що занадто велике. За допомогою класичного трюку "блоки степеня двійки" це можна оптимізувати до O((n+q)\log n).

Ми будуємо $\text{dsu}[k]$, де кожен вузол $u$ в $\text{dsu}[k]$ представляє блок [u..u+2^k-1]. Якщо ми вирішимо, що два блоки розміру 2^k, що починаються з $L$ та $R$, повинні бути рівними, ми об'єднуємо їх у $\text{dsu}[k]$ і рекурсивно накладаємо рівність їхніх лівих та правих половин у \text{dsu}[k-1], що врешті-решт об'єднує підлягаючі одиничні позиції в $\text{dsu}[0]$. Будь-яка рівність сегмента довільної довжини "довжина = $\text{len}$" може бути розкладена на максимум два блоки степеня двійки: візьміть \text{lg} = \lfloor \log_2(\text{len}) \rfloor, зрівняйте лівий великий блок розміру 2^{\text{lg}} та правий великий блок розміру 2^{\text{lg}}. Отже, кожен запит x = 1 перетворюється на два виклики "об'єднати ці два блоки", і через рекурсію ми поширюємо рівність до самих клітин.

Щоб перевірити запит x = 0, ми використовуємо дзеркальну процедуру "перевірки" через те ж саме розбиття на степені двійки: вона відповідає "чи вже гарантовано рівні ці два сегменти довжини $\text{len}$ під об'єднаннями, які ми зробили до цього часу?". Якщо вперед сегмент і його зворотний вже змушені бути рівними, тоді незалежно від того, як ми призначимо числа, $d[l..r]$ буде паліндромним, що означає, що $a[L..R]$ завжди є симетричним, тому запит x = 0 є неможливим. Якщо вони не змушені бути рівними, десь є принаймні одна пара позицій, які все ще належать різним компонентам DSU, що означає, що пізніше ми можемо дати їм різні значення і зламати паліндром.

В кінці ми призначаємо відмінне значення для кожної компоненти DSU: для кожної базової позиції $i$ в прямому масиві $d$ ми просто дозволяємо d[i] = \text{find}(i) (представник його набору), потім відновлюємо $a$ як префіксну суму, починаючи з $0$. Будь-які позиції, пов'язані DSU за допомогою обмежень x = 1, мають одного й того ж представника $\Rightarrow$ одне й те ж значення різниці $\Rightarrow$ паліндромні сегменти з'являються там, де це потрібно; і за конструкцією, для кожного запиту x = 0 ми забезпечили, що два сегменти не є повністю пов'язаними, тому принаймні одна пара вперед/назад має різних представників, що робить цей сегмент різниці непаліндромним і відповідний підмасив несиметричним.

Складність

Ми пропускаємо часову складність DSU (з компресією шляхів та об'єднанням за розміром), оскільки вона незначна.

Запити X = 1

По-перше, зверніть увагу, що ми будемо мати максимум n \log_2 n операцій об'єднання. Коли ми виконуємо операцію об'єднання в стані, ми більше не будемо розгалужуватися з цього стану. Отже, загальна часова складність для цих запитів становить O((n + q) \log_2 n).

Запити X = 0

Ми лише проходимо праву дитину запиту, якщо ліва дитина задоволена. Це означає, що коли ми досягаємо правого вузла, або була виконана операція об'єднання на лівій дитині, або ліва дитина вже задоволена, що займає $O(1)$ часу для перевірки.

Оскільки є максимум n \log_2 n операцій об'єднання, і кожен запит включає максимум O(\log_2 n) перевірок, які повертають хибні значення, загальна часова складність для всіх запитів X = 0 також становить O((n + q) \log_2 n).

#include<bits/stdc++.h>
using namespace std;
const int mxn = 2e6 + 5;
int n, q;
int l[mxn + 1], r[mxn + 1], x[mxn + 1];
struct DSU{
    int pa[mxn + 1];
    void init(){
        for(int i = 1; i <= 2 * (n - 1); i++)pa[i] = -1;
    }
    int fp(int u){
        if(pa[u] < 0)return(u);
        return(pa[u] = fp(pa[u]));
    }
    void unon(int u, int v){
        u = fp(u); v = fp(v);
        if(u == v)return;
        if(-pa[u] < -pa[v])swap(u, v);
        pa[u] += pa[v]; pa[v] = u;
    }
    bool check(int l, int r){
        return(fp(l) == fp(r));
    }
};
DSU dsu[20];
void go(int bit, int L, int R){
    if(dsu[bit].check(L, R))return;
    dsu[bit].unon(L, R);
    if(bit > 0){
        go(bit - 1, L, R); go(bit - 1, L + (1 << (bit - 1)), R + (1 << (bit - 1)));
    }
}
void add_edge(int L, int R, int len){
    int lg = __lg(len);
    go(lg, L, R); go(lg, L + len - (1 << lg), R + len - (1 << lg));
}
bool go2(int bit, int L, int R){
    if(dsu[bit].check(L, R))return(true);
    if(bit == 0)return(false);
    if(!go2(bit - 1, L, R))return(false);
    if(go2(bit - 1, L + (1 << (bit - 1)), R + (1 << (bit - 1))){
        dsu[bit].unon(L, R); return(true);
    }
    return(false);
}
bool check(int L, int R, int len){
    int lg = __lg(len);
    if(!go2(lg, L, R))return(false);
    return(go2(lg, L + len - (1 << lg), R + len - (1 << lg)));
}
long long d[mxn + 1];
void solve(){
    cin >> n >> q;
    for(int i = 0; i < q; i++){
        cin >> l[i] >> r[i] >> x[i]; --r[i];
    }
    for(int i = 0; i < 20; i++){
        dsu[i].init();
    }
    //1 2 3 4 .. n - 1 n - 1 n - 2.. 1
    for(int i = 1; i <= n - 1; i++){
        dsu[0].unon(i, n - 1 + (n - i));
    }
    for(int i = 0; i < q; i++){
        if(x[i] == 1){
            if(l[i] > r[i])continue;
            add_edge(l[i], n - 1 + (n - r[i]), r[i] - l[i] + 1);
        }
    }
    for(int i = 0; i < q; i++){
        if(x[i] == 0){
            if(l[i] > r[i]){
                cout << -1; return;
            }
            if(check(l[i], n - 1 + (n - r[i]), r[i] - l[i] + 1)){
                cout << -1; return;
            }
        }
    }
    
    for(int i = 1; i <= n - 1; i++){
        d[i] = dsu[0].fp(i);
    }
    cout << 0 << " ";
    for(int i = 1; i <= n - 1; i++){
        if(i > 1)d[i] += d[i - 1];
        cout << d[i] << " ";
    } 
    cout<<"\n";
    
}   
 
    
 
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("robot.in", "r", stdin);
    //freopen("robot.out", "w", stdout);
    int tt;
    cin>>tt;
    while(tt--){
        solve();
 
    }
    return(0);
}