求卡空间
查看原帖
求卡空间
501947
DengDuck鄧德楼主2024/5/16 19:51

大了就 MLE,小了就 RE。

#include<bits/stdc++.h>
#define LL int
#define LF long double
#define pLL pair<LL,LL>
#define pb push_back
#define LowBound lower_bound
#define UpBound upper_bound
#define Fi first
#define Se second
using namespace std;
//const LL Inf;
const int N=5e4+5;
const int M=5e4;
const long long Mod=1e9+7;
const int MM=1e7+5;
//const LF eps;
//const LL P;
namespace ST
{
	int tot,Ls[MM],Rs[MM],Sz[MM];
	long long S[MM];
	void Up(LL Rt)
	{
		S[Rt]=(S[Ls[Rt]]+S[Rs[Rt]])%Mod;
		Sz[Rt]=Sz[Ls[Rt]]+Sz[Rs[Rt]];
	}
	void Upd(LL &Rt,LL L,LL R,LL x,LL k,LL Flg)
	{
		
		if(!Rt)Rt=++tot;
		if(L==R)
		{
			S[Rt]=(S[Rt]+k+Mod)%Mod;
			Sz[Rt]+=Flg;
			return;
		}
		LL Mid=L+R>>1;
		if(x<=Mid)Upd(Ls[Rt],L,Mid,x,k,Flg);
		else Upd(Rs[Rt],Mid+1,R,x,k,Flg);
		Up(Rt);
	}
	pLL Qry(LL Rt,LL L,LL R,LL l,LL r)
	{
		if(!Rt||R<l||r<L)return {0,0};
		if(l<=L&&R<=r)return {S[Rt],Sz[Rt]};
		LL Mid=L+R>>1;
		pLL X=Qry(Ls[Rt],L,Mid,l,r),Y=Qry(Rs[Rt],Mid+1,R,l,r);
		return {(X.Fi+Y.Fi)%Mod,(X.Se+Y.Se)%Mod};
	}
}

#define Ls(x) (x<<1)
#define Rs(x) (x<<1|1)
LL rt[N<<2];
LL n,m,A[N],B[N];
void Ins(LL Rt,LL L,LL R,LL x,LL i)
{
	//	cout<<"Ins"<<L<<' '<<R<<' '<<i<<endl;
	ST::Upd(rt[Rt],1,M,A[i],B[i],1);
	if(L==R)return;
	LL Mid=L+R>>1;
	if(x<=Mid)Ins(Ls(Rt),L,Mid,x,i);
	else Ins(Rs(Rt),Mid+1,R,x,i);
}
void Del(LL Rt,LL L,LL R,LL x,LL i)
{
	//	cout<<"Del"<<L<<' '<<R<<' '<<i<<endl;
	ST::Upd(rt[Rt],1,M,A[i],-B[i],-1);
	if(L==R)return;
	LL Mid=L+R>>1;
	if(x<=Mid)Del(Ls(Rt),L,Mid,x,i);
	else Del(Rs(Rt),Mid+1,R,x,i);	
}
pLL Qry(LL Rt,LL L,LL R,LL l,LL r,LL x,LL y)
{
	if(R<l||r<L)return {0,0};
	if(l<=L&&R<=r)
	{
		pLL X=ST::Qry(rt[Rt],1,M,x,y);
		//	cout<<L<<' '<<R<<' '<<x<<' '<<y<<' '<<X.Fi<<' '<<X.Se<<endl;
		return {X.Fi,X.Se};
	}
	LL Mid=L+R>>1;
	pLL X=Qry(Ls(Rt),L,Mid,l,r,x,y),Y=Qry(Rs(Rt),Mid+1,R,l,r,x,y);
	return {(X.Fi+Y.Fi)%Mod,(X.Se+Y.Se)%Mod};
}
long long Ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&A[i],&B[i]);
		pLL t=Qry(1,1,n,1,i-1,A[i]+1,M);
		Ans=(Ans+t.Se*B[i]%Mod+t.Fi)%Mod;
		Ins(1,1,n,i,i);
	}
	for(int i=1;i<=m;i++)
	{
		LL x,y;
		scanf("%d%d",&x,&y);
		if(x==y)
		{
			printf("%lld\n",Ans);
			continue;
		}
		if(x>y)swap(x,y);
		if(A[x]>A[y])Ans-=(B[x]+B[y]);
		if(A[y]>A[x])Ans+=(B[x]+B[y]);
		//	cout<<Ans<<endl;
		if(x+1<=y-1)
		{
			pLL t1=Qry(1,1,n,x+1,y-1,1,A[y]-1);// A[y] Add
			//	cout<<t1.Se<<endl;
			Ans=(Ans+t1.Se*B[y]%Mod+t1.Fi)%Mod;
			pLL t2=Qry(1,1,n,x+1,y-1,A[y]+1,M);// A[y] Del
			Ans=(Ans-t2.Se*B[y]%Mod-t2.Fi+2*Mod)%Mod;
			pLL t3=Qry(1,1,n,x+1,y-1,A[x]+1,M);// A[x] Del
			Ans=(Ans+t3.Se*B[x]%Mod+t3.Fi)%Mod;
			pLL t4=Qry(1,1,n,x+1,y-1,1,A[x]-1);// A[x] Add
			Ans=(Ans-t4.Se*B[x]%Mod-t4.Fi+2*Mod)%Mod;
		}
		Del(1,1,n,x,x);
		Del(1,1,n,y,y);
		swap(A[x],A[y]);
		swap(B[x],B[y]);
		Ins(1,1,n,x,x);
		Ins(1,1,n,y,y);
		printf("%lld\n",Ans);
	}
	return 0;
}
//RP++
2024/5/16 19:51
加载中...