BOJ 14504 : 수열과 쿼리 18

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

14504번: 수열과 쿼리 18

우리는 이를 평방 분할(Sqrt Decomposition)로 풀 수 있다.

 

퀴리를 n^(1/2)만큼으로 분할 한 다음, 버킷에 정렬된 결과를 저장해놓으면 

우리는 이를 lower_bound, upper_bound를 통해 k보다 크거나 같은 A_i의 인덱스를 찾을 수 있다. 

그러므로 각 버킷에서 해는 n^(1/2)-(버킷에서 A_i<=k가 최대인 인덱스)가 된다.

 

#include <bits/stdc++.h>
#define MEM 100005
#define sanic ios_base::sync_with_stdio(0)
#define f first
#define s second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+7;
ll n,m;
ll sq;
ll a[MEM];
vector<ll> b[MEM];
void init(){
    sq=sqrt(n);
    for(int i=0; i<n; i++)
        b[i/sq].push_back(a[i]);
    for(int i=0; i<n/sq+1; i++)
        sort(b[i].begin(), b[i].end());
}
void update(int p, int val){
    auto i=lower_bound(b[p/sq].begin(), b[p/sq].end(), a[p]);
    a[p] = val;
    *i = val;
    sort(b[p/sq].begin(), b[p/sq].end());
}
int query(int l, int r, int k){
    int ret=0;
    while(l%sq && l<=r){
        if(a[l++]>k)
            ret++;
    }
    while((r+1)%sq && l<=r){
        if(a[r--]>k)
            ret++;
    }
    while(l<=r){
        ret += b[l/sq].end()-upper_bound(b[l/sq].begin(), b[l/sq].end(), k);
        l += sq;
    }
    return ret;
}
int main()
{
    sanic; cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    init();
    cin >> m;
    int q,w,e,s;
    for(int i=0; i<m; i++){
        cin >> q >> w >> e;
        if(q==1){
            cin >> s;
            cout << query(w-1, e-1, s) << '\n';
        }
        else update(w-1, e);
    }
}

Sqrt Decomposition 처음 짜본다. 근데 1트만에 AC가 나왔다는 게 이상한 것 같다.