BOJ 13547 : 수열과 쿼리 5

https://www.acmicpc.net/problem/13547

13547번: 수열과 쿼리 5

이 문제는 Update 쿼리가 주어져 있지 않으므로 모스 알고리즘(Mo's Algorithm)으로 풀 수 있다.

처리 방법 : 수가 나오는 빈도를 저장할 배열을 정하여 각 쿼리에 대응

 

#include <bits/stdc++.h>
#define MEM 100007
#define sanic ios_base::sync_with_stdio(0)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+7;
struct q{
    ll l,r,k;
};
ll sq;
bool c(q a, q b){
    if(a.l/sq==b.l/sq) return a.r>b.r;
    return a.l/sq>b.l/sq;
}
ll n,m,a[MEM],b[MEM*11];
ll ans[MEM];
ll res;
vector<q> y;
void add(int g){
    if(++b[g]==1) res++;
}
void sub(int g){
    if(--b[g]==0) res--;
}
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    sq=sqrt(n);
    cin >> m;
    for(int i=0; i<m; i++){
        int q1,q2;
        cin >> q1 >> q2;
        y.push_back({q1-1, q2-1, i});
    }
    sort(y.begin(), y.end(), c);
    int s=0,e=0;
    add(a[0]);
    for(int i=0; i<m; i++){
        int ns=y[i].l,ne=y[i].r;
        for(int i=s; i<ns; i++) sub(a[i]);
        for(int i=s-1; i>=ns; i--) add(a[i]);
        for(int i=e+1; i<=ne; i++) add(a[i]);
        for(int i=e; i>ne; i--) sub(a[i]);
        s=ns;
        e=ne;
        ans[y[i].k] = res;
    }
    for(int i=0; i<m; i++)
        cout << ans[i] << '\n';
}

모스 알고리즘도 처음 짜본다. ㄹㅇ 쉽네