XCPC Notes

Appearance

发布时间：2024-08-09

莫队 ​

基础 ​

  • 分块
  • 多关键字排序
  • 倍增树剖lca(树上莫队)
  • 数值离散化

HH的项链(SPOJ3267) ​

题意：
给定长度为n的序列，m次询问，每次询问一个区间有多少种不同的数
思路：

  • 树状数组：离线下来，然后只维护最后出现的数，前缀和查询即可
  • 主席树：在线询问，一样的思路维护最后出现的数，查询右端点对应的版本的[l,r]即可

莫队 ​

  • 离线询问
  • 首先考虑暴力怎么做
    • 对于每次询问，移动左右指针，开一个桶记录数的出现次数，复杂度: O(nm)O(nm)
  • 分块，然后区间如果左端点块编号不同，则按右端点排序，否则按左端点对应块编号排序
  • 假设块长为 BB ,对于同一个块内右端点最多移动 nn 次,有 nB\frac{n}{B} 个,复杂度为 O(n2B)O(\frac{n^2}{B})
  • 对于块编号相同的左端点，最多移动次数为 BB 次, mm 次询问,因此最多移动次数为 mBmB
  • 对于块编号不同的左端点块间距离为 2B2B,一共 移动 2B⋅nB=2n2B \cdot \frac{n}{B}=2n 次
  • 一般 BB 取 n\sqrt n 即可,此处让 n2B=mB即B=n2m\frac{n^2}{B}=mB 即B=\sqrt \frac{n^2}{m}
cpp
struct Node{
    int id,l,r;
};
int cnt[N],w[M];
int be[M],L[M],R[M],tot,block,res;
bool cmp(Node x,Node y){
    return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.l]&1)?x.r<y.r:x.r>y.r);
    //奇数块从小到大，偶数块相反
}
void add(int x){
    if(!(cnt[w[x]]++))res++;
}
void del(int x){
    if(!(--cnt[w[x]]))res--;
}
void solve(){
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    cin>>m;
    vector<Node> q(m);
    vector<int> ans(m);
    for(int i=0;i<m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
    block=sqrt((double)n*n/m),tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){
        int l=(i-1)*block+1,r=min(i*block,n);
        for(int j=l;j<=r;j++)be[j]=i;
    }
    sort(q.begin(),q.end(),cmp);
    for(int k=0,l=1,r=0;k<m;k++){
        auto [id,ql,qr]=q[k];
        while(r<qr)add(++r);
        while(r>qr)del(r--);
        while(l<ql)del(l++);
        while(l>ql)add(--l);
        ans[id]=res;
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}

P1903 [国家集训队] 数颜色 / 维护队列(带修莫队) ​

题意：
原来的基础上，加上修改某个数的操作
思路：

  • 二关键字变三关键字
  • 首先按l的块编号排序，再按r的块编号排序，最后按修改版本t排序
  • 对于l指针,块内移动为 BB,总次数为 mBmB,块间移动为 2⋅B⋅nB=2n2 \cdot B \cdot \frac{n}{B}=2n,总复杂度为 O(mB+n)O(mB+n)
  • 对于r指针,块内移动为 mBmB,块间移动为 n2B\frac{n^2}{B}
  • 对于t指针，移动次数为 n2B2t\frac{n^2}{B^2}t
  • dalao证明 B=nt3B= \sqrt[3] {nt} 最优
  • 块长取 n23比nn^{\frac{2}{3}} 比 \sqrt n 更优，总复杂度为 O(n53)O(n^{\frac{5}{3}})
  • 修改操作优化，将原数组的数与修改数交换即可
cpp
struct Node{
    int id,l,r,t;
};
int cnt[N],w[M];
int be[M],L[M],R[M],tot,block,res;
bool cmp(Node x,Node y){
    return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.r]^be[y.r]?be[x.r]<be[y.r]:x.t<y.t));
}
void add(int x){
    if(!(cnt[x]++))res++;
}
void del(int x){
    if(!(--cnt[x]))res--;
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    vector<Node> q;
    vector<array<int,2>> c={{0,0}};
    int que=0;
    for(int i=0;i<m;i++){
        char op;
        int x,y;
        cin>>op>>x>>y;
        if(op=='Q'){
            q.push_back({que++,x,y,c.size()-1});
        }
        else{
            c.push_back({x,y});
        }
    }
    vector<int> ans(que);
    block=pow(n,2.0/3.0),tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){
        int l=(i-1)*block+1,r=min(i*block,n);
        for(int j=l;j<=r;j++)be[j]=i;
    }
    sort(q.begin(),q.end(),cmp);
    for(int i=0,l=1,r=0,t=0;i<q.size();i++){
        auto [id,ql,qr,qt]=q[i];
        while(r<qr)add(w[++r]);
        while(r>qr)del(w[r--]);
        while(l<ql)del(w[l++]);
        while(l>ql)add(w[--l]);
        while(t<qt){
            t++;
            if(ql<=c[t][0]&&qr>=c[t][0])del(w[c[t][0]]),add(c[t][1]);
            swap(w[c[t][0]],c[t][1]);
        }
        while(t>qt){
            if(ql<=c[t][0]&&qr>=c[t][0])del(w[c[t][0]]),add(c[t][1]);
            swap(w[c[t][0]],c[t][1]);
            t--;
        }
        ans[id]=res;
    }
    for(auto it:ans)cout<<it<<"\n";
}

歴史の研究(回滚莫队) ​

题意：
一个数的重要度为数值*出现次数，每次询问一个区间内的最重要度
思路：

  • 按左端点块编号排序，再按右端点排序
  • 对于左右端点在同一块内的询问，暴力询问 qBqB
  • 对于不在同一块内的区间询问，固定当前右指针为块的右边，因为块内区间右端点升序，因此右指针单调移动，最多为 nn 次，总次数为 n2B\frac{n^2}{B} 次
  • 然后暴力移动左端点，每个块最多为 BB 次，一共 nn 次
  • B取 n2q\sqrt \frac{n^2}{q}
cpp
struct Node{
    int id,l,r;
};
int w[M];
int be[M],L[M],R[M],tot,block;
bool cmp(Node x,Node y){
    return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:x.r<y.r;
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> nums;
    for(int i=1;i<=n;i++)cin>>w[i],nums.push_back(w[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
    vector<int> cnt(nums.size());
    auto add=[&](int x,int &res){
        cnt[x]++;
        res=max(res,cnt[x]*nums[x]);
    };
    vector<int> ans(m+1);
    vector<Node> q(m+1);
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    block=sqrt(1.0*n*n/m),tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1,R[i]=min(i*block,n);
        for(int j=L[i];j<=R[i];j++)be[j]=i;
    }
    sort(q.begin()+1,q.end(),cmp);
    for(int i=1,j;i<=m;i++){
        j=i;
        int right=R[be[q[i].l]];
        while(j+1<=m&&be[q[i].l]==be[q[j+1].l])j++;
        while(i<=j&&q[i].r<=right){
            //左右端点在同一块
            auto [id,ql,qr]=q[i++];
            int res=0;
            for(int k=ql;k<=qr;k++)add(w[k],res);
            ans[id]=res;
            for(int k=ql;k<=qr;k++)cnt[w[k]]--;//复原
        }
        int l=right+1,r=right;
        int res=0;
        while(i<=j){
            auto [id,ql,qr]=q[i++];
            while(r<qr)add(w[++r],res);
            int backup=res;
            while(l>ql)add(w[--l],res);
            ans[id]=res;
            res=backup;
            while(l<right+1)cnt[w[l++]]--;
        }
        while(r>right)cnt[w[r--]]--;
        i=j;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}

P5906 【模板】回滚莫队&不删除莫队 ​

题意：
询问区间内最大的相同数之间的间距
思路：

  • 回滚莫队一样的套路
  • 注意：维护mx，mn数组，使用栈还原
cpp
int be[M],L[M],R[M],block,tot;
struct Q{
    int id,l,r;
};
bool cmp(Q &x,Q &y){
    return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:x.r<y.r;
}
void solve(){
    int n;
    cin>>n;
    vector<int> nums,w(n+1);
    for(int i=1;i<=n;i++)cin>>w[i],nums.push_back(w[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
    vector<int> mx(nums.size()),mn(nums.size());
    int m;
    cin>>m;
    vector<Q> q;
    vector<int> ans(m);
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        q.push_back({i,l,r});
    }
    block=sqrt(n),tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*block+1,R[i]=min(n,i*block);
        for(int j=L[i];j<=R[i];j++)be[j]=i;
    }
    sort(q.begin(),q.end(),cmp);
    vector<array<int,3>> st;
    auto add=[&](int x,int &res){
        st.push_back({w[x],mn[w[x]],mx[w[x]]});
        if(!mx[w[x]])mx[w[x]]=mn[w[x]]=x;
        else mx[w[x]]=max(mx[w[x]],x),mn[w[x]]=min(mn[w[x]],x);
        res=max(res,mx[w[x]]-mn[w[x]]);
    };
    auto del=[&](){
        auto [val,MN,MX]=st.back();
        st.pop_back();
        mn[val]=MN,mx[val]=MX;
    };
    for(int i=0,j;i<m;i++){
        j=i;
        while(j+1<m&&be[q[j].l]==be[q[j+1].l])j++;
        int right=R[be[q[i].l]];
        while(i<=j&&q[i].r<=right){
            auto [id,ql,qr]=q[i++];
            int res=0;
            for(int k=ql;k<=qr;k++)add(k,res);
            ans[id]=res;
            while(st.size())del();   
        }
        int res=0,l=right+1,r=right;
        while(i<=j){
            auto [id,ql,qr]=q[i++];
            while(r<qr)add(++r,res);
            int backup=res;
            while(l>ql)add(--l,res);
            ans[id]=res;
            res=backup;
            while(l<right+1)l++,del();
        }
        while(st.size())del();
        i=j;
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}

SP10707树上计数2(树上莫队板子) ​

题意：
给定一颗树，每次询问u，v的简单路径上，有多少种颜色
思路：

  • 树上问题转序列问题
  • 首先获取欧拉序，即dfs序，不过回溯的时候也要加进序列,每个点出现两次
  • 对于每个点给一个 firsti表示第一次出现，lasti表示第二次出现first_i表示第一次出现，last_i表示第二次出现
  • 假设 firstx<firstyfirst_x<first_y
    • 如果lca(x,y)=x那么路径出现的点数为 [firstx,firsty][first_x,first_y] 出现一次的点
    • 否则为 [lastx,firsty][last_x,first_y] 出现一次的点，加上lca
cpp
int be[M],block,tot;
vector<int> adj[M];
int w[M],cnt[M];
int first[M],last[M],seq[M],top,dep[M],par[M][20];
bool st[M];
struct Q{
    int id,l,r,p;
};
bool cmp(Q &x,Q &y){
    return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.l]&1)?x.r<y.r:x.r>y.r);
}
void dfs(int u,int fa){
    seq[++top]=u;
    first[u]=top;
    dep[u]=dep[fa]+1;
    par[u][0]=fa;
    for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    seq[++top]=u;
    last[u]=top;
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    while(dep[u]>dep[v])u=par[u][__lg(dep[u]-dep[v])];
    if(u==v)return u;
    for(int i=__lg(dep[u]);i>=0;i--){
        if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
    }
    return par[u][0];
}
void add(int x,int &res){
    st[x]^=1;
    if(!st[x]){
        if(!(--cnt[w[x]]))res--;
    }
    else{
        if(!(cnt[w[x]]++))res++;
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> nums;
    for(int i=1;i<=n;i++)cin>>w[i],nums.push_back(w[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> ans(m);
    dfs(1,0);
    vector<Q> q;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        if(first[u]>first[v])swap(u,v);
        int p=lca(u,v);
        if(p==u)q.push_back({i,first[u],first[v],0});
        else q.push_back({i,last[u],first[v],p});
    }
    block=sqrt(1.0*top*top/m),tot=(top+block-1)/block;
    for(int i=1;i<=tot;i++){
        int l=(i-1)*block+1,r=min(top,i*block);
        for(int j=l;j<=r;j++)be[j]=i;
    }
    sort(q.begin(),q.end(),cmp);
    int res=0;
    for(int i=0,l=1,r=0;i<m;i++){
        auto [id,ql,qr,p]=q[i];
        while(r<qr)add(seq[++r],res);
        while(r>qr)add(seq[r--],res);
        while(l<ql)add(seq[l++],res);
        while(l>ql)add(seq[--l],res);
        if(p)add(p,res);
        ans[id]=res;
        if(p)add(p,res);
    }
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}

P4887 【模板】莫队二次离线（第十四分块(前体)） ​

题意：
询问区间内最多有几对数，异或起来恰好有k个1
思路：

  • 莫队离线移动为 O(nn)O( n \sqrt n )
  • 数值最多为 2142^{14} ,即最多有14个1，可以暴力枚举
  • 定义 fif_i 表示 1到i−1有多少个数与i+1配对1到i-1有多少个数与i+1配对
  • 定义 gig_i 表示 能与i配对的数的数量,fi=gwi能与i配对的数的数量 ,f_i=g_{w_i}
  • 可以暴力计算 ff
  • 原区间为 l,rl,r
  • 假设 r<qrr<qr,那么假设前缀和 SiS_i 表示 1到i与wr配对的数1到i与 w_r配对的数 ,那么 res+=Sr+1−Sl−1=fr−Sl−1res+=S_{r+1}-S_{l-1}=f_r-S_{l-1},对于区间 [r+1,qr]都要算一遍对应的Sl−1[r+1,qr] 都要算一遍对应的S_{l-1}，这个是不能直接算的需要离线下来算，即二次离线
  • 同理，有以下
  • r>qr,res−=Sr−Sl−1=fr−1−Sl−1,对于所有区间r∈[qr+1,r]r>qr ,res-=S_{r}-S_{l-1}=f_{r-1}-S_{l-1},对于所有区间r∈[qr+1,r]
  • l<ql,res−=Sr−Sl−1=Sr−(fl−1+!k),对于所有l∈[l,ql−1]l<ql,res-=S_r-S{l-1}=S_r-(f_{l-1}+!k),对于所有l∈[l,ql-1]
  • l>ql,res+=Sr−Sl−2=Sr−(fl−2+!k),对于所有l∈[ql,l−1]l>ql,res+=S_r-S_{l-2}=S_r-(f_{l-2}+!k),对于所有l∈[ql,l-1]
  • 对于离线下来的range暴力求，本质上是移动l，r指针的贡献，为 nnn \sqrt n
  • 最后再进行累加，因为求的是相对变化
cpp
int be[M],block,tot;
struct Q{
    int id,l,r,res;
};
struct Range{
    int i,l,r,p;
};
bool cmp(Q &x,Q &y){
    return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.l]&1)?x.r<y.r:x.r>y.r);
}
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int> w(n+10),f(n+10),g(2e4);
    for(int i=1;i<=n;i++)cin>>w[i];
    vector<Q> q;
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        q.push_back({i,l,r,0});
    }
    if(k>14){
        for(int i=0;i<m;i++)cout<<"0\n";
        return;
    }
    block=sqrt(n),tot=(n+block-1)/block;
    for(int i=1;i<=tot;i++){
        int l=(i-1)*block+1,r=min(n,i*block);
        for(int j=l;j<=r;j++)be[j]=i;
    }
    sort(q.begin(),q.end(),cmp);
    vector<int> nums;
    for(int i=0;i<1<<14;i++){
        if(__builtin_popcount(i)==k)nums.push_back(i);
    }
    for(int i=1;i<=n;i++){
        for(auto it:nums)g[w[i]^it]++;
        f[i]=g[w[i+1]];
    }
    vector<Range> range[n+1];
    for(int i=0,l=1,r=0;i<m;i++){
        auto &[id,ql,qr,res]=q[i];
        if(r<qr)range[l-1].push_back({i,r+1,qr,-1});
        while(r<qr)res+=f[r++];
        if(r>qr)range[l-1].push_back({i,qr+1,r,1});
        while(r>qr)res-=f[--r];
        if(l<ql)range[r].push_back({i,l,ql-1,-1});
        while(l<ql)res+=f[l-1]+!k,l++;
        if(l>ql)range[r].push_back({i,ql,l-1,1});
        while(l>ql)res-=f[l-2]+!k,l--;
    }
    g.assign(2e4,0);
    for(int i=1;i<=n;i++){
        for(auto it:nums)g[w[i]^it]++;
        for(auto [id,l,r,p]:range[i]){
            for(int x=l;x<=r;x++)q[id].res+=g[w[x]]*p;
        }
    }
    vector<int> ans(m);
    for(int i=1;i<m;i++)q[i].res+=q[i-1].res;
    for(int i=0;i<m;i++)ans[q[i].id]=q[i].res;
    for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}

Wenwei Lin · 2022 — 2025