题目列表 - LOJ

菜单

gwfate
gwfate
发布于 2026-09-04 / 10 阅读
0
0

代码模板

快读快输

inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch == '-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

数学

#define rs (x>>1|1)
#define ls (x>>1)

int oldiv(int x1,int y1,int x2,int y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
int mhdiv(int x1,int y1,int x2,int y2){return abs(x1-x2)+abs(y1-y2);}

int gcd(int x,int y){ return y?gcd(y,x%y):x;}
int lcm(int x,int y){ return x/gcd(x,y)*y;}

链式前向星

struct edge{
     int to,next,val;
}e[N<<2];
int head[N],CNT;
void adde(int x,int y,int w){
     e[++CNT].to=y;
     e[CNT].val=w;
     e[CNT].next=head[x];
     head[x]=CNT;
};

线段树

struct SegNode{
	int val,sign,Max,Min,Sum;
};int SIGN=0;
class SegTree{
	#define mid ((l+r)>>1)
	#define ls (x<<1)
	#define rs (x<<1|1)
	
	public:
	
	SegNode tree[(N<<2)+22];
	
	//====================MAX====================
		inline void pushupMax(int x){
			tree[x].Max=max(tree[ls].Max,tree[rs].Max);
		}
		
		//====================MAX_Plus====================
		inline void downMaxPlus(int x,int l,int r){
			tree[ls].sign+=tree[x].sign;
			tree[ls].Max+=tree[x].sign;
			tree[rs].sign+=tree[x].sign;
			tree[rs].Max+=tree[x].sign;
			tree[x].sign=SIGN;
		}
		
		inline void changeMaxPlus(int x,int l,int r,int cl,int cr,int p){
			if(cl<=l && r<=cr){
				tree[x].Max+=p; 
				tree[x].sign+=p;
				return ;
			}
			if(tree[x].sign!=SIGN) downMaxPlus(x,l,r);
			if(cl<=mid) changeMaxPlus(ls,l,mid,cl,cr,p);
			if(cr>mid) changeMaxPlus(rs,mid+1,r,cl,cr,p);
			pushupMax(x);
		}
		
		int MaxPlusQuery(int x,int l,int r,int cl,int cr){
			if(cl<=l && r<=cr) return tree[x].Max;
			if(tree[x].sign!=SIGN) downMaxPlus(x,l,r);
			int ans=-1e18;
			if(cl<=mid) ans=MaxPlusQuery(ls,l,mid,cl,cr);
			if(cr>mid) ans=max(ans,MaxPlusQuery(rs,mid+1,r,cl,cr));
			return ans;
		}
		
		//====================MAX_Equal====================
		inline void downMaxEqual(int x,int l,int r){
			tree[ls].sign=tree[x].sign;
			tree[ls].Max=tree[x].sign;
			tree[rs].sign=tree[x].sign;
			tree[rs].Max=tree[x].sign;
			tree[x].sign=SIGN;
		}
		
		inline void changeMaxEqual(int x,int l,int r,int cl,int cr,int p){
			if(cl<=l && r<=cr){
				tree[x].Max=p; 
				tree[x].sign=p;
				return ;
			}
			if(tree[x].sign!=SIGN) downMaxEqual(x,l,r);
			if(cl<=mid) changeMaxEqual(ls,l,mid,cl,cr,p);
			if(cr>mid) changeMaxEqual(rs,mid+1,r,cl,cr,p);
			pushupMax(x);
		}
		
		int MaxEqualQuery(int x,int l,int r,int cl,int cr){
			if(cl<=l && r<=cr) return tree[x].Max;
			if(tree[x].sign!=SIGN) downMaxEqual(x,l,r);
			int ans=-1e18;
			if(cl<=mid) ans=MaxEqualQuery(ls,l,mid,cl,cr);
			if(cr>mid) ans=max(ans,MaxEqualQuery(rs,mid+1,r,cl,cr));
			return ans;
		}
		
		
	//====================MIN====================
		inline void pushupMin(int x){
			tree[x].Min=min(tree[ls].Min,tree[rs].Min);
		}
		
		//====================MIN_Plus====================
		inline void downMinPlus(int x,int l,int r){
			tree[ls].sign+=tree[x].sign;
			tree[ls].Min+=tree[x].sign;
			tree[rs].sign+=tree[x].sign;
			tree[rs].Min+=tree[x].sign;
			tree[x].sign=SIGN;
		}
		
		inline void changeMinPlus(int x,int l,int r,int cl,int cr,int p){
			if(cl<=l && r<=cr){
				tree[x].Min+=p; 
				tree[x].sign+=p;
				return ;
			}
			if(tree[x].sign!=SIGN) downMinPlus(x,l,r);
			if(cl<=mid) changeMinPlus(ls,l,mid,cl,cr,p);
			if(cr>mid) changeMinPlus(rs,mid+1,r,cl,cr,p);
			pushupMin(x);
		}
		
	    int MinPlusQuery(int x,int l,int r,int cl,int cr){
			if(cl<=l && r<=cr) return tree[x].Min;
			if(tree[x].sign!=SIGN) downMinPlus(x,l,r);
			int ans = 1e18;
			if(cl<=mid) ans=MinPlusQuery(ls,l,mid,cl,cr);
			if(cr>mid) ans=min(ans,MinPlusQuery(rs,mid+1,r,cl,cr));
			return ans;
		}
		
		//====================MIN_Equal====================
		inline void downMinEqual(int x,int l,int r){
			tree[ls].sign=tree[x].sign;
			tree[ls].Min=tree[x].sign;
			tree[rs].sign=tree[x].sign;
			tree[rs].Min=tree[x].sign;
			tree[x].sign=SIGN;
		}
		
		inline void changeMinEqual(int x,int l,int r,int cl,int cr,int p){
			if(cl<=l && r<=cr){
				tree[x].Min=p; 
				tree[x].sign=p;
				return ;
			}
			if(tree[x].sign!=SIGN) downMinEqual(x,l,r);
			if(cl<=mid) changeMinEqual(ls,l,mid,cl,cr,p);
			if(cr>mid) changeMinEqual(rs,mid+1,r,cl,cr,p);
			pushupMin(x);
		}
		
		int MinEqualQuery(int x,int l,int r,int cl,int cr){
			if(cl<=l && r<=cr) return tree[x].Min;
			if(tree[x].sign!=SIGN) downMinEqual(x,l,r);
			int ans = 1e18;
			if(cl<=mid) ans=MinEqualQuery(ls,l,mid,cl,cr);
			if(cr>mid) ans=min(ans,MinEqualQuery(rs,mid+1,r,cl,cr));
			return ans;
		}
		
	
	//====================SUM====================
		inline void pushupSum(int x){
			tree[x].Sum=tree[ls].Sum+tree[rs].Sum;
		}
		
		//====================SUM_Plus====================
		inline void downSumPlus(int x,int l,int r){
			tree[ls].sign+=tree[x].sign;
			tree[ls].Sum+=(mid-l+1)*tree[x].sign;
			tree[rs].sign+=tree[x].sign;
			tree[rs].Sum+=(r-mid)*tree[x].sign;
			tree[x].sign=SIGN;
		}
		
		inline void changeSumPlus(int x,int l,int r,int cl,int cr,int p){
			if(cl<=l && r<=cr){
				tree[x].Sum+=p*(r-l+1); 
				tree[x].sign+=p;
				return ;
			}
			if(tree[x].sign!=SIGN) downSumPlus(x,l,r);
			if(cl<=mid) changeSumPlus(ls,l,mid,cl,cr,p);
			if(cr>mid) changeSumPlus(rs,mid+1,r,cl,cr,p);
			pushupSum(x);
		}
		
		int SumPlusQuery(int x,int l,int r,int cl,int cr){
			if(cl<=l && r<=cr) return tree[x].Sum;
			if(tree[x].sign!=SIGN) downSumPlus(x,l,r);
			int ans=0;
			if(cl<=mid) ans+=SumPlusQuery(ls,l,mid,cl,cr);
			if(cr>mid) ans+=SumPlusQuery(rs,mid+1,r,cl,cr);
			return ans;
		}
		
		//====================SUM_Equal====================
		inline void downSumEqual(int x,int l,int r){
			tree[ls].sign=tree[x].sign;
			tree[ls].Sum=(mid-l+1)*tree[x].sign;
			tree[rs].sign=tree[x].sign;
			tree[rs].Sum=(r-mid)*tree[x].sign;
			tree[x].sign=SIGN;
		}
		
		inline void changeSumEqual(int x,int l,int r,int cl,int cr,int p){
			if(cl<=l && r<=cr){
				tree[x].Sum=p*(r-l+1); 
				tree[x].sign=p;
				return ;
			}
			if(tree[x].sign!=SIGN) downSumEqual(x,l,r);
			if(cl<=mid) changeSumEqual(ls,l,mid,cl,cr,p);
			if(cr>mid) changeSumEqual(rs,mid+1,r,cl,cr,p);
			pushupSum(x);
		}
		
		int SumEqualQuery(int x,int l,int r,int cl,int cr){
			if(cl<=l && r<=cr) return tree[x].Sum;
			if(tree[x].sign!=SIGN) downSumEqual(x,l,r);
			int ans=0;
			if(cl<=mid) ans+=SumEqualQuery(ls,l,mid,cl,cr);
			if(cr>mid) ans+=SumEqualQuery(rs,mid+1,r,cl,cr);
			return ans;
		}
		
	
	//====================Build====================
		inline void build(int x,int l,int r,int awa[]){
			if(l==r){
				tree[x].val=awa[l];
				tree[x].Sum=awa[l];
				tree[x].Max=awa[l];
				tree[x].Min=awa[l]; 
				return ;
			}
			build(ls,l,mid,awa);
			build(rs,mid+1,r,awa);
			pushupMax(x);
			pushupSum(x); 
			pushupMin(x);
		}
	
	//====================faster====================
		inline void SumEqual(int n,int l,int r,int p){return changeSumEqual(1,1,n,l,r,p);}
		inline void SumPlus(int n,int l,int r,int p){return changeSumPlus(1,1,n,l,r,p);}
		int SumEquQ(int n,int l,int r){return SumEqualQuery(1,1,n,l,r);}
		int SumPluQ(int n,int l,int r){return SumPlusQuery(1,1,n,l,r);}
		
		inline void MaxEqual(int n,int l,int r,int p){return changeMaxEqual(1,1,n,l,r,p);}
		inline void MaxPlus(int n,int l,int r,int p){return changeMaxPlus(1,1,n,l,r,p);}
		int MaxEquQ(int n,int l,int r){return MaxEqualQuery(1,1,n,l,r);}
		int MaxPluQ(int n,int l,int r){return MaxPlusQuery(1,1,n,l,r);}
		
		inline void MinEqual(int n,int l,int r,int p){return changeMinEqual(1,1,n,l,r,p);}
		inline void MinPlus(int n,int l,int r,int p){return changeMinPlus(1,1,n,l,r,p);}
		int MinEquQ(int n,int l,int r){return MinEqualQuery(1,1,n,l,r);}
		int MinPluQ(int n,int l,int r){return MinPlusQuery(1,1,n,l,r);}
		
		void Build(int n,int awa[]){build(1,1,n,awa);}
}STS;

java8,17,21
机械动力

评论