题解 CF848C 【Goodbye Souvenir】

· · 题解

\large \color{purple} My\;Blog

我这题共写了四种做法，其中两种可以通过。感兴趣的可以去博客里面看，这里仅给出正解。

思路

考虑最后的减去开始的等价于每一位减去前面的。

即位置x对[l,r]的贡献是x-pre_x,pre_x\geq l。

那么题目转化为二维数点：一维是位置x，一维是前驱pre_x，权值是x-pre_x。

当pre_x发生改变时消除原来的贡献，并加上新的。

询问可以变为查询以(l,l)为左下角，(r,n)为右上角的矩形之和。按照时间CDQ分治，每次算左边的点对右边的矩形的贡献。

然而这个矩形不好看，似乎还要差分？

其实并不用。考虑x>pre_x，所以直线y=x上方是没有点的，可以把查询变成以(1,l)为左下角，(r,n)为右上角的矩形。这样可以扫描线+树状数组了。

时间复杂度应该是O(n\log^2 n)。

代码

#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define pii pair<int,int>
    #define fir first
    #define sec second
    #define MP make_pair
    #define rep(i,x,y) for (int i=(x);i<=(y);i++)
    #define drep(i,x,y) for (int i=(x);i>=(y);i--)
    #define go(x) for (int i=head[x];i;i=edge[i].nxt)
    #define sz 101010
    typedef long long ll;
    template<typename T>
    inline void read(T& t)
    {
        t=0;char f=0,ch=getchar();
        double d=0.1;
        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
        if(ch=='.')
        {
            ch=getchar();
            while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
        }
        t=(f?-t:t);
    }
    template<typename T,typename... Args>
    inline void read(T& t,Args&... args){read(t); read(args...);}
    void file()
    {
        #ifndef ONLINE_JUDGE
        freopen("a.txt","r",stdin);
        #endif
    }
//  inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n,m,Q;
int a[sz];
int pre[sz],nxt[sz];
set<int>s[sz];

int calcPre(int x,int col){set<int>::iterator it=s[col].lower_bound(x);--it;return *it;}
int calcNxt(int x,int col){return *(s[col].upper_bound(x));}

ll ans[sz];
struct hh
{
    int type; // 0:modify 1:query
    int x,y,val;
    int id;
}q[sz*6];
inline bool cmp(const hh &x,const hh &y)
{
    if (x.type!=y.type) return x.type<y.type;
    if (x.type) return x.y<y.y;
    return x.x<y.x;
}
inline void calc(int x,int v) // pre[x]->v
{
    q[++m]=(hh){0,x,pre[x],pre[x]-x,0};
    pre[x]=v;
    q[++m]=(hh){0,x,v,x-v,0};
}

ll sum[sz];
void add(int x,ll v){ if (!x) return; while (x<=n) sum[x]+=v,x+=(x&(-x)); }
ll query(int x){ ll ret=0; while (x) ret+=sum[x],x-=(x&(-x)); return ret; }

void solve(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    int p=l-1;
    rep(i,mid+1,r) if (q[i].type)
    {
        while (p<mid&&(q[p+1].type||q[p+1].x<=q[i].y))
        {
            ++p;
            if (!q[p].type) add(q[p].y,q[p].val);
        }
        ans[q[i].id]+=query(n)-query(q[i].x-1);
    }
    rep(i,l,p) if (!q[i].type) add(q[i].y,-q[i].val);
    sort(q+l,q+r+1,cmp);
}

int main()
{
    file();
    int x,y,z;
    read(n,Q);
    rep(i,1,n) s[i].insert(0),s[i].insert(n+1);
    rep(i,1,n) read(a[i]),s[a[i]].insert(i);
    rep(i,1,n) pre[i]=calcPre(i,a[i]),nxt[i]=calcNxt(i,a[i]),q[++m]=(hh){0,i,pre[i],i-pre[i],0};
    int c=0;
    while (Q--)
    {
        read(z,x,y);
        if (z==1)
        {
            if (y==a[x]) continue;
            int Pre=calcPre(x,y),Nxt=calcNxt(x,y);
            s[a[x]].erase(x);s[y].insert(x);
            a[x]=y;
            if (nxt[x]!=n+1) calc(nxt[x],pre[x]);
            if (pre[x]!=0) nxt[pre[x]]=nxt[x];
            if (Pre!=0) nxt[Pre]=x;
            if (Nxt!=n+1) calc(Nxt,x);
            calc(x,Pre);
            nxt[x]=Nxt;
        }
        else ++c,q[++m]=(hh){1,x,y,0,c};
    }
    solve(1,m);
    rep(i,1,c) printf("%lld\n",ans[i]);
    return 0;
}