BOJ 13554 - 수열과 쿼리 9

문제 링크 : https://www.acmicpc.net/problem/13554

문제 태그 (관련 지식)

Mo's algorithm, Segment tree

문제 소개

길이가 N인 두 수열 A1, A2, ..., AN과 B1, B2, ..., BN가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• i j k: i ≤ p, q ≤ j이면서 Ap × Bq ≤ k 인 (p, q) 쌍의 개수를 출력한다.

문제 풀이

일단 오프라인 쿼리고 시간제한이 6초이다. 사실 어떻게 접근을 해야할지 모르겠다. 이 문제를 볼 때 쯤이면 다른 수열과 쿼리 문제를 꽤나 풀어봤을 것이고, 그러면 수쿼를 풀 수 있는 도구중 Mo's Algorithm이 생각이 날 수 밖에 없다. 

하지만 문제가 있다. Mo's algorithm의 이점은 전의 쿼리에 대한 정답을 얻고, 그를 이용하며 변화량 값만 계산해서 다음 쿼리의 정답을 바로 얻을 수 있다는데에 있다. 하지만 이 문제는 각 쿼리마다 k라는 제한이 바뀌기 때문에 전 쿼리에 대한 정답이 다음 쿼리에 대한 정답으로 이어질 수가 없다는 것이다.

따라서 우리는 Mo's Algorithm을 정답 전체에 대해서 적용하는 것이 아니라 좀 더 작은 범위에 대해서 적용을 시키는 방법에 대해서 생각해 봐야한다. 즉, Mo's algorithm으로 구간에 대한 전처리를 하고 그 값을 이용하여 쿼리마다 답을 구한다는 것이다.

곱해서 k이하인 두 수의 특징에 대해서 관찰을 해야한다. 딱 한가지 중요한 관찰이고, 생각보다 단순하지만 놓치기가 쉽다. 곱해서 k이하인 두 수중 적어도 하나는 $ \sqrt{k}$이하라는 것이다. 

따라서 우리는 Mo's algorithm을 통해서 구간내에 각 숫자가 몇개씩 있는지를 미리 구해놓을 수 있다. 또한 이를 이용하여 쿼리에 대한 답을 낼 것이다. 배열 a의 1~ $ \sqrt{k}$의 각각 i에 대해서 그 갯수와 배열 b에서 1~k/i 의 갯수의 곱을 구하면 될 것이다. 구간내의 갯수를 구해야 하기 때문에 일일이 더하게 되면 시간초과가 날 것이고 이때 세그먼트 트리를 활용하면 된다.

전체 풀이를 정리해보자. Mo's algorithm을 이용해 각 쿼리를 왔다갔다 하면서 Segment Tree에 각 배열별로 각 숫자의 갯수를 저장해 놓는다. 또한 각 쿼리별로 현재 Segment Tree에서 구간 합을 이용하여 구간내의 숫자 갯수를 구할 수 있고 이를 이용하여 쿼리에 대한 답을 낼 수 있다. 

시간복잡도는 $ O(N \sqrt{N}lgn)$이 되기 때문에 세그먼트 트리를 쓰면 시간초과가 날 가능성이 꽤 있고, 이 문제에서 원하는 연산을 수행해 줄 수 있으면서 훨씬 빠른 펜윅트리를 쓰는 것이 좋다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
 
struct q{
    ll x,idx,s,e;
};
q qer[1010101];
ll ans[1010101];
ll acnt[1010101];
ll arr[1010101];
ll bcnt[1010101];
ll brr[1010101];
 
ll sqn,nn=100000;
ll now;
ll lf,rf;
 
struct SEG{
    ll tree[1010101];
    void upt(ll idx, ll val){
        while(idx<=nn){
            tree[idx]+=val;
            idx+=idx&-idx;
        }
    }
 
    ll sum(ll x){
        ll val=tree[x];
        while(x-=x&-x) val+=tree[x];
        return val;
    }
 
    ll ans(ll l, ll r){
        return sum(r)-sum(l-1);
    }
};
SEG sa,sb;
 
bool sf(q a,q b)
{
    if(a.s/sqn!=b.s/sqn) return a.s<b.s;
    return a.e<b.e;
}
 
void mi(ll s, ll e)
{
    ll i;
    for(i=s;i<=e;i++)
    {
        sa.upt(arr[i],-1);
        sb.upt(brr[i],-1);
    }
}
 
void pl(ll s, ll e)
{
    ll i;
    for(i=s;i<=e;i++)
    {
        sa.upt(arr[i],1);
        sb.upt(brr[i],1);
    }
}
 
ll sol(ll k){
    ll sqk=sqrt(k),ret=0;
    for(ll i=1;i<=sqk;i++){
        ret+=sb.ans(sqk+1,k/i)*sa.ans(i,i);
    }
    for(ll i=1;i<=sqk;i++){
        ret+=sa.ans(1,k/i)*sb.ans(i,i);
    }
    return ret;
}
 
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,l,m,n,Q;
    cin>>n;
    sqn=sqrt(n);
    for(i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(i=1;i<=n;i++){
        cin>>brr[i];
    }
    cin>>Q;
    for(i=1;i<=Q;i++)
    {
        cin>>qer[i].s>>qer[i].e>>qer[i].x;
        qer[i].idx=i;
    }
 
    sort(qer+1,qer+1+Q,sf);
 
    for(i=qer[1].s;i<=qer[1].e;i++)
    {
        sa.upt(arr[i],1);
        sb.upt(brr[i],1);
    }
    ans[qer[1].idx]=sol(qer[1].x);
    ll lf=qer[1].s;
    ll rf=qer[1].e;
 
    for(i=2;i<=Q;i++)
    {    
        if(qer[i].s<lf) pl(qer[i].s,lf-1);
        if(qer[i].e>rf) pl(rf+1,qer[i].e);
        if(qer[i].s>lf) mi(lf,qer[i].s-1);
        if(qer[i].e<rf) mi(qer[i].e+1,rf);
 
        lf=qer[i].s;
        rf=qer[i].e;
        ans[qer[i].idx]=sol(qer[i].x);    }
 
    for(i=1;i<=Q;i++)
        cout<<ans[i]<<'\n';
}