原题地址

My code:

#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
int n,m;
int l[N],r[N],pos[N];
int a[N],cnt[N],siz[N];
int sum[N];
int len,f;
void C(int x,int y)
{	if(!cnt[N])
	return;
	sum[pos[x]]-=a[x];
	a[x]-=y;
	sum[pos[x]]+=a[x];
}
void I(int x,int y)
{	if(cnt[x])
	{	sum[pos[x]]-=a[x];
		a[x]=y;
		sum[pos[x]]+=a[x];
		
	}
	else
	{	cnt[x]=1;
		sum[pos[x]]-=a[x];
		a[x]=y;
		sum[pos[x]]+=a[x];
		siz[pos[x]]++;
	}
}
void D(int x)
{	int tot=1;
	while(x-siz[tot]>0)
	x-=siz[tot],tot++;
	for(int i=l[tot];i<=r[tot];i++)
	{	if(!x-cnt[i])
		{	siz[tot]--;
			sum[tot]-=a[i];
			a[i]=0;
			cnt[i]=0;
			return;
		}
		else
		{	x-=cnt[i];
		}
	}
}
signed main()
{	int h=500000;
	f=sqrt(h);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{	cin>>a[i];
		cnt[i]=1;
	}
	for(int i=1;i<=h;i++)
	{	pos[i]=(i-1)/f+1;
		
	}
	for(int i=1;i<=pos[h];i++)
	{	l[i]=r[i-1]+1;
		//int n1=500000;
		r[i]=min(l[i]+f-1,h);
	}
	/*for(int i=1;i<=h;i++)
	{	l[i]=r[i-1]+1;
		
	}
	if(r[h]<100000)
	{	h++;
		l[h]=r[h-1]+1;
		r[h]=100000;
	}*/
	for(int i=1;i<=pos[h];i++)
	{	for(int j=l[i];j<=r[i];j++)
		{	//pos[j]=i;
			sum[i]+=a[j];
			siz[i]+=cnt[j];
		}
	}
	for(int i=1;i<=m;i++)
	{	char s;
		int x,y;
		cin>>s;
		if(s=='C')
		{	cin>>x>>y;
			C(x,y);
		}
		if(s=='I')
		{	cin>>x>>y;
			I(x,y);
		}
		if(s=='D')
		{	cin>>x;
			D(x);
		}
		if(s=='Q')
		{	int v=0;
			for(int i=1;i<=pos[h];i++)
			v+=sum[i];
			cout<<v<<endl;
		 } 
	}
}