Hướng dẫn cho Đoạn Đẹp

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: quanhoangbla

Đặt \(b[i] = \begin{cases} 1, & \text{nếu } a[i] = 1\\ -1, & \text{nếu } a[i] = 0 \end{cases}\)
Gọi \(s_i\) là mảng tiền tố của \(b_i\). Khi đó, dãy \([j+1:i]\) đẹp khi và chỉ khi \(s_i-s_j=0\).
Nhận xét: Khi lật phần tử \(a_i\) thì các đoạn chứa \(a_i\) sẽ có tổng \(b_i\) thay đổi một lượng là \(2\) nếu \(a_i=0\), \(-2\) nếu \(a_i=1\).
\(=>\) Có thể biến đổi \([j+1:i]\) thành một dãy đẹp nếu \(|s_i-s_j|\le 2k\) và \(s_i-s_j\) chẵn. Hay nói cách khác : \(s_i-2k\le s_j\le s_i+2k\) và \(s_i\) cùng tính chẵn lẻ với \(s_j\).

Thuật toán: Duyệt qua từng chỉ số \(i\) sau đó tìm \(j (0\le j\le i-1)\) nhỏ nhất thoả mãn 2 điều kiện để \([j+1:i]\) trở thành một dãy đẹp. Để xử lí điều kiện 1, ta có thể sử dụng Segment Tree và rời rạc hoá vì số có thể âm, và ta có thể tạo 2 cái Segment Tree để xử lý riêng biệt giữa \(s_i\) chẵn lẻ để xử lí điều kiện 2.

Code mẫu

C++

#include<bits/stdc++.h>
using namespace std;
using ll=int;

const ll MAX = 2e5+1;
const ll INF = 1e9;

ll n,k,s[MAX];
struct SegmentTree{ // Segment Tree Point Update, Range Query
    ll st[MAX*4*3];
    void build(ll i, ll l, ll r){
        if (l==r)st[i]=INF;
        else{
            ll mid=(l+r)>>1;
            build(i*2,l,mid);
            build(i*2+1,mid+1,r);
            st[i]=min(st[i*2],st[i*2+1]);
        }
    }
    void update(ll idx, ll x, ll i, ll l, ll r){
        if (idx>r || idx<l)return;
        if (l==r)st[i]=min(st[i],x);
        else{
            ll mid=(l+r)>>1;
            update(idx,x,i*2,l,mid);
            update(idx,x,i*2+1,mid+1,r);
            st[i]=min(st[i*2],st[i*2+1]);
        }
    }
    ll query(ll u, ll v, ll i, ll l, ll r){
        if (l>v || r<u)return INF;
        if (u<=l && r<=v)return st[i];
        ll mid=(l+r)>>1;
        return min(query(u,v,i*2,l,mid),query(u,v,i*2+1,mid+1,r));
    }
};
vector<ll> c;
ll get(ll i){
    return upper_bound(c.begin(),c.end(),i)-c.begin();
}

SegmentTree even,odd;
void init(){
    even.build(1,1,MAX*3);
    odd.build(1,1,MAX*3);
}

void solve(){
    cin>>n>>k;
    c.push_back(0);
    for (ll i=1; i<=n; ++i){
        bool t;
        cin>>t;
        s[i]=s[i-1]+(t?1:-1);

        c.push_back(s[i]);
        c.push_back(s[i]+2*k);
        c.push_back(s[i]-2*k);
    }
    sort(c.begin(),c.end());
    c.erase(unique(c.begin(),c.end()),c.end());

    even.update(get(0),0,1,1,MAX*3);
    ll res=0;
    for (ll i=1; i<=n; ++i){
        ll u=get(s[i] - 2*k), v=get(s[i] + 2*k); // u<=s[j]<=v
        if (s[i]&1){
            res=max(res, i - odd.query(u, v, 1, 1, MAX*3));

            odd.update(get(s[i]), i, 1, 1, MAX*3);
        }else{
            res=max(res, i - even.query(u, v, 1, 1, MAX*3));

            even.update(get(s[i]), i, 1, 1, MAX*3);
        }
    }
    cout<<res<<'\n';
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    init();
    solve();

    return 0;
}

Độ phức tạp thời gian : \(O(N\log N)\)
Độ phức tạp bộ nhớ : \(O(N)\)

Bình luận

Tải bình luận...

Không có bình luận nào.