[题解] CF848C Goodbye Souvenir

· · 题解

博客内食用效果更佳

思路：CDQ 分治（三维偏序）

对于给出的一个序列 val，设 pre_i 为上一个值为 val_i 的元素下标，即：

pre_i=\max\left\{j\right\}\quad \left(val_j=val_i,j<i\right)

所以对于 l,r 的询问我们可以转化为：

ans_{l,r}=\sum\limits_{i=l}^r\left(val_i-pre_i\right)\quad \left(pre_i\ge l\right)

显然地，当 pre_i\ge l 时，一定有 i>l，所以答案转化为：

ans_{l,r}=\sum\left(val_i-pre_i\right)\quad \left(pre_i\ge l,i\le r\right)

现在已经有两维度的条件，加上时间维度便是三维条件，所以可以用三维偏序进行求解。

具体实现：

  1. 对于 pre 的维护
    • 采用 set 维护，对于数值 v 来说，我们用 s_v 存储所有 v 出现的位置。
  2. 对于初始序列
    • 只需要加入每个点的贡献，对于第 i 个位置，将 \left(pre_i,i,t\right) 加入 CDQ 中，值为 i-pre_i。
  3. 对于修改操作 \left(a,b,c\right)
    • 将原来的值的贡献减掉：删除 b 对 pre_b 的贡献，删除 nex_b 对 b 的贡献，加入 nex_b 对 pre_b 的贡献。
    • 将 b 从 s_{val_b} 中删除，将 b 加入 s_c，将 val_b 更新为 c。
    • 将新的值的贡献加入，与前面的操作类似。
  4. 对于询问操作 \left(a,b,c\right)
    • 直接将 \left(b,c,t\right) 加入 CDQ 中。

代码实现需要注意的地方：

我的代码采用的是先对 t 排序（本身加入的时候就是有序的），再对 l 排序，将 r 插入树状数组中。

参考代码：

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=1e5+1;

int n,m;
int val[N];
set<int>s[N];
//--------------------//
struct CT//树状数组
{
    LL t[N];
    int lobit(int x){return x&-x;}
    void change(int p,LL val)
    {
        while(p<=n)
            t[p]+=val,p+=lobit(p);
        return;
    }
    LL query(int p)
    {
        LL res=0;
        while(p>0)
            res+=t[p],p-=lobit(p);
        return res;
    }
}T;
//--------------------//
//CDQ
const int NM=1e6+1;
struct CDQ_Node
{
    int l,r,t;
    LL val;
    int type;
}cdq[NM],tem[NM];
int cnt;

int ast;//ast 是询问操作计数
LL ans[N];

void CDQ(int l,int r)
{
    if(l==r)
        return;
    int mid=l+r>>1,p1=l,p2=mid+1;
    CDQ(l,mid);
    CDQ(mid+1,r);
    for(int i=l;i<=r;i++)
    {
        if(p1<=mid&&(p2>r||cdq[p1].l>=cdq[p2].l))//按照 l 大小排序
        {
            if(cdq[p1].type==1)
                T.change(cdq[p1].r,cdq[p1].val);
            tem[i]=cdq[p1++];
        }
        else
        {
            if(cdq[p2].type==2)
                ans[cdq[p2].val]+=T.query(cdq[p2].r);
            tem[i]=cdq[p2++];
        }
    }
    for(int i=l;i<=mid;i++)//回溯
        if(cdq[i].type==1)
            T.change(cdq[i].r,-cdq[i].val);
    for(int i=l;i<=r;i++)
    {
        cdq[i]=tem[i];
    }
    return;
}
//--------------------//
int main()
{
    multiset<int>::iterator it;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        s[val[i]].insert(i);
        it=s[val[i]].find(i);
        if(it!=s[val[i]].begin())//没有前缀则不需要修改
        {
            --it;
            cdq[++cnt]={*it,i,cnt,i-*it,1};
        }
    }
    int a,b,c,last,pre,nex;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(a==1)
        {
            if(val[b]==c)
                continue;

            pre=0,nex=0;
            it=s[val[b]].find(b);
            if(it!=s[val[b]].begin())--it,pre=*it,++it;
            ++it;
            if(it!=s[val[b]].end())nex=*it;
            //删除原先的贡献
            if(pre)cdq[++cnt]={pre,b,cnt,pre-b,1};
            if(nex)cdq[++cnt]={b,nex,cnt,b-nex,1};
            if(pre&&nex)cdq[++cnt]={pre,nex,cnt,nex-pre,1};

            s[val[b]].erase(b);
            val[b]=c;
            s[c].insert(b);

            pre=0,nex=0;
            it=s[c].find(b);
            if(it!=s[c].begin())--it,pre=*it,++it;
            ++it;
            if(it!=s[c].end())nex=*it;
            //添加新的贡献
            if(pre)cdq[++cnt]={pre,b,cnt,b-pre,1};
            if(nex)cdq[++cnt]={b,nex,cnt,nex-b,1};
            if(pre&&nex)cdq[++cnt]={pre,nex,cnt,pre-nex,1};
        }
        else
            cdq[++cnt]={b,c,cnt,++ast,2};
    }
    CDQ(1,cnt);
    for(int i=1;i<=ast;i++)
        printf("%lld\n",ans[i]);
    return 0;
}