Simmetrik Tikinti (Həll təhlili)

Həll

Onların "simmetrik" şərtinin əslində bir alt array içində cüt cəmlərlə bağlı olduğunu qeyd edin: $a[l..r]$ üçün a[l+i] + a[r-i] bütün uyğun $i$ üçün eyni olmalıdır. İki ardıcıl $i$ üçün tənlikləri yazın: a[l+i] + a[r-i] = S və a[l+i+1] + a[r-i-1] = S. Onları çıxardın və siz əldə edirsiniz a[l+i+1] - a[l+i] = a[r-i] - a[r-i-1].

İndi d[i] = a[i+1] - a[i] üçün 1 \le i \le n-1 qoyun, sonra bu əlaqə tam olaraq d[l+i] = d[r-1-i] olur.

Beləliklə, $a[l..r]$-dəki bütün simmetrik şərt d[l..r-1]-in palindrom olması tələb olunur. Və sorğular indi deyir: $a$-da hər $[L,R]$ üçün, $d$-də [l, r] = [L, R-1] ilə maraqlanırıq. Əgər x = 1 isə, $d[l..r]$ palindromik olmalıdır, əgər x = 0 isə, palindromik olmamalıdır. Hər hansı bir uyğun d[1..n-1] təyin etdikdən sonra, $a$-nı (bir sabit dəyişmə ilə) prefiks cəmləri ilə bərpa edə bilərik, buna görə də $d$-ni yaratmaq kifayətdir.

Sonra "$d[l..r]$ palindromikdir" demək "$d[l..r]$ öz əksinə bərabərdir" deməkdir. Beləliklə, $d$-ni əksinə bir nüsxə ilə birləşdirərək bir indeks sahəsinə yapışdıraq: 1..n-1 orijinal $d$-dir, n..2n-2 isə konseptual olaraq $d$-nin əksidir. Hər $i$ üçün bilirik ki, irəliləyən indeks $i$ və onun əks tərəfi (daha doğrusu, $d[i]$-nin əks nüsxədə göründüyü yer) həmişə bərabər olmalıdır, buna görə də bu iki mövqeyi dərhal birləşdiririk.

İndi $a$-da [L, R, x] sorğusu üçün, $d$-yə çevirdikdən sonra [l, r] = [L, R-1] və \text{len} = r - l + 1 alırıq. $d[l..r]$-yə uyğun əks seqment, bu ikiqat arrayda bəzi indeks $\text{rev}$-də başlayır, buna görə "$d[l..r]$ palindromikdir" demək "uzunluğu $\text{len}$ olan seqment $l$-də başlayır, $\text{len}$ uzunluğunda seqment isə $\text{rev}$-də başlayır" deməkdir. Hər x = 1 sorğusunu bir 1D arrayda 2 \cdot (n-1) ölçüsündə seqment bərabərlik məhdudiyyətlərinə endirdik.

Bu, seqmentlər üzərində DSU ilə birləşdirilə bilər: "seqment [L..L+\text{len}-1] seqment [R..R+\text{len}-1]-ə bərabər olmalıdır" şərtini yerinə yetirmək istəyirik, eyni zamanda daha sonra başqa seqmentlərin artıq əvvəlki məhdudiyyətlər tərəfindən bərabər olub olmadığını yoxlaya bilmək. Əgər sorğu başına bütün mövqeləri birləşdirməyə çalışsaq, $O(nq)$ alarıq, bu da çox böyükdür. Klassik "iki güc blokları" triki ilə O((n+q)\log n)-ə optimallaşdırıla bilər.

Biz $\text{dsu}[k]$-ni qururuq, burada $\text{dsu}[k]$-dəki hər bir node $u$ bir blok [u..u+2^k-1]-u təmsil edir. Əgər 2^k ölçüsündə iki blokun $L$ və $R$-də bərabər olmasını qərara alsaq, onları $\text{dsu}[k]$-də birləşdiririk və sol yarısını və sağ yarısını \text{dsu}[k-1]-də bərabər etməyə məcbur edirik, bu da nəticədə $\text{dsu}[0]$-dəki tək mövqeləri birləşdirir. Hər hansı bir qeyri-müəyyən uzunluqdakı seqment bərabərliyi "uzunluq = $\text{len}$" ən çox iki güc-blokuna parçalanır: \text{lg} = \lfloor \log_2(\text{len}) \rfloor götürün, sol böyük blokun ölçüsünü 2^{\text{lg}} və sağ böyük blokun ölçüsünü 2^{\text{lg}} bərabərləşdirin. Beləliklə, hər x = 1 sorğusu "bu iki blokları birləşdir" çağırışlarına çevrilir və rekursiya ilə bərabərliyi hüceyrələrə qədər yayırıq.

x = 0 sorğusunu yoxlamaq üçün, eyni güc-blok parçalanması üzərində əks "yoxlama" prosedurundan istifadə edirik: bu, "bu iki seqmentin uzunluğu $\text{len}$ artıq indiyə qədər etdiyimiz birləşmələr altında bərabərdir?" sualını cavablandırır. Əgər irəliləyən seqment və onun əksi artıq bərabərsə, onda biz ədədləri necə təyin etsək də, $d[l..r]$ palindromik olacaq, yəni $a[L..R]$ həmişə simmetrikdir, buna görə də x = 0 sorğusu mümkün deyil. Əgər bərabər deyilsə, bir yerdə hələ də fərqli DSU komponentlərinə aid olan ən azı bir mövqe var, bu da deməkdir ki, sonra onlara fərqli dəyərlər verə bilərik və palindromu pozuruq.

Nəticədə, hər DSU komponenti üçün fərqli bir dəyər təyin edirik: irəliləyən $d$ arrayında hər əsas mövqe $i$ üçün biz sadəcə d[i] = \text{find}(i) (onun dəstəsinin nümayəndəsi) qoyuruq, sonra $0$-dan başlayaraq prefiks cəmi kimi $a$-nı bərpa edirik. x = 1 məhdudiyyətləri ilə DSU ilə bağlı olan hər mövqe eyni nümayəndəni paylaşır $\Rightarrow$ eyni fərq dəyəri $\Rightarrow$ lazım olan yerlərdə palindromik seqmentlər görünür; və konstruksiya ilə, hər x = 0 sorğusu üçün iki seqmentin tam bağlı olmadığını təmin etdik, buna görə də ən azı bir irəliləyən/əks cüt fərqli nümayəndələrə malikdir, bu da o fərq seqmentini palindromik etməyəcək və müvafiq alt array simmetrik olmayacaq.

Komplekslik

DSU-nun vaxt kompleksliyini (yol sıxılması və ölçüyə görə birləşmə ilə) nəzərə almırıq, çünki bu, əhəmiyyətsizdir.

X = 1 Sorğuları

İlk öncə, ən çox n \log_2 n birləşmə əməliyyatımız olacağını qeyd edin. Hər dəfə bir vəziyyətdə birləşmə əməliyyatı həyata keçirdikdə, o vəziyyətdən bir daha ayrılmayacağıq. Buna görə də, bu sorğular üçün ümumi vaxt kompleksliyi O((n + q) \log_2 n)-dir.

X = 0 Sorğuları

Biz yalnız bir sorğunun sol uşağı təmin edildikdə sağ uşağı keçirik. Bu, sağ düyünə çatdığımızda ya sol uşağa birləşmə əməliyyatı aparıldığını, ya da sol uşağın artıq təmin edildiyini bildirir, bu da yoxlamaq üçün $O(1)$ vaxt alır.

Çünki ən çox n \log_2 n birləşmə əməliyyatı var və hər bir sorğu ən çox O(\log_2 n) yoxlamaları ehtiva edir ki, bu da yanlış nəticə verir, bütün X = 0 sorğuları üçün ümumi vaxt kompleksliyi də O((n + q) \log_2 n)-dir.

#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);
}