[DS记录]CF848C Goodbye Souvenir

· · 个人记录

题意 : 给出一个数组,定义一个数 X 在区间内的权值为 : 最后一次出现的位置减去第一次出现的位置。不重复贡献。

现在资瓷单点修改,查询某个区间内的权值和。

允许离线。n,m\leq 10^5 ,时限\texttt{6s}.

设 las[i] 为上一个同色的位置。

考虑每个数的权值设为 i-las[i] ,我们把区间内的权值求和,就能得到 : 最后一次出现的位置减去第一次出现的前继。

然后,我们要减去多余的 “第一次出现的位置-前继”。

这也好办,计算 \sum\limits_{i=l}^r[las[i]<l]i 即可。这是一个二维数点。

带修改的话,拿 set 维护一下前继,然后写个 CDQ 就做完了。

细节不少,可以CDQ和偏序生成分开来调试。

#include<algorithm>
#include<cstdio>
#include<set>
#define lbit(x) ((x)&-(x))
#define ll long long
#define MaxN 105000
using namespace std;
inline int read(){
  register int X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
ll t[MaxN];
int n,m;
void add(int p,int c)
{while(p<=n){t[p]+=c;p+=lbit(p);}}
void clr(int p)
{while(p<=n){t[p]=0;p+=lbit(p);}}
ll qry(int p){
  ll ret=0;
  while(p){ret+=t[p];p^=lbit(p);}
  return ret;
}
ll ans[MaxN];
struct Data
{int a,b,c,x;bool op;}b[MaxN*7];
bool cmpB(const Data &A,const Data &B){return A.b<B.b;}
int tn;
void solve(int l,int r)
{
  if (l==r)return ;
  int mid=(l+r)>>1;
  solve(l,mid);solve(mid+1,r);
  sort(b+l,b+mid+1,cmpB);
  sort(b+mid+1,b+r+1,cmpB);
  for (int i=mid+1,p=l;i<=r;i++){
    while(p<=mid&&b[p].b<=b[i].b){
      if (b[p].op==1)
        add(b[p].a,b[p].x);
      p++;
    }if (b[i].op==0){
      ll ret=qry(b[i].a);
      if (b[i].x<0)ans[-b[i].x]-=ret;
      else ans[b[i].x]+=ret;
    }
  }for (int i=l;i<=mid;i++)
    if (b[i].op==1)clr(b[i].a);
}
set<int> s[MaxN];
int x[MaxN],las[MaxN],tq;
void upd(int p,int i){
  int c=*(--s[x[p]].lower_bound(p));
  b[++tn]=(Data){p,las[p],i,p-las[p],1};
  add(p,las[p]-c);las[p]=c;
  b[++tn]=(Data){p,las[p],i,c-p,1};
}
int main()
{
  n=read();m=read();
  for (int i=1;i<=n;i++)s[i].insert(0);
  for (int i=1;i<=n;i++){
    x[i]=read();
    las[i]=*(--s[x[i]].end());
    add(i,i-las[i]);
    b[++tn]=(Data){i,las[i],0,las[i]-i,1};
    s[x[i]].insert(i);
  }
  for (int i=1,op;i<=m;i++){
    op=read();
    if (op==1){
      int p=read();s[x[p]].erase(p);
      set<int>::iterator it=s[x[p]].upper_bound(p);
      if (it!=s[x[p]].end())upd(*it,i);
      it=s[x[p]=read()].insert(p).first;
      upd(p,i);it++;if (it!=s[x[p]].end())upd(*it,i);
    }else {
      int l=read(),r=read();
      ans[++tq]=qry(r)-qry(l-1);
      b[++tn]=(Data){l-1,l-1,i,-tq,0};
      b[++tn]=(Data){r,l-1,i,tq,0};
    }
  }for (int i=1;i<=n;i++)t[i]=0;
  solve(1,tn);
  for (int i=1;i<=tq;i++)
    printf("%lld\n",ans[i]);
  return 0;
}