CF 848C

概述听说，一个好的oier是题目喂出来的。 题意 给定长度为n的数组, 定义数字X在[l,r]内的值为数字X在[l,r]内最后一次出现位置的下标减去第一次出现位置的下标 给定m次询问, 每次询问有三个整数a,b,c询问规则如下: 当a=1时, 将数组内第b个元素更改为c 当a=2时, 求区间[b,c]所有数字的值的和 解题思路 不难想到对于每个点，记录上一个权值和他相同的点的下标（不妨称之为前驱)，设

听说，一个好的oIEr是题目喂出来的。

题意

给定长度为n的数组,定义数字X在[l,r]内的值为数字X在[l,r]内最后一次出现位置的下标减去第一次出现位置的下标

给定m次询问,每次询问有三个整数a,b,c询问规则如下:

当a=1时,将数组内第b个元素更改为c

当a=2时,求区间[b,c]所有数字的值的和

解题思路

不难想到对于每个点，记录上一个权值和他相同的点的下标（不妨称之为前驱)，设他的权值为这两个下标之差。

于是可以发现 [l,r] 的权值可以基本表示为[l,r]内所有点的权值和。

但我们很快发现，我们多加了一些。

而后修正为[l,r]内所有前驱也在[l,r]内的点的权值和。

然后看着就很像查询二维平面上一个矩形的和了。

CDQ分治即可

``

include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int sz=7e5+527;
struct hh{
int x,y,t,val;
}tmp[sz],q[sz];
int n,m;
int tot,cnt;
int type,x,y;
ll a[sz],f[sz];
ll ans[sz];
set S[sz];
set ::i@R_502_6704@tor it;
int head[sz],lst[sz];
voID update(int x,int sum){
for(;x<=n+1;x+=(x&(-x))) f[x]+=sum;
}
ll query(int x){
ll ret=0;
for(;x;x-=x&(-x)) ret+=f[x];
return ret;
}
voID cdq(int l,int r){
if(l==r) return;
int mID=(l+r)>>1;
cdq(l,mID),cdq(mID+1,r);
int i=l,j=mID+1,k=l-1;
while(i<=mID||j<=r){
if(j>r || i<=mID && (q[i].x<q[j].x || q[i].x==q[j].x &&q[i].t<q[j].t)){
if(!q[i].t) update(q[i].y,q[i].val);
tmp[++k]=q[i];
i++;
}
else{
if(q[j].t){
int num=abs(q[j].val);
if(q[j].val>0) ans[num]+=query(q[j].y);
else ans[num]-=query(q[j].y);
}
tmp[++k]=q[j];
j++;
}
}
for(int i=l;i<=mID;i++) if(!q[i].t) update(q[i].y,-q[i].val);
for(int i=l;i<=r;i++) q[i]=tmp[i];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
S[a[i]].insert(i);
lst[i]=head[a[i]],head[a[i]]=i;
q[++tot]=(hh){i,lst[i],i-lst[i]};
}
for (int i=1; i<=m; ++i){
scanf("%d%d%d",&type,&x,&y);
if (type==1){
int p1=0,n1=0;//前驱 后继
it=S[a[x]].find(x);
if (it!=S[a[x]].begin()) --it,p1= it,++it;
if ((++it)!=S[a[x]].end()) n1=it; --it;
S[a[x]].erase( it); q[++tot]=(hh){x,lst[x],lst[x]-x}; if(n1){ q[++tot]=(hh){n1,lst[n1],lst[n1]-n1}; lst[n1]=p1; q[++tot]=(hh){n1,n1-lst[n1]}; } int p2=0,n2=0; a[x]=y; S[a[x]].insert(x); it=S[a[x]].find(x); if (it!=S[a[x]].begin()) --it,p2=it,++it; if ((++it)!=S[a[x]].end()) n2=*it; --it; lst[x]=p2; q[++tot]=(hh){x,x-lst[x]}; if (n2){ q[++tot]=(hh){n2,lst[n2],lst[n2]-n2}; lst[n2]=x; q[++tot]=(hh){n2,n2-lst[n2]}; } } else{ ++cnt; q[++tot]=(hh){x-1,x-1,1,cnt}; q[++tot]=(hh){y,cnt}; q[++tot]=(hh){x-1,-cnt}; q[++tot]=(hh){y,-cnt}; } } for (int i=1; i<=tot; ++i) q[i].x++,q[i].y++; cdq(1,tot); for(int i=1;i<=cnt;i++) printf("%lld\n",ans[i]); }

总结

以上是内存溢出为你收集整理的CF 848C全部内容，希望文章能够帮你解决CF 848C所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。