笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 P4396 【[AHOI2013]作业】

posted on 2020-04-12 00:47:48 | under 题解 |

写一个感觉比较详细(萌新友好向)的莫队做法…复杂度 $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 我