首页 > 代码库 > 莫队算法

莫队算法

http://www.cnblogs.com/hzf-sbit/p/4056874.html

https://www.zhihu.com/question/27316467/answer/36260465

处理一类无修改的离线区间询问问题

复杂度为O(n*sqrt(n)*a),a为单次更新操作的复杂度。

作者:张瑯小强
链接:https://www.zhihu.com/question/27316467/answer/130423804
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*********************************
问题:有n个数组成一个序列,有m个形如询问L, R的询问,每次询问需要回答区间内至少出现2次的数有哪些。
*********************************

int len;    // 块长度
struct Query{
    int L, R, ID, block;
    Query(){}  // 构造函数重载
    Query(int l, int r, int ID):L(l), R(r), ID(ID){
        block = l / len;
    }
    bool operator < (const Query rhs) const {
        if(block == rhs.block) return R < rhs.R;  // 不是if(L == rhs.L) return R < rhs.R; return L < rhs.L
        return block < rhs.block;           // 否则这就变回算法一了
    }
}queries[maxm];

map<int, int> buf;

inline void insert(int n){
    if(buf.count(n))
        ++buf[n];
    else
        buf[n] = 1;
}
inline void erase(int n){
    if(--buf[n] == 0) buf.erase(n);
}

int A[maxn];        // 原序列
queue<int> anss[maxm];  // 存储答案

int main(){
    int n, m;
    cin >> n;
    len = (int)sqrt(n);    // 块长度
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    cin >> m;
    for(int i = 1; i <= m; i++){
        int l, r;
        cin >> l >> r;
        queries[i] = Query(l, r, i);
    }
    sort(queries + 1, queries + m + 1);
    int L = 1, R = 1;
    buf[A[1]] = 1;
    for(int i = 1; i <= m; i++){
        queue<int>& ans = anss[queries[i].ID];
        Query &qi = queries[i];
        while(R < qi.R) insert(A[++R]);
        while(L > qi.L) insert(A[--L]);
        while(R > qi.R) erase(A[R--]);
        while(L < qi.L) erase(A[L++]);

        for(map<int, int>::iterator it = buf.begin(); it != buf.end(); ++it){
            if(it->second >= 2){
                ans.push(it->first);
            }
        }
    }
    for(int i = 1; i <= m; i++){
        queue<int>& ans = anss[i];
        while(!ans.empty()){
            cout << ans.front() <<  ;
            ans.pop();
        }
        cout << endl;
    }
}

在update的同时更新ans。(本题可考虑维护一个set,表示出现至少两次的数的集合)

莫队算法