[BOJ] 13536 수열과 쿼리 4

Mo's algorithm 을 사용하는 문제다.

와아아아아아아앙 짝짝짝짝

각 숫자마다 list로 관리하면서 (dq[i].front-dq[i].back) 의 값이 숫자 i 의 최대 길이이다.

이제 이 숫자 i의 최대길이를 O(k) 가 아닌 O(sqrt(K)) 에 구해아 한다.

이 방법은 최대길이를 관리하는 버킷을 만들어서 sqrt(K) 개로 쪼갠다음 각 구간을 관리한다.

이러면 제일긴 길이 를 찾는방법을 O(sqrt(K)) 만에 구할 수 있다.

자세한건 코드를 보자.

 

#include <bits/stdc++.h>
using namespace std;
list <int> dq[300005];
int n,k,Q,val,sz;
int ans[300005],a[300005];
int b[300005],cnt[5000005];

struct Query {
    int l,r,idx;
}q[300005];

bool cmp(Query q1,Query q2) {
    if(q1.l/sz == q2.l/sz) return q1.r < q2.r;
    return q1.l/sz < q2.l/sz;
}

void AddL(int x) {
    if(!dq[a[x]].empty()) {
        val = dq[a[x]].front()-dq[a[x]].back();
        cnt[val]--;
        b[val/sz]--;
    }
    dq[a[x]].push_back(x);
    val = dq[a[x]].front()-dq[a[x]].back();
    cnt[val]++;
    b[val/sz]++;
}

void AddR(int x) {
    if(!dq[a[x]].empty()) {
        val = dq[a[x]].front()-dq[a[x]].back();
        cnt[val]--;
        b[val/sz]--;
    }
    dq[a[x]].push_front(x);
    val = dq[a[x]].front()-dq[a[x]].back();
    cnt[val]++;
    b[val/sz]++;
}

void DelL(int x) {
    val = dq[a[x]].front()-dq[a[x]].back();
    cnt[val]--;
    b[val/sz]--;
    dq[a[x]].pop_back();
    if(!dq[a[x]].empty()) {
        val = dq[a[x]].front()-dq[a[x]].back();
        cnt[val]++;
        b[val/sz]++;
    }
}

void DelR(int x) {
    val = dq[a[x]].front()-dq[a[x]].back();
    cnt[val]--;
    b[val/sz]--;
    dq[a[x]].pop_front();
    if(!dq[a[x]].empty()) {
        val = dq[a[x]].front()-dq[a[x]].back();
        cnt[val]++;
        b[val/sz]++;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    sz = sqrt(n)+5;
    for(int i = 1;i <= n;i++) cin >> a[i];
    cin >> Q;
    for(int i = 1;i <= Q;i++) {
        cin >> q[i].l >> q[i].r;
        q[i].idx = i;
    }
    sort(q+1,q+Q+1,cmp);
    int l = q[1].l, r = q[1].l-1;
    for(int i = 1;i <= Q;i++) {
        int nl = q[i].l, nr = q[i].r;
        while(l > nl) AddL(--l);
        while(r < nr) AddR(++r);
        while(l < nl) DelL(l++);
        while(r > nr) DelR(r--);
        for(int ii = sz-1;ii >= 0;ii--) {
            if(!b[ii]) continue;
            for(int j = sz-1;j >= 0;j--) {
                if(cnt[ii*sz+j]) {
                    ans[q[i].idx] = ii*sz+j;
                    break;
                }
            }
            break;
        }
    }
    for(int i = 1;i <= Q;i++) cout << ans[i] << '\n';
}