U11讲 笔记

带修改的莫队算法

struct Query{int l,r,t,id;}q[M];
int nQ;
bool cmp(const Query&x,const Query&y){
    if(b[x.l]!=b[y.l])return x.l<y.l;
    if(b[x.r]!=b[y.r])return x.r<y.r;
    return x.t<y.t;
}

q[i].t\rm q[i].t 表示 i\rm i 号问询依赖几次修改。

修改次数可以理解成时间戳

复杂度分析+最优分块大小

序列编号每组大小 BB ，序列共 n/Bn/B 组，平面共 n2/2B2n^2/2B^2

ll 移动 ： 每两个问询间：左端点抖动距离不超过 BB ，左端点抖动总距离不超过 mBmB

rr 移动 ： 块内每两个问询间：右端点抖动距离不超过 BB ，右端点抖动总距离不超过 mBmB ，跨越块列时总距离： nB∗n2\frac{n}{B}*\frac{n}{2}

tt 移动 ： 每个块内总距离 ： nn ，所有块总距离 ： n22B2∗n\frac{n^2}{2B^2}*n

总复杂度 ： $2mB+ \frac{n^2}{2B}+ \frac{n^3}{2B^2} \ge n \sqrt[3]{2m^2} = O(n \sqrt[3]{m^2})$ 额外排序：O(mlog⁡m)\rm O(m \log m)

等号条件 ： $B^3=\frac{n^3}{4m} , \quad B=\frac{n}{\sqrt[3]{4m}}$

例一 KK3170 计数种类 1

题面

题目描述

有一个长度为 nn 的正整数序列，共有 mm 次操作，分为两种

QLRQ \quad L \quad R \quad 代表询问你从第 LL 个数到第 RR 个数中共有几种不同的数字类型。

RPVR \quad P \quad V \quad 把第 PP 个数字替换为数值 VV

程序名 : category.cpp

输入格式 \quad category.in

第一行包含正整数 nn 和 mm 。

接着一行为 nn 个正整数，代表序列的初始值。

然后有 mm 行，每行一条操作指令，保证都合法。

输出格式 \quad category.out

对于每一个问询，输出一行包含一个整数

输入样例

6 5

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Q 1 4

Q 2 6

输出样例

4

4

3

4

数据范围

1≤n,m≤100001 \le n,m \le 10000

序列中元素的数值范围是 11 到 10000001000000

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int M=1e4+10;
const int R=1e6+10;

struct Query{int l,r,t,id;}q[M];
int nQ;
bool cmp(const Query&x,const Query&y){
    if(b[x.l]!=b[y.l])return x.l<y.l;
    if(b[x.r]!=b[y.r])return x.r<y.r;
    return x.t<y.t;
}

struct Update{int p,v1,v2;}upds[M];
int nU;

int n,m,L;

int cnt[R];
int a[N];

int main(){
    freopen("category.in","r",stdin);
    freopen("category.out","w",stdout);
    
    cin>>n>>m;
    L=cbrt(n*n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=(i-1)/L+1;
    }
    
    for(int i=1;i<=m;i++){
        char op;
        int x,y,p,v;
        cin>>op;
        if(op=='Q'){
            ++nQ;
            cin>>q[nQ].l>>q[nQ].r;
            q[nQ].t=nU;
            q[nQ].id=nQ;
        }else{
            ++nU;
            cin>>upds[nU].p>>upds[nU].v2;
            upds[nU].v1=a[upds[nU].p];
            a[upds[nU].p]=upds[nU].v2;
        }
    }
    
    sort(q+1,q+1+nQ,cmp);
    int l=1,r=0;
    int ans=0;
    int t=nU;
    for(int i=1;i<=nQ;i++){
        while(q[i].l>l){
            --cnt[a[l]];
            ans-=(cnt[a[l]]==0);
            l++;
        }
        while(q[i].l<l){
            --l;
            ++cnt[a[l]];
            ans+=(cnt[a[l]]==1);
        }
        while(q[i].r<r){
            --cnt[a[r]];
            ans-=(cnt[a[r]]==0);
            r--;
        }
        while(q[i].r>r){
            ++r;
            ++cnt[a[r]];
            ans+=(cnt[a[r]]==1);
        }
        while(q[i].t>t){
            ++t;
            if(l<=upds[t].p&&upds[t].p<=r){
                --cnt[a[upds[t]].p];
                ans-=(cnt[a[upds[t].p]]==0);
            }
            a[upds[t].p]=upds[t].v2;
            if(l<=upds[t].p&&upds[t].p<=r){
                ++cnt[a[upds[t].p]];
                ans+=(cnt[a[upds[t].p]]==1);
            }
        }
        while(q[i].t<t){
            if(l<=upds[t].p&&upds[t].p<=r){
                --cnt[a[upds[t]].p];
                ans-=(cnt[a[upds[t].p]]==0);
            }
            a[upds[t].p]=upds[t].v1;
            if(l<=upds[t].p&&upds[t].p<=r){
                ++cnt[a[upds[t].p]];
                ans+=(cnt[a[upds[t].p]]==1);
            }
            --t;
        }
        ANS[q[i].id]=ans;
    }
    for(int i=1;i<=nQ;i++)
        cout<<ANS[i]<<endl;
}

封装操作函数

void add(int v){
    ans+=((++cnt[v])==1);
}

void rmv(int v){
    ans-=((--cnt[v])==0);
}

void upd(int iQ,int iU,int tag){
    if(q[iQ].l<=upds[iU].p&&upds[iU].p<=q[iQ].r)
        rmv(a[upds[iU].p]);
    a[upds[iU].p]=(tag==1?upds[iU].v1:upds[iU].v2);
    if(q[iQ].l<=upds[iU].p&&upds[iU].p<=q[iQ].r)
        add(a[upds[iU].p]);
}

封装后的核心代码

sort(q+1,q+1+nQ,cmp);
int l=1,r=0;
int t=nU;
for(int i=1;i<=nQ;i++){
    while(q[i].l>l)rmv(a[l++]);
    while(q[i].l<l)add(a[--l]);
    while(q[i].r<r)rmv(a[r--]);
    while(q[i].r>r)add(a[++r]);
    while(q[i].t>t)upd(i,++t,2);
    while(q[i].t<t)upd(i,t--,1);
    ANS[q[i].id]=ans;
}

简化修改操作

修改只有两种可能：正向修改/反向撤销

且一定是交替发生

struct Update{int p,v;}upds[M];
int nU;

void upd(int iQ,int iU){
    if(q[iQ].l<=upds[iU].p&&upds[iU].p<=q[iQ].r)
        rmv(a[upds[iU].p]);
    swap(a[upds[iU].p],upds[iU].v);
    if(q[iQ].l<=upds[iU].p&&upds[iU].p<=q[iQ].r)
        add(a[upds[iU].p]);
}

for(int i=1;i<=m;i++){
    char op;
    int x,y,p,v;
    cin>>op;
    if(op=='Q'){
        
    }
    else{
        ++nU;
        cin>>upds[nU].p>>upds[nU].v;
    }
}

int t=0;
int l=1,r=0;
int ans=0;
for(int i=1;i<=nQ;i++){
    while(q[i].l>l)rmv(a[l++]);
    while(q[i].l<l)add(a[--l]);
    while(q[i].r<r)rmv(a[r--]);
    while(q[i].r>r)add(a[++r]);
    while(q[i].t>t)upd(i,++t);
    while(q[i].t<t)upd(i,t--);
    ANS[q[i].id]=ans;
}

例二 KK3171 计数种类2

题面

题目描述

有一个长度为 nn 的正整数数列，共有 mm 次操作，分为两种：

1LR1 \quad L \quad R \quad 代表问询你从第 LL 个数到第 RR 个数中出现次数所组成数集的 mex\rm mex 值

2PV2 \quad P \quad V \quad 把第 PP 个数字替换成数值 VV

备注：在这里，一个整数集合的 mex\rm mex 值为最小的不在集合中的正整数

输入格式 \quad classification.in

第一行包含正整数 nn 和 mm 。

接着一行为 nn 个正整数，代表序列的初始值。

然后有 mm 行，每行一条操作指令，保证都合法。

输出格式 \quad classification.out

对于每一个问询，输出一行包含一个整数。

输入样例

10 4

1 2 3 1 1 2 2 2 9 9

1 1 1

1 2 8

2 7 1

1 2 8

输出样例

2

3

2

数据范围

1≤n,m≤500001 \le n,m \le 50000

数值范围是 11 到 10000000001000000000

算法分析

引理

答案范围不超过 O(n)O(\sqrt{n})

证明

假设某一次问询的答案为 xx ，大于 O(n)O(\sqrt{n}) ，那么根据 mex\rm mex 的定义，这段区间中数的个数至少为 $O(\sum_{i=1}^{i<=x} i) > O(\sum_{i=1}^{i<=\sqrt{n}} i) = O(n)$ 但是区间长度不能超过 O(n)O(n) 。因此假设不成立。

因此，答案并不会很大，可以维护一个计数器的计数器数组。

Code

离散化

for(int i=1;i<=n;i++)as[i]=a[i];
for(int i=1;i<=nU;i++)as[i+n]=upds[i].v;
sort(as+1,as+1+n+nU);
for(int i=1;i<=n;i++)
    a[i]=lower_bound(as+1,as+1+n+nU,a[i])-as;
for(int i=1;i<=nU;i++)
    upds[i].v=lower_bound(as+1,as+1+n+nU,upds[i].v)-as;

核心代码

sort(q+1,q+1+nQ,cmp);
int l=1,r=0;
int t=0;
for(int i=1;i<=nQ;i++){
    while(q[i].l>l)rmv(a[l++]);
    while(q[i].l<l)add(a[--l]);
    while(q[i].r<r)rmv(a[r--]);
    while(q[i].r>r)add(a[++r]);
    while(q[i].t>t)upd(i,++t);
    while(q[i].t<t)upd(i,t--);
    for(int c=1;1;c++){
        if(ccnt[c])continue;
        ANS[q[i].id]=c;
        break;
    }
}

三个封装的函数

void add(int v){
    --ccnt[cnt[v]];
    ++cnt[v];
    ++ccnt[cnt[v]];
}

void rmv(int v){
    --ccnt[cnt[v]];
    --cnt[v];
    ++ccnt[cnt[v]];
}

void upd(int iQ,int iU){
    if(q[iQ].l<=upds[iU].p&&upds[iU].p<=q[iQ].r)
        rmv(a[upds[iU].p]);
   	swap(a[upds[iU].p],upds[iU].v);
    if(q[iQ].l<=upds[iU].p&&upds[iU].p<=q[iQ].r)
        add(a[upds[iU].p]);
}

Homework

KK3170,KK3170

讨论

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 19ms
  4. Powered by Hydro v4.14.1 Community