• 周四. 6月 30th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

HDOJ 6964 I love counting

admin

11月 28, 2021

题目链接

HDOJ6964 I love counting

题目大意

给定一个长度为 (n) 的序列 ({c})(q) 次询问,每次给出 (l,r,a,b),求在 ([l,r]) 中有多少种不同的值 (k) 满足 (koplus aleq b)​.

(1leq n,qleq 10^5)(1leq c_ileq n)(a,bleq n+1)

思路

做法一

求区间内有多少种不同的权值?这不是经典问题嘛,先把询问离线下来,按照 (r) 从小到大排序,然后用线段树维护数字的出现情况,当 (r) 扫到值 (c_i) 时,先在线段树上 (i)(+1)​,若 (c_i) 之前出现过,线段树上在之前出现的那个位置 (-1)​​,然后直接线段树查询 ([l,r]) 区间和即可。

这里采用类似的做法,在线段树每个节点上储存一棵 (Trie)​​​,表示对应区间上数字,在上传信息时,直接将两个儿子的 (Trie)​​​ 合并起来给父亲即可,由于一个数字会在 (Trie)​​​ 上产生 (O(log n))​​​ 个节点,而线段树有 (O(log n))​ 层,所以空间复杂度为 (O(nlog^2n))​​ 。在查询时找到 ([l,r]) 对应的 (O(log n)) 个节点,将 (Trie) 上的答案加起来即可。

(Trie) 上的询问很简单,传入两个参数 (a,b),在 (Trie) 上贴着 (aoplus b) 走,若 (b) 当前位是 (1),则所有 (koplus a) 在当前位是 (0) 的数字都符合要求(前面的所有位置都与 (aoplus b) 相同),即将对应节点的子树大小加入到答案中,最后再把 (k=aoplus b) 的情况加到答案里即可,(O(log n))

综上,时间复杂度 (O((n+q)log^2 n)),空间复杂度 (O(nlog^2 n))

然而我们看一眼题目空间限制:(256MB),而 (Trie) 的每个节点需要储存 (siz,leftson,rightson) 三个 (int),满打满算需要 (315.8MB)​ 的内存,卡不过去!后来脑子清醒了一下,发现这里「单点加区间查询」的操作树状数组就可以做了,而根据树状数组的结构性质,它的空间复杂度具有 (frac{1}{2})​​ 的常数(每一层的大小都为 (frac{n}{2})),所以上树状数组就行了!交上去实际使用内存 (100.8MB)​,然后就过了。

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<fstream>
#include<ctime>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 100100
#define LOG 17
#define lowbit(x) (x&-x)
using namespace std;

inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') s = (s<<3)+(s<<1)+(ch^48), ch = getchar();
    return s*w;
}

int p[N], lst[N], ans[N];
int n, q;

struct node{
    int siz, c[2];
} t[N*LOG*LOG/2]; //卡空间!
int cnt;

void insert(int x, int k, int id){
    t[x].siz += id;
    per(i,16,0){
        int dir = k>>i&1;
        if(!t[x].c[dir]) t[x].c[dir] = ++cnt;
        x = t[x].c[dir];
        t[x].siz += id;
    }
}
int query(int x, int a, int b){
    int ret = 0;
    per(i,16,0){
        int id = b>>i&1;
        int dir = id^(a>>i&1);
        if(id) ret += t[t[x].c[dir^1]].siz;
        if(!t[x].c[dir]) break;
        x = t[x].c[dir];
        if(i == 0) ret += t[x].siz;
    }
    return ret;
}

struct Fenwik_Tree{
    int t[N];

    void add(int loc, int k, int id){
        while(loc <= n) insert(t[loc], k, id), loc += lowbit(loc);
    }
    int query(int loc, int a, int b){
        int ret = 0;
        while(loc) ret += ::query(t[loc], a, b), loc -= lowbit(loc);
        return ret;
    }
} BIT;

struct query{
    int l, r, a, b, id;
    bool operator < (query c){ return r < c.r; }
} ask[N];

int main(){
    n = read();
    rep(i,1,n) p[i] = read();
    q = read();
    rep(i,1,q){
        ask[i].l = read(), ask[i].r = read(), ask[i].a = read(), ask[i].b = read();
        ask[i].id = i;
    }

    rep(i,1,n) BIT.t[i] = i;
    cnt = n;
    sort(ask+1, ask+q+1);
    int now = 1;
    rep(i,1,q){
        while(now <= ask[i].r){
            if(lst[p[now]]) BIT.add(lst[p[now]], p[now], -1);
            BIT.add(now, p[now], 1);
            lst[p[now]] = now;
            now++;
        }
        ans[ask[i].id] = BIT.query(ask[i].r, ask[i].a, ask[i].b) - BIT.query(ask[i].l-1, ask[i].a, ask[i].b);
    }
    rep(i,1,q) printf("%d
", ans[i]);
    return 0;
}

做法二

做法一是「树状数组套 (Trie) 」,它时空复杂度同阶的原因是,树套树两层数据结构都是时空复杂度同阶的(树状数组拥有 (O(log n)) 层,所以套起来就不是线性空间的),所以如果可以把其中一个换成线性空间的数据结构,如套在里面的树状数组,或者平衡树,空间复杂度就可以少一个 (log),无需卡空间了。

(Trie) 在里面,外面的选择就只有平衡树,显然这没法做,那就把 (Trie) 放外面!考虑 (Trie) 套平衡树的做法,我们只建一棵 (Trie)(Trie)​​ 上每个节点开一棵平衡树,维护有哪些下标的值会访问到当前节点,这里为了去重,也需要按照之前的策略,把询问离线下来按 (r)​ 排序,将每个值先前出现的位置在平衡树上删去,然后查询时直接在 (Trie)​ 上走,在合法的节点平衡树上找有多少节点的 (valgeq l),统计答案即可。

时间复杂度 (O(nlog^2 n)),空间复杂度 (O(nlog n))

实现细节

  • 出题人毒瘤,他卡常。开始写了 (fhqTreap) 被卡的死死的,换成 (rotate) 版本的 (Treap) 才卡过去。

  • 为了平衡空间,开始每棵 (Treap) 里都是用 (vector) 存节点的,本人的 (Treap)​ 是通过引用操作对节点进行修改信息的,然而 (vector) 的内容进行引用操作是 Undefined Behaviour,因为 (vector)​​ 在改变长度时会重构空间,导致指向原地址的指针失效。

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<cstdio>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 100100
#define LOG 17
#define Root -1
#define rt(x) t[x].p.root
#define Inf 0x3f3f3f3f
using namespace std;

inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') s = (s<<3)+(s<<1)+(ch^48), ch = getchar();
    return s*w;
}

struct node{
    int val, siz, dat;
    int c[2];
    node(){ val = siz = dat = c[0] = c[1] = 0; }
} t[2*N*LOG];
int cnt;

struct Treap{
    int root;

    int New(int val){
        ++cnt;
        t[cnt].val = val, t[cnt].dat = rand(), t[cnt].siz = 1;
        return cnt;
    }

    void print(int x){
        if(x == Root) x = root;
        if(x == 0) return;
        print(t[x].c[0]), cout<<t[x].val<<" ", print(t[x].c[1]);
    }

    inline void pushup(int x){
        t[x].siz = t[t[x].c[0]].siz + t[t[x].c[1]].siz + 1;
    }

    void init(){
        root = New(-Inf), t[root].c[1] = New(Inf);
        pushup(root);
    }

    void rotate(int &x, int id){
        int u = t[x].c[id];
        t[x].c[id] = t[u].c[id^1], t[u].c[id^1] = x, x = u;
        pushup(t[x].c[id^1]), pushup(x);
    }

    void insert(int &x, int val){
        if(x == 0){ x = New(val); return; }
        if(val < t[x].val){
            insert(t[x].c[0], val);
            if(t[x].dat < t[t[x].c[0]].dat) rotate(x, 0);
        } else{
            insert(t[x].c[1], val);
            if(t[x].dat < t[t[x].c[1]].dat) rotate(x, 1);
        }
        pushup(x);
    }

    void del(int &x, int val){
        if(!x) return;
        if(val == t[x].val){
            if(t[x].c[0] || t[x].c[1]){
                if(!t[x].c[1] || t[t[x].c[0]].dat > t[t[x].c[1]].dat){
                    rotate(x, 0), del(t[x].c[1], val);
                } else rotate(x, 1), del(t[x].c[0], val);
                pushup(x);
            } else x = 0;
            return;
        }
        if(val < t[x].val) del(t[x].c[0], val);
        else del(t[x].c[1], val);
        pushup(x);
    }

    int query(int x, int val){
        if(x == Root) x = root;
        if(x == 0) return 0;
        if(t[x].val < val) return query(t[x].c[1], val);
        else return t[t[x].c[1]].siz + 1 + query(t[x].c[0], val);
    }
};

struct Trie{
    struct node{
        int c[2];
        Treap p;
    } t[N*LOG];
    int cnt;
    Trie(){ cnt = 1, t[1].p.init(); }

    void insert(int k, int pos, int pre){
        if(pre) t[1].p.del(rt(1), pre);
        t[1].p.insert(rt(1), pos);
        int x = 1;
        per(i,16,0){
            int dir = k>>i&1;
            if(!t[x].c[dir]) t[x].c[dir] = ++cnt, t[cnt].p.init();
            x = t[x].c[dir];
            if(pre) t[x].p.del(rt(x), pre);
            t[x].p.insert(rt(x), pos);
        }
    }

    int query(int a, int b, int l){
        int x = 1, ret = 0;
        per(i,16,0){
            int id = b>>i&1;
            int dir = id^(a>>i&1);
            if(id && t[x].c[dir^1]) ret += t[t[x].c[dir^1]].p.query(Root, l)-1;
            if(!t[x].c[dir]) break;
            x = t[x].c[dir];
            if(i == 0) ret += t[x].p.query(Root, l)-1;
        }
        return ret;
    }
} trie;

struct query{
    int l, r, a, b, id;
    bool operator < (query k){ return r < k.r; }
} ask[N];

int a[N], ans[N], lst[N];
int n, q;

int main(){
    srand(time(0));
    n = read();
    rep(i,1,n) a[i] = read();
    q = read();
    rep(i,1,q){
        ask[i].l = read(), ask[i].r = read(), ask[i].a = read(), ask[i].b = read();
        ask[i].id = i;
    }

    sort(ask+1, ask+q+1);
    int it = 1;
    rep(i,1,q){
        while(it <= ask[i].r) 
            trie.insert(a[it], it, lst[a[it]]), lst[a[it]] = it, it++;
        ans[ask[i].id] = trie.query(ask[i].a, ask[i].b, ask[i].l);
    }
    rep(i,1,q) printf("%d
", ans[i]);
    return 0;
}

不过正如前面的分析,(Trie)​ 套树状数组也是可行的,不过要预处理每个节点可能会遇到的所有位置,并将它们各自离散化,然后 (vector)​ 存下标,时空复杂度同上。实现就咕了吧,应该不复杂。


做法三

我会莫队!嗯,讲完了。

时间复杂度 (O(nsqrt nlog n)),空间复杂度 (O(nlog n))

实现细节

虽说莫队就行了,不过 (2s) 的时限和 (5.25e8) 的运算量看起来不大能过,我们来大力卡常!

  • 朴素的实现,按照 ({frac{l}{sqrt n},r}) 双关键字将询问排序,然后直接对 (Trie) 修改和查询:(36s)
  • (pragma) 火箭头优化:(9.8s)
  • (num_i) 记录数字 (i)([l,r]) 的出现次数,若插入当前数字不会改变答案,就不插了:(3.3s)
  • (cin) 去同步换成快读:(980ms)
  • 既然只有一棵 (01Trie)​,采用线段树的节点标号方式,上位运算:(263ms)

现在看起来非常稳了,交一发试试,出题人的数据真强,竟然跑了 (1450ms)

  • 把排序标准换成:当 (frac{l}{sqrt n}) 相同时,若 (frac{l}{sqrt n}) 为奇数,返回 (r_igeq r_j),否则返回 (r_ileq r_j)​:(268ms)

    这么做使得 (r) 的位置变化可以被充分利用,本身莫队的常数为 (3)(n)(O(sqrt n))(l) 变化,发生在块内的 (sqrt n)(O(n))(r) 右移,发生在块间的 (sqrt n)(O(n))(r) 左移),这样常数就只有 (2)​ 了。

虽然本地慢了一点,但是交上去只要 (967ms) 了,系三种做法中最快的,经过卡常,代码在本地快了 (137) 倍,跑出了一秒 (6e8) 的神速!

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<fstream>
#include<ctime>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 100010
#define B 316
#define LOG 17
using namespace std;

inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') s = (s<<3)+(s<<1)+(ch^48), ch = getchar();
    return s*w;
}

int num[N], siz[N*LOG];
int cnt = 1;

void insert(int k, int id){
    if(!k) return;
    if(id == -1 && --num[k] > 0) return;
    if(id == 1 && num[k]++ > 0) return;
    int x = 1;
    siz[x] += id;
    per(i,16,0) x = (x<<1) + (k>>i&1), siz[x] += id;
}
int query(int a, int b){
    int x = 1, ret = 0;
    per(i,16,0){
        int dir = (b>>i&1)^(a>>i&1);
        if(b>>i&1) ret += siz[(x<<1) + (dir^1)];
        x = (x<<1) + dir;
    }
    ret += siz[x];
    return ret;
}

int a[N], ans[N];
int n, q;

struct query{
    int l, r, a, b, id;
    bool operator < (query k){ return (l/B != k.l/B ? l/B < k.l/B : (r < k.r) ^ ((l/B)&1)); }
} ask[N];

int main(){
    n = read();
    rep(i,1,n) a[i] = read();
    q = read();
    rep(i,1,q){
        ask[i].l = read(), ask[i].r = read(), ask[i].a = read(), ask[i].b = read();
        ask[i].id = i;
    }

    sort(ask+1, ask+q+1);
    int l = 0, r = 0;
    rep(i,1,q){
        while(l > ask[i].l) insert(a[--l], 1);
        while(r < ask[i].r) insert(a[++r], 1);
        while(l < ask[i].l) insert(a[l++], -1);
        while(r > ask[i].r) insert(a[r--], -1);
        ans[ask[i].id] = query(ask[i].a, ask[i].b);
    }

    rep(i,1,q) printf("%d
", ans[i]);
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。