首页 > 代码库 > [学习-思考-探究]莫队算法 曼哈顿最小生成树与分块区间询问算法-3

[学习-思考-探究]莫队算法 曼哈顿最小生成树与分块区间询问算法-3

2024-11-27 04:19:02   203人阅读

若要转载，不需要联系我，只需要在下面回复一下并注明原文。

在线区间询问算法(增强算法)2

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdio>
 
using namespace std;
 
//该模版需要状态满足区间可减性
//该模版写的是 小Z的袜子 ...
 
typedef long long LL;
 
const int maxn = 50005;
const int tmaxn = 888;
 
int block_size;
 
struct Val {
    int t, v;
    Val(int t_, int v_) : t(t_), v(v_) {}
    bool operator<(Val b) const {
        return t < b.t;
    }
};
 
vector<Val> stat[tmaxn][maxn];
 
int GetInt() {
    int x = 0, F = 1; char C = getchar();
    while (C < ‘0‘ || C > ‘9‘) { if (C == ‘-‘) F = -F; C = getchar(); }
    while (C >= ‘0‘ && C <= ‘9‘) { x = x * 10 - ‘0‘ + C, C = getchar(); }
    return x * F;
}
 
 
inline int getLast(int b, int in) {
    if (stat[b][in].empty()) return 0;
    vector<Val>::iterator iter = stat[b][in].end();
    return (--iter)->v;
}
 
inline void insert(LL &o, int b, int in, int t) {
    //这里是小z的袜子独有写法
    o -= (getLast(b, in)*(getLast(b, in)-1)) >> 1;
    stat[b][in].push_back(Val(t, getLast(b, in)+1));
    o += (getLast(b, in)*(getLast(b, in)-1)) >> 1;
}
 
LL val[tmaxn][tmaxn];
 
int col[maxn];
 
int n, m;
 
vector<int> ra, rb;
 
int cnt[maxn];
int ts[maxn];
int tms = 0;
 
inline void update_clear(int in) {
    if (ts[in] < tms) {
        ts[in] = tms;
        cnt[in] = 0;
    }
}
 
int lb = 0, ri = 0;
 
inline void update_restore(int in) {
    if (ts[in] < tms) {
        ts[in] = tms;
        if (stat[lb][in].empty()) cnt[in] = 0;
        else {
            int t = int(lower_bound(stat[lb][in].begin(), stat[lb][in].end(), Val(ri, 0))-stat[lb][in].begin());
            if (stat[lb][in][t].t > ri) t--;
            if (t < 0) cnt[in] = 0;
            else cnt[in] = stat[lb][in][t].v;
        }
    }
}
 
inline LL getAns(int l, int r) {
    if (r-l+1 <= block_size) {
        ++ tms;
        LL ret = 0;
        for (int i = l; i <= r; i++) {
            update_clear(col[i]);
            ret -= (cnt[col[i]]*(cnt[col[i]]-1)) >> 1;
            cnt[col[i]] ++;
            ret += (cnt[col[i]]*(cnt[col[i]]-1)) >> 1;
        }
        return ret;
    } else {
        int a = l, b = r;
        ra.clear(), rb.clear();
        while (a % block_size) {
            ra.push_back(a);
            a++;
        }
        while (b % block_size) {
            rb.push_back(b);
            b--;
        }
        int a_b = a / block_size;
        int b_b = b / block_size;
        LL ret = val[a_b][b_b];
        lb = a_b;
        ri = b;
        ++ tms;
        for (int i = 0; i < ra.size(); i++) {
            update_restore(col[ra[i]]);
            ret -= (cnt[col[ra[i]]]*(cnt[col[ra[i]]]-1)) >> 1;
            cnt[col[ra[i]]] ++;
            ret += (cnt[col[ra[i]]]*(cnt[col[ra[i]]]-1)) >> 1;
        }
        for (int i = 0; i < rb.size(); i++) {
            update_restore(col[rb[i]]);
            ret -= (cnt[col[rb[i]]]*(cnt[col[rb[i]]]-1)) >> 1;
            cnt[col[rb[i]]] ++;
            ret += (cnt[col[rb[i]]]*(cnt[col[rb[i]]]-1)) >> 1;
        }
        return ret;
    }
}
 
LL gcd(LL a, LL b) {
    if (!b) return a;
    return gcd(b, a%b);
}
 
int main() {
    //freopen("sock.in", "r", stdin);
    //freopen("sock.out", "w", stdout);
    n = GetInt(), m = GetInt();
    for (int i = 0; i < n; i++) {
        col[i] = GetInt();
    }
    block_size = sqrt(n/(log(n)/log(2)+1));
    for (int i = 0; i < n; i++) {
        if (i % block_size == 0) {
            //这个循环的范围仅针对小Z的袜子!
            int b_in = i / block_size;
            LL ans = 0;
            for (int j = i; j < n; j++) {
                insert(ans, b_in, col[j], j);
                if (j % block_size == 0) {
                    val[b_in][j/block_size] = ans;
                }
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        int l = GetInt(), r = GetInt();
        LL ans = getAns(l-1, r-1);
        LL len = r-l+1;
        if (ans == 0) {
            printf("0/1\n");
        } else {
            LL fm = len*(len-1)/2;
            LL g = gcd(ans, fm);
            printf("%lld/%lld\n", ans/g, fm/g);
        }
    }
    return 0;
}

 这一段代码空间太大不能AC，但是非常有用，具有普遍性。如果不想看可以直接看下一篇，比较重要和有效。

 

 

这道题不是已经用在线算法A过了，怎么又来一遍？

别忘了！之前用到了区间可加性！

这次的算法既不用区间可加性，也不用区间可减性，是怎么做到的呢？

从一个端点出发，到每一个点的区间，可以依次向又更新，每次最多更新一个点。

因此我们可以使用可持久化思想。

这里是用的是一种乱想出来的“可持久化”数组。通过vector记录每一项的修改，然后通过二分查找的方式，获得某一时间的状态。

这样查询复杂度多了一个log。

引用以前写的说明：

技术分享

 嗯，于是我们就成功把log放进了根号了。

如果你还没有看懂，或者有兴趣与我讨论，可以加QQ2502669375
下一篇链接：

[学习-思考-探究]莫队算法 曼哈顿最小生成树与分块区间询问算法-4

 

 
 
 

[学习-思考-探究]莫队算法 曼哈顿最小生成树与分块区间询问算法-3


联系
我们