HOJ 327 - 兔子王國

http://hoj.twbbs.org/judge/problem/view/327

題目：給一串數列，和一堆查詢，每次查詢[a, b]之間有多少數字和這區間其他數互質，不強迫在線，多筆測資

N = 200000, Time Limit = 3000/per file

是某區域賽，原本想了個36*N^1.5的做法，可是T了，大概是因為常數再加上多筆測資，只好怒看題解。

主要概念是對每個數字紀錄和他互質最左界可以到哪裡，最右界可以到哪裡。
對於一個區間，我們希望的答案就是 數字左界<=區間左界 且 數字右界>=區間右界 的個數

然後對查詢做離線處理，根據查詢區間左界做排序。

準備一個和線段樹。對於每筆查詢，我們都要先像是維護單調性調整左界，
(1) 當一個數字的左界被左指標指到時， 這個數字可能可以在接下來的查詢出現
(2) 當一個數字的位置被左指標超越時，這個數字不可能在接下來的查詢出現


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

using namespace std;

struct sumbst{ // 0-base
    int base;
    vector<int> tree;
    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;
    }
};

int arr[200000];

vector<int> rad[200001];

int rn[200000];
vector<int> adat[200000];

void make(int n){
    for(int lx = 0;lx < n;lx++) adat[lx].clear();
    vector<int> ap(200000, 0);
    for(int lx = 0;lx < n;lx++){
        int pos = 0;
        for(int pp : rad[arr[lx]]){
            pos = max(pos, ap[pp]);
            ap[pp] = lx+1;
        }
        adat[pos].push_back(lx);
    }
    ap = vector<int>(200000, n-1);
    for(int lx = n-1;lx >= 0;lx--){
        int pos = n-1;
        for(int pp : rad[arr[lx]]){
            pos = min(pos, ap[pp]);
            ap[pp] = lx-1;
        }
        rn[lx] = pos;
    }
    return;
}

struct qry{
    int x,y,id;
    qry(int _x = 0, int _y = 0, int _id = 0):x(_x), y(_y), id(_id){return;}
};
bool operator<(const qry& a, const qry& b){return a.x < b.x;}

int main(){
    {
        vector<int> seive(200000, 1);
        for(int lx = 2;lx < 200000;lx++)
            if(seive[lx])
                for(int ly = 1;ly*lx <= 200000;ly++)
                    rad[ly*lx].push_back(lx), seive[lx*ly] = 0;
    }
    int n, q;
    while(scanf("%d %d", &n, &q) != EOF){
        for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
        make(n);
        vector<qry> qrys(q);
        for(int lx = 0;lx < q;lx++){
            int x, y; scanf("%d %d", &x, &y);
            x--, y--;
            qrys[lx] = qry(x, y, lx);
        }
        sort(qrys.begin(), qrys.end());
       
        vector<int> ans(q, 0);
        sumbst bst(n+1);
        int nl = -1;
        for(qry& qq : qrys){
            while(nl < qq.x){
                if(nl != -1){
                    bst.modify(nl, -1);
                    bst.modify(rn[nl]+1, 1);
                }
                nl++;
                for(int id: adat[nl]){
                    bst.modify(id, 1);
                    bst.modify(rn[id]+1, -1);
                }
            }
            ans[qq.id] = bst.query(qq.x, qq.y);
        }
        for(int lx = 0;lx < q;lx++)
            printf("%d\n", ans[lx]);
    }
    return 0;
}