Epik Altmassivlərin Sayılması (Həll təhlili)

Həll

Qeyd edin ki, $1$-in ilk mövqedən başqa yerdə olduğu epik massiv ola bilməz, yəni epik massivlərin ümumi forması:

buna görə də prosesi asanlaşdırmaq üçün $1$-lərin mövqelərini $\text{pos}$ massivində saxlayırıq.

(1 \le i \le n-1) üçün a_{\text{pos}[i]} və a_{\text{pos}[i+1]} arasında $2$-lərin blokunun ölçüsü \text{pos}[i+1]-\text{pos}[i]-1-dir, çünki biz həmçinin başlayan $1$-i sayırıq, ifadə \text{pos}[i+1]-\text{pos}[i] olur.

İndi hər blok üçün, blokun özünün altmassivlərini saymaq istədiyimizi nəzərə alaraq, $1$-in başlanğıc indeksini $a$ və son indeksini $b$ olaraq götürsək, prosesi simulyasiya edərək (a\rightarrow a) , (a \rightarrow a+1) , .. (a \rightarrow b-1) alırıq, eyni şəkildə (a+1 \rightarrow a+1) ,... , (a+1 \rightarrow b-1) üçün.

Bu simulyasiya ilk $k$ tam ədədin cəmi ilə eyni olur, yəni Triangular ədədlər T(n)=\frac{n(n+1)}{2}.

Bundan sonra, a_{\text{pos}[0]}-dan əvvəl görünən iki seqmenti nəzərə almalısınız, çünki bu sayılmayacaq, həmçinin a_{n-\text{pos}[\text{last}}]}.

Beləliklə, $a$-da ən azı bir $2$ olduqda həllimiz tamamlanır.

a=[1,1,1,...,1] olduqda həll $T(n)$-dir.

Komplekslik $\mathcal{O}(n)$.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

int T(int x){return x*(x+1)/2;}

void solve(){
    int n;cin>>n;
    vector<int>a(n);
    for(auto &i:a)cin>>i;
    vector<int>pos;
    for(int i=0;i<n;i++){
        if(a[i]==1) pos.push_back(i);
    }
    int ans=0;
    if(pos.empty()){
        ans=T(n);
    }else{
        ans+=T(pos[0]);           
        for(int i=0;i+1<(int)pos.size();i++){
            ans+=T(pos[i+1]-pos[i]);   
        }
        ans+=T(n-pos.back());        
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}