DQUERY - D-query

跟兔子王國類似的手法，對Query x排序，準備sumbst，處理pop數字ptr和push數字ptr..

[兔子王國]

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

struct sumbst{
    vector<int> tree;
    int base;
    sumbst(int n){
        base = (1<<(int)(ceil(log2(n+3))))-1;
        tree = vector<int>(2*base+2, 0);
        return;
    }
    void modify(int p, int v){
        p += base + 2;
        tree[p] = v;
        for(p>>=1;p;p>>=1)
            tree[p] = tree[p<<1] + tree[(p<<1)^1];
        return;
    }
    int query(int a, int b){
        int ret = 0;
        for(a+=base+1,b+=base+3; a^b^1;a>>=1, b>>=1){
            if(~a&1) ret += tree[a^1];
            if(b&1) ret += tree[b^1];
        }
        return ret;
    }
};


struct qry{int id, x, y;};
bool operator<(const qry& a, const qry& b){return a.x < b.x;}

int arr[200000];
int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++)
        scanf("%d", arr+lx);
   
    map<int, vector<int> > posrec;
    map<int, int > posptr;
    for(int lx = 0;lx < n;lx++){
        posrec[arr[lx]].push_back(lx);
        posptr[arr[lx]] = 1;
    }

    int q; scanf("%d", &q);
    vector<qry> qrys(q);
    for(int lx = 0;lx < q;lx++){
        int a, b;
        scanf("%d %d", &a, &b);
        qrys[lx].x = a-1, qrys[lx].y = b-1, qrys[lx].id = lx;
    }
    sort(qrys.begin(), qrys.end());
   
    vector<int> ans(q);
    sumbst bst(n);
    for(auto& it : posrec)
        bst.modify(it.second[0], 1);

    int now = 0;
    for(qry& qq : qrys){
        while(now < qq.x){
            auto& vec = posrec[arr[now]];  
            auto& ptr = posptr[arr[now]];
            bst.modify(vec[ptr-1], 0);
            if(vec.size() > ptr)
                bst.modify(vec[ptr], 1);
            ptr++, now++;
        }
        ans[qq.id] = bst.query(qq.x, qq.y);
    }
   
    for(int lx = 0;lx < q;lx++)
        printf("%d\n", ans[lx]);

    return 0;
}