WA 20pts求条
查看原帖
WA 20pts求条
1037614
__crz_qaq__楼主2024/8/22 08:28
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int root[N],a[N],tot;
int tr[N<<5],ls[N<<5],rs[N<<5],tag[N<<5];
void pushup(int p){tr[p]=tr[ls[p]]+tr[rs[p]];}
int build(int pl,int pr)
{
	int p=++tot;
	if(pl==pr)
	{
		tr[p]=a[pl];
		return p;
	}
	int mid=(pl+pr)>>1;
	ls[p]=build(pl,mid);
	rs[p]=build(mid+1,pr);
	pushup(p);
	return p;
}
void addtag(int p,int pl,int pr,int d)
{
	tag[p]+=d;
	tr[p]+=(pr-pl+1)*d;
}
void pushdown(int p,int pl,int pr)
{
	int mid=(pl+pr)>>1;
	if(tag[p])
	{
		addtag(ls[p],pl,mid,tag[p]);
		addtag(rs[p],mid+1,pr,tag[p]);
		tag[p]=0;
	}
}
int update(int p,int pl,int pr,int L,int R,int d)
{
	++tot;
	tr[tot]=tr[p];
	ls[tot]=ls[p];
	rs[tot]=rs[p];
	tag[tot]=tag[p];
	p=tot;
	if(L<=pl&&pr<=R)
	{
		addtag(p,pl,pr,d);
		return p; 
	}
	int mid=(pl+pr)>>1;
	pushdown(p,pl,pr);
	if(L<=mid)ls[p]=update(ls[p],pl,mid,L,R,d);
	if(mid<R)rs[p]=update(rs[p],mid+1,pr,L,R,d);
	pushup(p);
	return p;
}
int query(int p,int pl,int pr,int L,int R)
{
	if(R<pl||pr<L)
		return 0;
	if(L<=pl&&pr<=R)
		return tr[p];
	int mid=(pl+pr)>>1;
	pushdown(p,pl,pr);
	return query(p<<1,pl,mid,L,R)+query(p<<1|1,mid+1,pr,L,R);	
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n=2;
	root[0]=build(1,n);
	int x,y;
	cin>>x>>y;
	root[1]=update(-1,1,n,1,1,x);
	root[2]=update(-1,1,n,2,2,y);
	cout<<query(1,1,n,1,2);
	return 0;
}

2024/8/22 08:28
加载中...