티스토리 뷰
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';
}