[求助哇哇哇线段树板子题]30分wa了10发了呜呜呜
查看原帖
[求助哇哇哇线段树板子题]30分wa了10发了呜呜呜
299810
issue_is_fw楼主2020/7/21 09:47

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 );
	}
} 
2020/7/21 09:47
加载中...