做网站不推广/个人网站seo

$Describe$

写一种集动态删除、单点修改、区间查询于一身的数据结构

$Solution$

自然分块

难点是如何找到第$x$个未被删除的元素
我会权值线段树，我会二分+树状数组，滚！
用一个数组$Geshu$表示每个块中元素的个数，这样就可以找到第$x$个未被删除的元素就好啦

其他的日常分块咯

$Code$

#include<cmath>
#include<cstdio>
#include<cctype>
#include<iostream>
#include<algorithm>
#define N 200010
using namespace std;typedef long long LL;
int L[710],R[710],t,n,q,opt,x,d,pos[N],k,geshu[710],y;
LL sum[710],add[710],a[N];
//L,R为每个块的左右边界，pos为每个点所属的块，geshu为每个块中还存在节点的个数
//sum为每个块的区间和，add为lazy数组，不过这题用不到
//a是原数组，ok为每个元素是否存在
bool ok[N];
char ch;
inline long long read()
{char c;int d=1;long long f=0;while(c=getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
inline void write(register long long x)
{if(x<0)putchar(45),x=-x;if(x>9)write(x/10);putchar(x%10+48);return;
}//以上输入优化
LL ask(register int l,register int r)//区间查询
{int pl=pos[l],pr=pos[r];LL ans=0;if(pl==pr){for(register int i=l;i<=r;i++) ans+=a[i]+add[pl];//同一块内暴力加return ans;}else{for(register int i=l;i<=R[pl];i++) ans+=a[i]+add[pl];//左边暴力加for(register int i=L[pr];i<=r;i++) ans+=a[i]+add[pr];//右边暴力加for(register int i=pl+1;i<pr;i++) ans+=sum[i]+add[i]*t;//中间加lazy和sumreturn ans;}
}
int find(int x)//找到第x个未被删除的元素所在的块
{int now=0,blk=1;while(now+geshu[blk]<x) now+=geshu[blk++];for(register int i=L[blk];i<=R[blk];i++) {if(!ok[i]) now++;if(now==x)return i;}return -1;
}
signed main()
{n=read();q=read();t=(int)sqrt(200001)+1;for(register int i=1;i<=t;i++) {L[i]=R[i-1]+1,R[i]=min(R[i-1]+t,200001);for(register int j=L[i];j<=R[i];j++) {pos[j]=i;sum[i]+=a[j];if(j>n)ok[j]=true;}}for(register int i=1;i<=n;i++) a[i]=read(),geshu[pos[i]]++,sum[pos[i]]+=a[i];//以上为初始化while(q--){cin>>ch;if(ch=='Q') write(ask(1,n)),putchar(10);//区间查询if(ch=='C') {x=read();y=read();if(!ok[x]) a[x]-=y,sum[pos[x]]-=y;}//单点修改if(ch=='D') {x=read();y=find(x);sum[pos[y]]-=a[y];a[y]=0;ok[y]=1;--geshu[pos[y]];}//动态删点if(ch=='I') {x=read();y=read();sum[pos[x]]-=a[x];a[x]=y;sum[pos[x]]+=a[x];if(ok[x])geshu[pos[x]]++,ok[x]=0;if(x>n) n=x;}//加入新点}return 0;
}