MLE 0pts求条
查看原帖
MLE 0pts求条
1037614
__crz_qaq__楼主2024/8/22 20:50
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int tot,root[N];
int tr[N<<5],adt[N<<5],mlt[N<<5];
int ls[N<<5],rs[N<<5];
int copy(int p)
{
	++tot;
	tr[tot]=tr[p];
	adt[tot]=adt[p];
	mlt[tot]=mlt[p];
	ls[tot]=ls[p];
	rs[tot]=rs[p];
	return tot;
}
void pushup(int p){tr[p]=tr[ls[p]]+tr[rs[p]];}
void addadt(int p,int pl,int pr,int d)
{
	adt[p]+=d;
	tr[p]+=(pr-pl+1)*d;
}
void addmlt(int p,int d)
{
	adt[p]*=d;
	mlt[p]*=d;
	tr[p]*=d;
}
void pushdown(int p,int pl,int pr)
{
	int mid=(pl+pr)>>1;
	if(adt[p]!=0||mlt[p]!=1)
	{
		addmlt(ls[p],mlt[p]);
		addmlt(rs[p],mlt[p]);
		addadt(ls[p],pl,mid,adt[p]);
		addadt(rs[p],mid+1,pr,adt[p]);
		adt[p]=0;
		mlt[p]=1;
	}
}
int build(int pl,int pr)
{
	int p=++tot;
	if(pl==pr)
		return p;
	int mid=(pl+pr)>>1;
	ls[p]=build(pl,mid);
	rs[p]=build(mid+1,pr);
	pushup(p);
	return p;
}
int add(int p,int pl,int pr,int L,int R,int d)
{
	p=copy(p);
	if(L<=pl&&pr<=R)
	{
		addadt(p,pl,pr,d);
		return p;
	}
	int mid=(pl+pr)>>1;
	pushdown(p,pl,pr);
	ls[p]=add(ls[p],pl,mid,L,R,d);
	rs[p]=add(rs[p],mid+1,pr,L,R,d);
	pushup(p);
	return p;
}
int multple(int p,int pl,int pr,int L,int R,int d)
{
	p=copy(p);
	if(L<=pl&&pr<=R)
	{
		addmlt(p,d);
		return p;
	}
	int mid=(pl+pr)>>1;
	pushdown(p,pl,pr);
	ls[p]=multple(ls[p],pl,mid,L,R,d);
	rs[p]=multple(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()
{
	int x,y;
	cin>>x>>y;
	root[0]=build(1,2);
	root[1]=add(root[0],1,2,1,1,x);
	root[2]=add(root[0],1,2,2,2,y);
	root[3]=multple(root[1],1,2,1,1,1);
	root[4]=multple(root[3],1,2,1,2,1);
	cout<<query(1,1,2,1,2);
}
2024/8/22 20:50
加载中...