题解 P4396 【[AHOI2013]作业】

皎月半洒花 · 2020-04-12 00:47:48 · 题解

写一个感觉比较详细(萌新友好向)的莫队做法…复杂度 O(n\sqrt m+m\sqrt n) 。

考虑直接莫队的话，需要支持查询某个值域区间中的数，需要上树状数组，但这样带 \log 。

于是考虑一下莫队的本质，即莫队的复杂度分析，本质上分析的是 l,r 移动的复杂度，也就是修改的复杂度。所以莫队可以本质上看成一个 O(n\sqrt m) 修改，O(m) 询问的数据结构。观察到询问数较少，于是可以用一个可以快速修改，低速查询的 ds 来维护值域，那这自然就是值域分块，最终复杂度 O(n\sqrt m+m\sqrt n) 。

以下是补充内容：

1、莫队的复杂度分析

令 m 为操作数，B 为块大小。考虑对于一个块内的 l，其 r 是单增的，于是考虑如下：

• 左端点，在块内可能会一前一后这样设置，这样复杂度被卡到最满，为 O(m\cdot B) ；
• 右端点，考虑各块内的询问显然都可以做到单块 O(n)，所以不需要考虑 m 的贡献，即右端点移动的复杂度就是 \frac{n}{B}\cdot n=\frac{n^2}{B}。

均值一下发现 m\cdot B+\frac{n^2}{B}\geq 2\sqrt{n^2m}=O(n\sqrt m) ，此时有 m\cdot B=\frac{n^2}{B}，解得 B=\frac{n}{\sqrt m} .

所以取块大小为 \frac{n}{\sqrt m} 时达到理论最优，复杂度为 O(n\sqrt m) 。

2、值域分块的正确打开方式

观察到我们本质上需要一个值域上 O(1) 单点加/减，O(\sqrt n) 区间询问的结构，那就是普通的分块了。考虑分块维护块内和和单点值，修改的时候 O(1) 修改点值和块值，询问就是朴素询问(for 过去)即可。

然后本题需要分别维护出现次数和是否出现，分别维护即可。

#include <bits/stdc++.h>

using namespace std ;

const int N = 200010 ;

void debug(int *tp, int minn, int maxn, char c){
    for (int i = minn ; i <= maxn ; ++ i)
        cout << tp[i] << " " ;  cout << c ;
}

int B ; 
int V ; 
int n, m ;
int bl[N] ;
int blv[N] ;
int res[N] ;
int ans[N] ;
int sum[N] ;
int sumr[N] ;
int sump[N] ;
int base[N] ;

struct query{
    int id ; 
    int l, r ; 
    int a, b ; 
}q[N] ;

bool comp(query a, query b){
    return (bl[a.l] ^ bl[b.l]) ? bl[a.l] < bl[b.l] : 
           ((bl[a.l] & 1) ? a.r < b.r : a.r > b.r) ;
}
void del(int p){
    sump[base[p]] -- ; 
    sumr[blv[base[p]]] -- ;
    if (sump[base[p]] <= 0) -- sum[blv[base[p]]]  ; 
}
void add(int p){
    sump[base[p]] ++ ; 
    sumr[blv[base[p]]] ++ ; 
    if (sump[base[p]] <= 1) ++ sum[blv[base[p]]]  ; 
}
int get_ans(int l, int r){
    int ret = 0 ; 
    r = min(r, V) ; 
    if (l > V) return 0 ; 
    int nl = blv[l] + 1 ; 
    int nr = blv[r] - 1 ;
    if (blv[l] == blv[r]){
        for (int i = l ; i <= r ; ++ i)
            ret += (bool)sump[i] ; return ret ; 
    }
    for (int i = nl ; i <= nr ; ++ i) ret += sum[i] ;
    for (int i = l ; blv[i] == blv[l] && l <= V ; ++ i) ret += (bool)sump[i] ;
    for (int i = r ; blv[i] == blv[r] && r >= 0 ; -- i) ret += (bool)sump[i] ;
    return ret ;
}
int get_res(int l, int r){
    int ret = 0 ; 
    r = min(r, V) ; 
    if (l > V) return 0 ; 
    int nl = blv[l] + 1 ; 
    int nr = blv[r] - 1 ;
    if (blv[l] == blv[r]){
        for (int i = l ; i <= r ; ++ i)
            ret += sump[i] ; return ret ; 
    }
    for (int i = nl ; i <= nr ; ++ i) ret += sumr[i] ;
    for (int i = l ; blv[i] == blv[l] && l <= V ; ++ i) ret += sump[i] ;
    for (int i = r ; blv[i] == blv[r] && r >= 0 ; -- i) ret += sump[i] ;
    return ret ;
}
int main(){
    cin >> n >> m ; 
    B = 1.0 * n / sqrt(m) + 1 ; 
    for (int i = 1 ; i <= n ; ++ i)
        scanf("%d", &base[i]), V = max(V, base[i]), bl[i] = i / B ; 
    for (int i = 1 ; i <= m ; ++ i)
        scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].a, &q[i].b), q[i].id = i ; 
    sort(q + 1, q + m + 1, comp) ; 
    int l = 1, r = 0 ; B = sqrt(V) + 1 ; 
    for (int i = 0 ; i <= V ; ++ i) blv[i] = i / B ; 
    for (int i = 1 ; i <= m ; ++ i){
        int a = q[i].a, b = q[i].b ; 
        while (l < q[i].l) del(l ++) ; 
        while (l > q[i].l) add(-- l) ; 
        while (r < q[i].r) add(++ r) ;
        while (r > q[i].r) del(r --) ;
        res[q[i].id] = get_res(a, b) ;
        ans[q[i].id] = get_ans(a, b) ; 
    }
    for (int i = 1 ; i <= m ; ++ i) 
        printf("%d %d\n", res[i], ans[i]) ; return 0 ; 
}

快来夸我码风! (超自豪

我是一个刚开始学 lxl 深刻理论的萌新，不要 d 我