RT 就是一个板子题,但我死活不知道哪里错了 wuwuwuwu~~
help~~~
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
#define int long long
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define ls p<<1
#define rs p<<1|1
int n,m,w[maxn];
struct P{
int l,r,v,cnt;
}a[maxn];
void push_up(int p)
{
a[p].v=a[ls].v+a[rs].v;
a[p].cnt=a[ls].cnt+a[rs].cnt;
}
void build(int p,int l,int r)
{
a[p]=(P){l,r,0,0};
if( l==r )
{
a[p].v=w[l],a[p].cnt=1;
return;
}
int mid=l+r>>1;
build(lson); build(rson);
push_up(p);
}
void update(int p,int l,int r,int k,int ok)
{
if( a[p].l>=l&&a[p].r<=r )
{
if( ok==1 ) a[p].v-=k;//颜值下降;
else a[p].v=k,a[p].cnt=1;//换妹子
return;
}
int mid=a[p].l+a[p].r>>1;
if( mid>=l ) update(ls,l,r,k,ok);
if( mid<r ) update(rs,l,r,k,ok);
push_up(p);
}
void del(int p,int k)//删除[l,r]的妹子
{
if( a[p].l==a[p].r )
{
a[p].v=0, a[p].cnt--;//清空妹子
return;
}
int shu=a[ls].cnt;//获取左儿子的妹子数
if( k<=shu ) del(ls,k);
else del(rs,k-shu);
push_up(p);
}
signed main()
{
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> w[i];
int s=500000;
build(1,1,s);
while( m-- )
{
char ok;
int x,y;
cin >> ok;
if( ok=='I'||ok=='C') cin >> x >> y;
else if( ok=='D' ) cin >> x;
if( ok=='C' ) update(1,x,x,y,1);
else if( ok=='I' ) update(1,x,x,y,0);
else if( ok=='D' ) del(1,x);
else printf("%lld\n",a[1].v );
}
}