Mo's Algorithm

// 1-based, 닫힌 구간 [l, r] 쿼리
int sqrtN;
 
struct Query{
    int l, r, idx;
    bool operator<(const Query& o) const {
        int b = l / sqrtN, ob = o.l / sqrtN;
        if(b != ob) return b < ob;
        return (b & 1) ? (r < o.r) : (r > o.r);
    }
};
 
int cur;
void Push(int i){
    
}
void Pop(int i){
    
}
 
vector<int> mo(int n, vector<Query>& Q){
    sqrtN = max(1, (int)sqrt(n));
    sort(Q.begin(), Q.end());
    vector<int> ans(Q.size());
    int L = 1, R = 0;
    for(const auto& [l, r, idx] : Q){
        while(L > l) Push(--L);
        while(R < r) Push(++R);
        while(L < l) Pop(L++);
        while(R > r) Pop(R--);
        ans[idx] = cur;
    }
    return ans;
}