值域分块学习笔记

First Post:

Last Update:

Word Count:
9.2k

Read Time:
48 min

参考文章

又是一个很有用但一直不会的东西，今天学习一下。

不过写的还是比较浅显，可以看参考文章，讲的很好。

什么是值域分块

普通的分块都学过，它是对序列分块的。

而值域分块，顾名思义，是对值域分块。

序列分块和值域分块的关系就像线段树和权值线段树的关系一样，一个维护序列，一个维护值域。

两种常用的值域分块

第一种：修改 ，查询

维护每个值域上每个值的值和每个值域块内的值的总和。

1
2
3
4
5
6
7
8
9
10
11
inline void add(int x){++cnt1[x],++cnt2[bel[x]];}
inline int query1(int l,int r){
    int L=bel[l],R=bel[r],res=0;
    if(L==R) for(re int i=l;i<=r;++i) res+=cnt1[i];
    else{
        for(re int i=l;i<=ed[L];++i) res+=cnt1[i];
        for(re int i=st[R];i<=r;++i) res+=cnt1[i];
        for(re int i=L+1;i<=R-1;++i) res+=cnt2[i];
    }
    return res;
}

第二种：修改 ，查询

维护每个值域上每个值的值的前缀和，修改时整块打标记，散块暴力加。

区间查询可以差分成两个前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void add(int x){
    if(tag1[bel[x]]){
        for(re int i=st[bel[x]];i<=ed[bel[x]];++i) cnt[i]+=tag1[bel[x]];
        tag1[bel[x]]=0;
    }
    if(tag2[bel[x]]){
        for(re int i=st[bel[x]];i<=ed[bel[x]];++i) sum[i]+=tag2[bel[x]];
        tag2[bel[x]]=0;
    }
    for(re int i=x;i<=ed[bel[x]];++i) ++cnt[i],sum[i]+=x;
    for(re int i=bel[x]+1;i<=tot;++i) ++tag1[i],tag2[i]+=x;
}
inline int query1(int x){return tag1[bel[x]]+cnt[x];}
inline int query2(int x){return tag2[bel[x]]+sum[x];}

应用

值域分块一般用来平衡复杂度。

例如莫队，我们有 次修改和 次查询，这时可以用 修改， 查询的值域分块平衡复杂度。

而如果用 修改， 查询的其他数据结构，复杂度就来到了混乱邪恶的 ，不可接受。

值域分块配合莫队

[AHOI2013] 作业

可以说是板子题了。

使用 修改， 查询的值域分块。

复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e5+10,maxm=500;
int n,m,siz,tot;
int a[maxn];
int ans1[maxn],ans2[maxn];
int st[maxm],ed[maxm],bel[maxn];
int cnt1[maxm],cnt2[maxn],cnt3[maxm];
struct query{
    int l,r,a,b,id;
}q[maxn];
inline bool cmp(query a,query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void init(){
    siz=sqrt(n);
    tot=n/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<n) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=n;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void add(int x){
    if(!cnt2[x]) ++cnt3[bel[x]];
    ++cnt1[bel[x]];
    ++cnt2[x];
}
inline void del(int x){
    --cnt1[bel[x]];
    --cnt2[x];
    if(!cnt2[x]) --cnt3[bel[x]];
}
inline int get_ans1(int l,int r){
    int L=bel[l],R=bel[r];
    int res=0;
    if(L==R) for(re int i=l;i<=r;++i) res+=cnt2[i];
    else{
        for(re int i=l;i<=ed[L];++i) res+=cnt2[i];
        for(re int i=st[R];i<=r;++i) res+=cnt2[i];
        for(re int i=L+1;i<=R-1;++i) res+=cnt1[i];
    }
    return res;
}
inline int get_ans2(int l,int r){
    int L=bel[l],R=bel[r];
    int res=0;
    if(L==R) for(re int i=l;i<=r;++i) res+=(bool)cnt2[i];
    else{
        for(re int i=l;i<=ed[L];++i) res+=(bool)cnt2[i];
        for(re int i=st[R];i<=r;++i) res+=(bool)cnt2[i];
        for(re int i=L+1;i<=R-1;++i) res+=cnt3[i];
    }
    return res;
}
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif	
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r>>q[i].a>>q[i].b,q[i].id=i;
    init();
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(re int i=1;i<=m;++i){
        while(r<q[i].r) add(a[++r]);
        while(l>q[i].l) add(a[--l]);
        while(r>q[i].r) del(a[r--]);
        while(l<q[i].l) del(a[l++]);
        ans1[q[i].id]=get_ans1(q[i].a,q[i].b);
        ans2[q[i].id]=get_ans2(q[i].a,q[i].b);
    }
    for(re int i=1;i<=m;++i) cout<<ans1[i]<<" "<<ans2[i]<<'\n';
    return 0;
}
[Ynoi2019 模拟赛] Yuno loves sqrt technology II

区间逆序对，不难想到用树状数组维护修改。

但这样复杂度是 的，不能接受。

但可以发现，这个贡献是可以差分的，所以考虑莫队二次离线。

这里还是把二离详细说一下吧（毕竟我也不太懂）。

假设当前在区间 。

我们分四种情况讨论指针的移动。

1.右指针右移

考虑当前到的位置 ，此时会产生的新贡献是 里大于 的个数。

可以差分成 中大于 的个数减去 大于 的个数。

2.右指针左移

考虑当前到的位置 ，此时会减少的贡献是 里大于 的个数。

可以差分成 中大于 的个数减去 大于 的个数。

3.左指针左移

考虑当前到的位置 ，此时会产生的新贡献是 里小于 的个数。

可以差分成 中小于 的个数减去 小于 的个数。

4.左指针右移

考虑当前到的位置 ，此时会减少的贡献是 里小于 的个数。

可以差分成 中小于 的个数减去 小于 的个数。

请注意上文的减少，因为是减少下面的那个东西，所以要记得变号。

然后可以发现有一些可以预处理出来。

例如 中 的个数， 中 的个数。

然后剩下的部分离线下来，一共 次修改和 次询问。

然后扫描线，用数据结构维护剩下形如：每次求一个前缀中 或 的数的个数。

这让你想到了什么？值域分块！

我们用 修改， 查询的值域分块维护这个东西。

最后，别忘了我们上面讨论的都是变化量，相当于答案的差分，所以最后还要求个前缀和得到答案。

我们如果直接存 次询问，空间复杂度是 的。

但是不难发现，莫队每次的指针移动是一段区间，所以直接把这一段区间一块存下来就行了。

空间复杂度变为 。

这是莫队二离的一个经典优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include"bits/stdc++.h"
#define re register
// #define int long long
#define lb(x) (x&(-x))
using namespace std;
const int maxn=1e5+10,maxm=500;
int n,m,siz,tot,len;
int a[maxn],b[maxn],tr[maxn];
int st[maxm],ed[maxm],bel[maxn],idx[maxn];
int fl[maxn],fr[maxn];
int cnt[maxn],tag[maxm];
long long ans[maxn];
struct query{
    int l,r,id;
    long long ans;
}q[maxn];
struct node{
    int l,r,id,op;
};
vector<node> g1[maxn],g2[maxn];
inline bool cmp(query a,query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void add(int x,int val){while(x<=maxn) tr[x]+=val,x+=lb(x);}
inline int query(int x){int res=0;while(x>0) res+=tr[x],x-=lb(x);return res;}
inline void pre(){
    for(re int i=1;i<=n;++i){
        fr[i]=i-1-query(a[i]);
        add(a[i],1);
    }
    for(re int i=1;i<=n;++i) add(a[i],-1);
    for(re int i=1;i<=n;++i){
        add(a[i],1);
        fl[i]=query(a[i]-1);
    }
}
inline void init(){
    siz=sqrt(len);
    tot=ceil(len/siz);
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<len) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=len;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i,idx[j]=j-st[i]+1;
}
inline void update(int x,int val){
    if(tag[bel[x]]){
        for(re int i=st[bel[x]];i<=ed[bel[x]];++i) cnt[i]+=tag[bel[x]];
        tag[bel[x]]=0;
    }
    for(re int i=x;i<=ed[bel[x]];++i) cnt[i]+=val;
    for(re int i=bel[x]+1;i<=tot;++i) tag[i]+=val;
}
inline int query1(int x){return tag[bel[x]]+cnt[x];}
inline void solve_l(){
    for(re int i=1;i<=n;++i){
        update(a[i],1);
        for(auto t:g1[i]){
            for(re int j=t.l;j<=t.r;++j){
                q[t.id].ans+=t.op*(i-query1(a[j]));
            }
        }
    }
    for(re int i=1;i<=n;++i) update(a[i],-1);
}
inline void solve_r(){
    for(re int i=1;i<=n;++i){
        update(a[i],1);
        for(auto t:g2[i]){
            for(re int j=t.l;j<=t.r;++j){
                q[t.id].ans+=t.op*query1(a[j]-1);
            }
        }
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    len=unique(b+1,b+n+1)-(b+1);
    for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    pre();
    for(re int i=1;i<=m;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    siz=sqrt(n);
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(re int i=1;i<=m;++i){
        if(r<q[i].r){
            g1[l-1].push_back({r+1,q[i].r,i,-1});
            while(r<q[i].r) q[i].ans+=fr[++r];
        }
        if(l>q[i].l){
            g2[r].push_back({q[i].l,l-1,i,1});
            while(l>q[i].l) q[i].ans-=fl[--l];
        }
        if(r>q[i].r){
            g1[l-1].push_back({q[i].r+1,r,i,1});
            while(r>q[i].r) q[i].ans-=fr[r--];
        }
        if(l<q[i].l){
            g2[r].push_back({l,q[i].l-1,i,-1});
            while(l<q[i].l) q[i].ans+=fl[l++];
        }
    }
    init();
    solve_l();
    solve_r();
    for(re int i=1;i<=m;++i) q[i].ans+=q[i-1].ans;
    for(re int i=1;i<=m;++i) ans[q[i].id]=q[i].ans;
    for(re int i=1;i<=m;++i) cout<<ans[i]<<'\n';
    return 0;
}

值域分块配合根号分治

[JRKSJ R4] risrqnis

很好的一道题，加深了我对根号分治和平衡复杂度的理解。

首先考虑 怎么做。

这个对值域上的操作很讨厌，因为值域很大。

但不难发现，把所有操作离线后离散化，可以做到值域 ，且每个数至多被加入一次。

所以我们把每个数挂到对应的值上，然后用 set 维护还没有被加入的数，每次加入时查值域上的前驱后继即可。至于求和，树状数组维护即可。

这样做的话，均摊复杂度是 的。

那 怎么办？

首先可以把 离散化到 。

然后关键来了：考虑对每个集合的操作次数根号分治。

对于操作次数 的集合，个数是 的，那么我们直接按上面那个做法做，总复杂度是 的。

但这个复杂度是不能接受的。

但可以发现，我们一共有 次修改和 次查询（这里可能会有疑惑：每个集合的修改和询问不都是 的吗？那总的操作为什么不都是 ？因为总的操作次数一共是 的，而修改是值域上的修改，所以可以保证每个集合都做到 次修改，但查询是有总和保证的，总询问一定也是 的）。

所以可以用序列分块来平衡复杂度，这样可以做到 修改， 查询。

然后瓶颈就是 set 每次查找的 了，我们考虑去掉这个 。

一开始想到的是链表，但链表删除虽然是 ，但每次还得找第一个没被删的，这是 的。

然后想到并查集，发现可以做。

思路还是和链表一样，每删一个就更新父亲，相当于把那个数删除了。

每次找的时候也是找父亲。

总复杂度为

然后考虑操作次数 的集合。

这种集合的个数是 的，但操作次数是 的。

这可以得到一个很关键的性质：操作后的值域上的连续段个数不超过 。

然后我们再想想询问在干什么：求值域上在已经出现过的连续段内且序列上下标在 之间的点的个数。

这是个标准的二维数点。

因为连续段个数不超过 ，所以询问可以看成对 个连续段分别查询。

那么一共有 次修改和 次询问（这里可能又有疑惑：一共 个集合，每个集合修改次数都是 的，那为什么总修改次数还是 的？因为可以发现，具体是哪个集合对答案没有影响，所以我们可以先把所有询问离线下来，这样一共有 次询问，但我们只需要修改 次即可）。

考虑扫描序列维，然后用值域分块维护另一维。

总复杂度

综上，总复杂度为 。

但你先别急，因为这东西空间复杂度是 ，直接炸了。

然后有一些神奇技巧来优化空间，例如离线逐块处理，分散层叠等。

但我摆了。

还有个坑点，在处理小块的时候，我们要离线询问，但是不能直接离线。

例如第一次修改，把值域 加进去，第二次修改，把值域 加进去。

如果这两段有交，那么交集部分不能算两次，只能算一次。

所以离线询问时要处理这个东西。

注意特殊处理 ，因为空间开不下。

还有注意离散化后值域是

代码是空间 的，只能得 45 pts。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include"bits/stdc++.h"
#define re register
// #define int long long
#define pii pair<int,int> 
#define fi first
#define se second
#define lb(x) (x&(-x))
using namespace std;
const int maxn=1e6+10,maxm=1750;
int n,m,Q,siz,tot,cnt;
int a[maxn],b[3*maxn],ans[maxn],fa[maxn*3];
int st[maxm],ed[maxm],bel[maxn],idx[maxn];
int sum1[maxn],sum2[maxm];
pii stk[maxn];
int cnt1[maxn*3],cnt2[maxm][maxm];
struct query{
    int op,l,r,k,id;
}q[maxn];
vector<int> g[maxn],s[maxn];
vector<query> q1[maxn];
inline void init(){
    int tmp=max(n,cnt);
    siz=sqrt(tmp);
    tot=ceil(tmp/siz);
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<tmp) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=tmp;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i,idx[j]=j-st[i]+1;
}
inline void clear(){
    for(re int i=1;i<=cnt+1;++i) fa[i]=i;
    memset(sum1,0,sizeof sum1),memset(sum2,0,sizeof sum2);
}
inline void add(int x){++sum1[x],++sum2[bel[x]];}
inline int query(int l,int r){
    int L=bel[l],R=bel[r],res=0;
    if(L==R) for(re int i=l;i<=r;++i) res+=sum1[i];
    else{
        for(re int i=l;i<=ed[L];++i) res+=sum1[i];
        for(re int i=st[R];i<=r;++i) res+=sum1[i];
        for(re int i=L+1;i<=R-1;++i) res+=sum2[i];
    }
    return res;
}
inline int find(int x){if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];}
inline void solve1(int id){
    clear();
    for(auto x:g[id]){
        if(q[x].op==1){
            int pos=find(q[x].l);
            while(pos<=q[x].r){
                for(auto v:s[pos]) add(v);
                fa[pos]=fa[pos+1];
                pos=find(pos+1);
            }
        }
        else ans[q[x].id]=query(q[x].l,q[x].r);
    }
}
inline void solve2(int id){
    int top=0;
    for(auto x:g[id]){
        if(q[x].op==1) stk[++top]={q[x].l,q[x].r};
        else{
            if(!top) continue;
            sort(stk+1,stk+top+1);
            int nowl=stk[1].fi,nowr=stk[1].se;
            for(re int i=2;i<=top;++i){
                if(stk[i].fi<=nowr) nowr=max(nowr,stk[i].se);
                else{
                    q1[q[x].l-1].push_back({-1,nowl,nowr,998244353,q[x].id});
                    q1[q[x].r].push_back({1,nowl,nowr,998244353,q[x].id});	
                    nowl=stk[i].fi,nowr=stk[i].se;
                }
            }
            q1[q[x].l-1].push_back({-1,nowl,nowr,998244353,q[x].id});
            q1[q[x].r].push_back({1,nowl,nowr,998244353,q[x].id});	
        }
    }
}
inline void update(int x){
    int id=bel[x];
    for(re int i=id;i<=tot;++i) ++cnt1[i];
    for(re int i=idx[x];i<=idx[ed[id]];++i) ++cnt2[id][i];
}
inline int query1(int l,int r){
    int L=bel[l],R=bel[r];
    long long res=0;
    if(L==R) res+=(cnt2[L][idx[r]]-cnt2[L][idx[l]-1]);
    else{
        res+=(cnt2[L][idx[ed[L]]]-cnt2[L][idx[l]-1]);
        res+=(cnt2[R][idx[r]]);
        res+=(cnt1[R-1]-cnt1[L]);
    }
    return res;
}
inline void solve(){
    for(re int i=1;i<=n;++i){
        update(a[i]);
        for(auto x:q1[i]){
            ans[x.id]+=x.op*query1(x.l,x.r);
        }
    }
}
int tr[maxn];
inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
inline void solve0(){
    for(re int i=1;i<=n;++i) cin>>a[i],b[i]=a[i],stk[i]={a[i],i};
    sort(b+1,b+n+1);sort(stk+1,stk+n+1);
    for(re int i=1;i<=n+1;++i) fa[i]=i;
    int op,l,r,k;
    while(Q--){
        cin>>op>>l>>r>>k;
        if(op==1){
            l=lower_bound(b+1,b+n+1,l)-b,r=upper_bound(b+1,b+n+1,r)-b-1;
            int pos=find(l);
            while(pos<=r){
                add(stk[pos].se,1);
                fa[pos]=fa[pos+1];
                pos=find(pos+1);
            }
        }
        else cout<<query(r)-query(l-1)<<'\n';
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>Q>>m;
    if(m==1){solve0();return 0;}
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1;i<=Q;++i) cin>>q[i].op>>q[i].l>>q[i].r>>q[i].k,q[i].id=i,b[i]=q[i].k;
    sort(b+1,b+Q+1);
    m=unique(b+1,b+Q+1)-(b+1);
    for(re int i=1;i<=Q;++i) q[i].k=lower_bound(b+1,b+m+1,q[i].k)-b,g[q[i].k].push_back(i);
    cnt=0;
    for(re int i=1;i<=n;++i) b[++cnt]=a[i];
    for(re int i=1;i<=Q;++i) if(q[i].op==1) b[++cnt]=q[i].l,b[++cnt]=q[i].r;
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-(b+1);
    for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b,s[a[i]].push_back(i);
    for(re int i=1;i<=Q;++i) if(q[i].op==1) q[i].l=lower_bound(b+1,b+cnt+1,q[i].l)-b,q[i].r=lower_bound(b+1,b+cnt+1,q[i].r)-b;
    init();
    for(re int i=1;i<=m;++i){
        if(g[i].size()>=sqrt(Q)) solve1(i);
        else solve2(i);
    }
    solve();
    for(re int i=1;i<=Q;++i) if(q[i].op==2) cout<<ans[i]<<'\n';
    return 0;
}

序列分块套值域分块

先来个简单问题：全局 kth。

权值线段树很好维护对吧，线段树上二分即可。

考虑值域分块怎么做。

事实上是类似的。枚举整块，如果超了就枚举块内。

复杂度

那现在加强一下：区间 kth。

【模板】可持久化线段树 2

主席树可以做，那分块呢？

在学值域分块前，我的第一想法是序列分块+二分。

然而复杂度是

能不能把 去掉呢？

我们考虑序列分块套值域分块。

这种值域类数据结构都有非常好的性质：单调性。

我们先对序列分块，维护块内每个数的出现次数。

然后对值域分块，维护每个序列块内每个值域块中数的出现次数。

然后对序列块做上面两个信息的前缀和，这样就可以 查询一段块内每个数的出现次数以及每个值域块中数的出现次数。

这个预处理的复杂度是 的。

查询时，我们先把散块里的元素放到一个桶里，再把值域块中的数放到一个桶里。

然后跳值域块，超过 时就跳块内的数。

复杂度

代码实现里序列块和值域块共用了块长和所有编号，请分清哪个是序列块，哪个是值域块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e5+10,maxm=500;
int n,m,siz,tot;
int a[maxn],b[maxn];
int st[maxm],ed[maxm],bel[maxn];
int cnt1[maxm][maxn],cnt2[maxm][maxm];
int buc1[maxn],buc2[maxm];
inline void init(){
    siz=sqrt(n);
    tot=n/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<n) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=n;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void pre(){
    for(re int i=1;i<=tot;++i){
        for(re int j=1;j<=n;++j) cnt1[i][j]=cnt1[i-1][j];
        for(re int j=1;j<=tot;++j) cnt2[i][j]=cnt2[i-1][j];
        for(re int j=st[i];j<=ed[i];++j) ++cnt1[i][a[j]],++cnt2[i][bel[a[j]]];
    }
}
inline int query(int l,int r,int k){
    int L=bel[l],R=bel[r],res=-1,tmp=0,id=0;
    if(L==R){
        for(re int i=l;i<=r;++i) ++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=1;i<=tot;++i){
            tmp+=buc2[i];
            if(tmp>=k){
                tmp-=buc2[i];
                id=i;
                break;
            }
        }
        for(re int i=st[id];i<=ed[id];++i){
            tmp+=buc1[i];
            if(tmp>=k){
                res=b[i];
                break;
            }
        }
        for(re int i=l;i<=r;++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
    }
    else{
        for(re int i=l;i<=ed[L];++i) ++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=st[R];i<=r;++i) ++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=1;i<=tot;++i){
            tmp+=buc2[i]+cnt2[R-1][i]-cnt2[L][i];
            if(tmp>=k){
                tmp-=buc2[i]+cnt2[R-1][i]-cnt2[L][i];
                id=i;
                break;
            }
        }
        for(re int i=st[id];i<=ed[id];++i){
            tmp+=buc1[i]+cnt1[R-1][i]-cnt1[L][i];
            if(tmp>=k){
                res=b[i];
                break;
            }
        }
        for(re int i=l;i<=ed[L];++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
        for(re int i=st[R];i<=r;++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
    }
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif	
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-(b+1);
    for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    init();
    pre();
    for(re int i=1,l,r,k;i<=m;++i){
        cin>>l>>r>>k;
        cout<<query(l,r,k)<<'\n';
    }
    return 0;
}

那再加强一下：单点修。

Dynamic Rankings

因为我们预处理的是前缀和，所以要更改 的块。

代码基本相同。

但如果你还把两种块的编号并用，请注意元素个数可能会 。

代码里的 n=cnt 就是解决这一情况的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include"bits/stdc++.h"
#define re register
// #define int long long
using namespace std;
const int maxn=2e5+10,maxm=500;
int n,m,siz,tot,cnt;
int a[maxn],b[maxn];
int st[maxm],ed[maxm],bel[maxn];
int cnt1[maxm][maxn],cnt2[maxm][maxm];
int buc1[maxn],buc2[maxm];
struct query{
    int op;
    int l,r,k;
    int x,y;
}q[maxn];
inline void init(){
    n=cnt;
    siz=sqrt(n);
    tot=n/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<n) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=n;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void pre(){
    for(re int i=1;i<=tot;++i){
        for(re int j=1;j<=n;++j) cnt1[i][j]=cnt1[i-1][j];
        for(re int j=1;j<=tot;++j) cnt2[i][j]=cnt2[i-1][j];
        for(re int j=st[i];j<=ed[i];++j) ++cnt1[i][a[j]],++cnt2[i][bel[a[j]]];
    }
}
inline void modify(int x,int y){
    int pos=bel[x];
    for(re int i=pos;i<=tot;++i){
        --cnt1[i][a[x]];
        --cnt2[i][bel[a[x]]];
        ++cnt1[i][y];
        ++cnt2[i][bel[y]];
    }
    a[x]=y;
}
inline int query(int l,int r,int k){
    int L=bel[l],R=bel[r],res=-1,tmp=0,id=0;
    if(L==R){
        for(re int i=l;i<=r;++i) ++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=1;i<=tot;++i){
            tmp+=buc2[i];
            if(tmp>=k){
                tmp-=buc2[i];
                id=i;
                break;
            }
        }
        for(re int i=st[id];i<=ed[id];++i){
            tmp+=buc1[i];
            if(tmp>=k){
                res=b[i];
                break;
            }
        }
        for(re int i=l;i<=r;++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
    }
    else{
        for(re int i=l;i<=ed[L];++i) ++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=st[R];i<=r;++i) ++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=1;i<=tot;++i){
            tmp+=buc2[i]+cnt2[R-1][i]-cnt2[L][i];
            if(tmp>=k){
                tmp-=buc2[i]+cnt2[R-1][i]-cnt2[L][i];
                id=i;
                break;
            }
        }
        for(re int i=st[id];i<=ed[id];++i){
            tmp+=buc1[i]+cnt1[R-1][i]-cnt1[L][i];
            if(tmp>=k){
                res=b[i];
                break;
            }
        }
        for(re int i=l;i<=ed[L];++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
        for(re int i=st[R];i<=r;++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
    }
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif	
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i],b[++cnt]=a[i];
    char op;
    for(re int i=1;i<=m;++i){
        cin>>op;
        if(op=='Q') cin>>q[i].l>>q[i].r>>q[i].k,q[i].op=1;
        else cin>>q[i].x>>q[i].y,q[i].op=2,b[++cnt]=q[i].y;
    }
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-(b+1);
    for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    init();
    pre();
    for(re int i=1;i<=m;++i){
        if(q[i].op==1) cout<<query(q[i].l,q[i].r,q[i].k)<<'\n';
        else modify(q[i].x,lower_bound(b+1,b+cnt+1,q[i].y)-b);
    }
    return 0;
}

那再加强一下：区间修。

[Ynoi2018] 未来日记

望月悲叹的最初分块。

每个序列块用并查集把所有值相同的缩在一起。然后维护 rt[i][x]，表示第 个块中某个值为 的数的位置。

对于整块修改，如果 不存在，直接无视。

否则，如果 不存在，那么就把 映射成 。

否则暴力重构。

然后还要把我们维护的前缀和修改掉。

因为是区间修，所以我们还得再记录一下每个序列块内每个数的出现次数，用于修改后面的前缀和。

对于散块修改，直接暴力重构即可。

具体的，我们把并查集的信息全部重新维护一遍，然后再把后面块的前缀和修改一下。

感觉说的也不是很清楚？那放一下lxl的题解吧。

实现参考了题解（我太菜了写不出来QWQ）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include"bits/stdc++.h"
#define re register
// #define int long long
using namespace std;
const int maxn=1e5+10,maxm=170;
int n,m,siz,tot;
int a[maxn];
int st[maxm],ed[maxm],bel[maxn];
int cnt1[maxm][maxn],cnt2[maxm][maxm],cnt3[maxm][maxn];
int buc1[maxn],buc2[maxm];
int fa[maxn],rt[maxm][maxn];
int stk[maxn];
inline int find(int x){if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];}
inline void init(){
    siz=600;
    tot=n/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<n) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=n;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void pre(){
    for(re int i=1;i<=tot;++i){
        for(re int j=st[i];j<=ed[i];++j){
            if(!rt[i][a[j]]) rt[i][a[j]]=j; 
            else fa[j]=rt[i][a[j]];
        }
        for(re int j=1;j<=n;++j) cnt1[i][j]=cnt1[i-1][j];
        for(re int j=1;j<=tot;++j) cnt2[i][j]=cnt2[i-1][j];
        for(re int j=st[i];j<=ed[i];++j) ++cnt1[i][a[j]],++cnt2[i][bel[a[j]]],++cnt3[i][a[j]];
    }
}
inline void update(int p,int l,int r,int x,int y){
    int tmp=0,top=0,L=st[p],R=ed[p];
    rt[p][x]=rt[p][y]=0;
    for(re int i=L;i<=R;++i){
        a[i]=a[find(i)];
        if(a[i]==x||a[i]==y) stk[++top]=i;
    }
    for(re int i=l;i<=r;++i) if(a[i]==x) a[i]=y,++tmp;
    for(re int i=1;i<=top;++i) fa[stk[i]]=stk[i];
    for(re int i=1;i<=top;++i){
        if(!rt[p][a[stk[i]]]) rt[p][a[stk[i]]]=stk[i];
        else fa[stk[i]]=rt[p][a[stk[i]]];
    }
    cnt3[p][x]-=tmp,cnt3[p][y]+=tmp;
    for(re int i=p;i<=tot;++i){
        cnt1[i][x]-=tmp,cnt1[i][y]+=tmp;
        if(bel[x]!=bel[y]) cnt2[i][bel[x]]-=tmp,cnt2[i][bel[y]]+=tmp;
    }
}
inline void modify(int l,int r,int x,int y){
    if(x==y) return;
    int L=bel[l],R=bel[r];
    if(L==R) update(L,l,r,x,y);
    else{
        update(L,l,ed[L],x,y),update(R,st[R],r,x,y);
        int tmp1=0,tmp2=0;
        for(re int i=L+1;i<=R-1;++i){
            if(rt[i][x]){
                if(!rt[i][y]) rt[i][y]=rt[i][x],a[rt[i][x]]=y;
                else fa[rt[i][x]]=rt[i][y];
                rt[i][x]=0;
                tmp1=cnt3[i][x],tmp2+=tmp1;
                cnt3[i][y]+=tmp1,cnt3[i][x]=0;
            }
            cnt1[i][x]-=tmp2,cnt1[i][y]+=tmp2;
            if(bel[x]!=bel[y]) cnt2[i][bel[x]]-=tmp2,cnt2[i][bel[y]]+=tmp2;
        }
        for(re int i=R;i<=tot;++i){
            cnt1[i][x]-=tmp2,cnt1[i][y]+=tmp2;
            if(bel[x]!=bel[y]) cnt2[i][bel[x]]-=tmp2,cnt2[i][bel[y]]+=tmp2;
        }
    }
}
inline int query(int l,int r,int k){
    int L=bel[l],R=bel[r],res=-1,tmp=0,id=0;
    if(L==R){
        for(re int i=l;i<=r;++i) a[i]=a[find(i)],++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=1;i<=tot;++i){
            tmp+=buc2[i];
            if(tmp>=k){
                tmp-=buc2[i];
                id=i;
                break;
            }
        }
        for(re int i=st[id];i<=ed[id];++i){
            tmp+=buc1[i];
            if(tmp>=k){
                res=i;
                break;
            }
        }
        for(re int i=l;i<=r;++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
    }
    else{
        for(re int i=l;i<=ed[L];++i) a[i]=a[find(i)],++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=st[R];i<=r;++i) a[i]=a[find(i)],++buc1[a[i]],++buc2[bel[a[i]]];
        for(re int i=1;i<=tot;++i){
            tmp+=buc2[i]+cnt2[R-1][i]-cnt2[L][i];
            if(tmp>=k){
                tmp-=buc2[i]+cnt2[R-1][i]-cnt2[L][i];
                id=i;
                break;
            }
        }
        for(re int i=st[id];i<=ed[id];++i){
            tmp+=buc1[i]+cnt1[R-1][i]-cnt1[L][i];
            if(tmp>=k){
                res=i;
                break;
            }
        }
        for(re int i=l;i<=ed[L];++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
        for(re int i=st[R];i<=r;++i) buc1[a[i]]=0,buc2[bel[a[i]]]=0;
    }
    return res;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif	
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i],fa[i]=i;
    init();
    pre();
    for(re int i=1,op,l,r,x,y,k;i<=m;++i){
        cin>>op;
        if(op==1) cin>>l>>r>>x>>y,modify(l,r,x,y);
        else cin>>l>>r>>k,cout<<query(l,r,k)<<'\n';
    }
    return 0;
}

事实上这东西和主席树很像，都是维护前缀信息，然后通过差分求区间信息。

一般来说，我们都会维护前缀序列块的某个值域块的前缀和，这样可以方便修改。

有时候，我们还会维护前缀序列块的前缀值域块的前缀和。

例如[ABC339G] Smaller Sum，我们维护前缀序列块的前缀值域块的前缀和。

在序列上，我们把询问差分成 ，然后因为我们还维护了前缀值域块的前缀和，所以 的和也直接求出来了。

倍增值域分块

倍增值域分块，就是把值域分成 的形式，一般取 。

通常用来解决 的操作。

常见做法是每块建一颗线段树维护。

Phoenix and Diamonds *3400

考虑倍增值域分块。

我们把值域按 分块。

设 当前在的块是 ，那么 有三种情况：，，。

最后一种情况显然不需要考虑。

如果选了第二种情况，那么 就会向下掉一层。

如果选了第一种情况，那么也有两种情况：一直选，然后掉到下一层；或者直接选完。

考虑对每一块开一颗线段树维护。

线段树上维护 的 和 ，以及选一个 所需的 的最小值（别忘了拿 的条件是先把前面拿完）。

查询就是线段树上二分。

还有另一种写法，不过差不多。

线段树上每个节点维护所有块信息，维护的东西不变。

设 ， 为上文提到的 的最小值。

那么查询时，如果 ，那么说明小物品都能拿，那么直接返回 。

如果 ，说明比 所在层的下一层还要小的物品可以全拿（拿完以后可能掉下去也可能不掉下去），但是下一层的物品一个也拿不了，那么直接返回 。

否则向两边递归。可以证明复杂度为 。

感性理解就是每次递归都至少往下走一层，最多走 层。

复杂度

实现时，查询里要实时维护当前在哪一层。

代码实现了第二种（感觉线段树上二分不太好写）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e5+10,maxv=20,inf=2e18;
int n,m,c,rt,segcnt,now;
int seq[maxn],id[maxn];
struct node{
    int num,w,v,id;
}a[maxn];
struct node1{
    int sw,sv,tot;
};
struct tree{
    int ls,rs;
    node1 s[maxv];
}tr[maxn<<1];
inline bool cmp(int x,int y){
    if(a[x].v==a[y].v) return a[x].w<a[y].w;
    return a[x].v>a[y].v;
}
inline void up(int p){
    for(re int i=1;i<=18;++i){
        tr[p].s[i].sw=tr[tr[p].ls].s[i].sw+tr[tr[p].rs].s[i].sw;
        tr[p].s[i].sv=tr[tr[p].ls].s[i].sv+tr[tr[p].rs].s[i].sv;
        tr[p].s[i].tot=min(tr[tr[p].ls].s[i].tot,tr[tr[p].ls].s[i].sw+tr[tr[p].rs].s[i].tot);
    }
}
inline void init(int p,int pos){
    for(re int i=1;i<=18;++i){
        tr[p].s[i].sw=tr[p].s[i].sv=0,tr[p].s[i].tot=inf;
        if(a[pos].w<(1<<(i-1))) tr[p].s[i].sw=a[pos].w*a[pos].num,tr[p].s[i].sv=a[pos].v*a[pos].num;
        else if(a[pos].w<(1<<i)&&a[pos].num) tr[p].s[i].tot=a[pos].w; 
    }
}
inline void build(int l,int r,int &p){
    if(!p) p=++segcnt;
    if(l==r){init(p,id[l]);return;}
    int mid=(l+r)>>1;
    build(l,mid,tr[p].ls),build(mid+1,r,tr[p].rs);
    up(p);
}
inline void update(int l,int r,int pos,int p){
    if(l==r){init(p,id[pos]);return;}
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,pos,tr[p].ls);
    else update(mid+1,r,pos,tr[p].rs);
    up(p);
}
inline void calc(){while(now>1&&(1<<((now-1)-1))>c) --now;}
inline int query(int l,int r,int p){
    if(l==r){
        int num=min(a[id[l]].num,c/a[id[l]].w);
        c-=num*a[id[l]].w;calc();
        return num*a[id[l]].v;
    }
    if(c>=tr[p].s[now].sw){int tmp=tr[p].s[now].sv;c-=tr[p].s[now].sw,calc();return tmp;}
    else if(c>=tr[p].s[now-1].sw&&c<tr[p].s[now-1].tot){int tmp=tr[p].s[now-1].sv;c-=tr[p].s[now-1].sw,calc();return tmp;}
    else{
        int mid=(l+r)>>1;
        return query(l,mid,tr[p].ls)+query(mid+1,r,tr[p].rs);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1;i<=n;++i) cin>>a[i].num>>a[i].w>>a[i].v,id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(re int i=1;i<=n;++i) seq[id[i]]=i;
    build(1,n,rt);
    while(m--){
        int op,num,pos;
        cin>>op;
        if(op==3){
            cin>>c;now=18;calc();
            cout<<query(1,n,1)<<'\n';
        }
        else{
            cin>>num>>pos;
            if(op==1) a[pos].num+=num;
            else a[pos].num-=num;
            update(1,n,seq[pos],1);
        }
    }
    return 0;
}
[Ynoi2007] rgxsxrs

摆

[Ynoi Easy Round 2022] 堕天作战 TEST_98

摆

≡