本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-16 17:01:35

文中 $n$ 实际表示题目中的 $n-1$ 。

设 $d=A-B$ 。首先显然 $d>0$ 。

观察性质，发现可以把整条路径拆成两条，从起点出发每隔 $d$ 个都会经过，从终点往回走每隔 $d$ 个也会经过，具体共经过几个点取决于 $A$ 的取值。两条路径经过点数相同，点互不同。

然后枚举 $d$ ，再枚举 $A$ ，发现 $A$ 需要满足 $A\equiv n \pmod{d}$ 。而且 $A\leq n$ ，所以 $A$ 的取值个数只有 $\frac{n}{d}$ 个。

发现不合法的方案满足 $n\equiv 0\pmod{d}\land n-A\geq A$ 。后面条件的前者是第一条路径的结尾，后者是第二条路径的结尾，只要 $d|n$ ，就可能出现两条路径涉及同一点的情况，路径是连续段，所以只需要判有无交即可。

代码好写，可以不需要用数组预处理前/后缀和，但是这样写比较简单。

因为在处理后缀和的时候可能会越界，所以开了两倍空间（因为这个调了好久/ll）

code

const int N=2e5+5;

int a[N];

int pre[N],suf[N];

signed main(){
	int n=read()-1;
	for(int i=0;i<=n;i++)
		a[i]=read();
	int ans=0;
	for(int d=1;d<=n;d++){
		for(int i=d;i<=n;i+=d)
			pre[i]=pre[i-d]+a[i];
		for(int i=n;i>=0;i-=d)
			suf[i]=suf[i+d]+a[i];
		for(int A=n%d+((n%d==0)+1)*d;A<=n;A+=d){
			if(n%d==0&&n-A>=A)
				continue;
			ans=max(ans,pre[n-A]+suf[A]);
		}
	}print(ans),pc('\n'); 
	return 0; 
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-16 23:12:10

有两种做法。

第一种：

观察问题，等价于求一个 $p-1$ 次函数 $f(x)$ 满足 $f(i)\equiv a_i\pmod{p}$ 。用拉格朗日插值法求即可。

第二种：

费马小定理 ：$x^{p-1}\equiv 1\pmod{p}(p\ is\ prime\land p \nmid x)$ 。

考虑通过这个来构造 $g_i(x)=[x=a_i]$ 。

也很简单，对于 $a_i=1$ ， $g_i(x)=1-(x-i)^{p-1}$ ，$a_i=0$ ， $g_i(x)=0$ 即可。

然后答案即为 $f(x)=\sum_{i=0}^{p-1}g_i(x)$ 。

只写了第二种。

code

const int N=3e3+5;
int mod;

int a[N];

int J[N],inv[N];

int qp(int x,int y){
	int ans=1;
	for(int i=1;i<=y;i<<=1){
		if(i&y)
			ans=ans*x%mod;
		x=x*x%mod;
	}return ans;6
}

int b[N];

int C(int n,int m){
	return J[n]*inv[n-m]%mod*inv[m]%mod;
}

signed main(){
	int p=read();
	mod=p;
	J[0]=inv[0]=1;
	for(int i=1;i<p;i++)
		J[i]=J[i-1]*i%mod;
	inv[p-1]=qp(J[p-1],mod-2);
	for(int i=p-2;i>=1;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
	for(int i=0;i<p;i++){
		if(read()){
			for(int j=p-1;j>=0;j--)
				b[j]-=qp(-i,p-1-j)*C(p-1,j)%mod;
			b[0]+=1;
		}
	}
	for(int i=0;i<p;i++)
		print((b[i]%mod+mod)%mod),pc(' ');pc('\n');
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-21 02:05:29

今天（根据写鲜花的时间来看是昨天）和同学去看了 你的名字。

我从以前就对新海诚的作品不感冒，但除了新的铃芽户缔没看过，秒速五厘米，你的名字，天气之子都自己看过一遍。

看完电影心里并没有太多的波澜，但是在刚刚休息的时候，电影中的许多情感突然充斥于我的脑海。

我一直都很相信缘分，我觉得两个有缘的人想要见面是一定能见到面的，所以我并不担心三叶和泷在并排驶过的两列地铁上会找不到彼此。像是秒速五厘米那样的分别，我打心里觉得还是羁绊太浅。

说起来，我为什么会去看新海诚的作品呢。

我才想到，天气之子刚上映的时候，我应该在五年级吧。那时我尚未深入接触OI，还在小学过着无忧无虑的日子。我当时好像还没有看过第一部自己想要看的动画，但由于前作你的名字的火爆，我好像对天气之子也有一点点印象。但我从未打算去看。

记得那一天，是小学的大队长与其他学生干部选举。那时的我十分认真的准备了这个活动，但在现场紧张的手脚冰凉，喘不出气。最后的才艺展示环节，我照例表演了已经学了很久的钢琴，弹了一首不算简单的曲子——《彩云追月》。这首曲子非常好听，但由于一遍又一遍的练习，那时的我并不沉浸在其中，更不用谈在这个紧张的环境下了。

我是参与选举的倒数第二个人，最后一个人是一名令我印象深刻的女生。她是年级中活跃的人，在学校里担任不少职务，也有不少艺术方面的特长。她在四年级的时候就被选上了宣传部长，一般来说“部长”这样的职位都是由五年级学生担任，这足以见她的能力。小学时的我虽不与对方在一个班内，但也一直暗暗与她较劲，同时也非常敬佩对方。

记得那天，她在最后的才艺展示环节，表演了那首歌《愛にできることはまだあるかい》。

这是一首气势磅礴的歌，一次震撼人心的表演。她选择了这首歌的官方动画版MV作为背景视频和音频，自己则负责伴奏与主旋律的钢琴。我很难用文字述说我当时的感情，但那让我沉浸其中。伴随着背景视频中的念白与动画中的冲突，钢琴也变得一点又一点激昂，迸发着强烈的情感，仿佛要将我纳入其中。这种感觉太奇妙了。

当天晚上我梦游了。那是我迄今为止唯一一次梦游。我与家人们的论断是由于选举时的紧张，但在我写着这篇鲜花时，我发现，这可不可能是如同你的名字中婆婆说的，我正在做的梦？

我在那周的周末在家看了天气之子。片尾阳菜的兜帽飘起，音乐变得激昂，然后是标题出现。即使四年过去，我也还是记得片尾的那一幕。

之后我又看了你的名字，再晚些看了秒速五厘米。虽然风评基本都是你的名字要好，但我更喜欢天气之子。这个结论仿佛很早就在我心中了。现在想想，我可能非常向往天气之子里以男女主为代表的人们的行为：任性，自我，无拘无束。令我印象深刻的是帆高和阳菜的逃亡。虽然可能算不上逃亡，但这深深的打动了我。

时至今日，电影中的演出已记不得多少，残留在脑海中的只剩下那个结尾时出现的标题与音乐。就连我看天气之子的契机：那一次选举上的表演也快被我忘记，那位女生的名字我更是一点都不记得。甚至于在于同学讨论最初是为何看新海诚的电影的时候，也完全没有想起来这件理应也确实给我留下深刻印象的事。

我不会觉得可惜，毕竟我的脑海中只能存放下那一小点当下的东西，并不能清楚的记得过去。但又觉得遗憾。那真的是一次优秀的表演，表演者也是我在小学时并不陌生的人，但我现在却连对方的名字都记不起。

我最常听的RADWIMPS的歌（虽然并不常听）也从 愛にできることはまだあるかい 变成了 大丈夫。

但是泷和三叶无论记不记得对方名字都是一定可以找到彼此的。

我并不需要再次相遇，只希望能够记起对方的名字以体现我对她的尊重。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 13:55:42

Link

感觉我的做法比较奇怪，但感觉很对。

发现 $N$ 比较小，考虑暴力一点的做法。

考虑如何查找所需次数最少，经典想法就是子树大小接近 $\frac{num}{2}$ ，$num$ 是现在还存在的树的大小（每一次若不存在于子树内则砍掉子树再加回来每一个剩余点的父亲，再砍掉所有叶子，若存在则砍掉除子树之外的部分）。

然后暴力维护这一棵树，如果用 set 来维护则复杂度是单次查询 $O(n\log n)$ 。

为什么这样能较优？考虑极端情况——菊花图，这样的情况下，子树大小是距离 $\frac{num}{2}$ 相当远的。

但是注意到每一次若不在子树中则会向上走一格。而菊花图叶子非常多。这种策略在菊花图时能跑的非常快。

那么在链的情况下呢？容易发现若是链，则 $\frac{num}{2}$ 是非常容易接近的一个数。所以其也能跑的非常快。

我估计一个上界是 $O(\sqrt n)$ 级别的，若有读者能够提出证明欢迎发在评论区。

实现方法则是用 set 维护一个点集，表示这些点可能会存在 mole 。按照dfn排序后倒序处理子树和，类似dp。

然后找到子树和最接近 $\frac{num}{2}$ 且最小的点，对其查询。

若 mole 在其子树内则遍历点集，删掉子树外的点。若不在则删掉子树内的点，再将子树外的点删掉，其父亲加入。

容易发现每一种操作可能涉及的点数量都是 $O(n)$ 。这样单次询问即为 $O(n\log n)$ 。

容易发现删掉子树内/外所有点相当于dfn序列上的一个区间覆盖，可以使用差分预处理，但将父亲插入较难实现。可以找出一个点距离其子树内叶子最远距离，然后考虑一次整体上移造成的影响：删掉所有叶子，加入根的父亲（若有）。删叶子可以通过刚刚所说的预处理子树内距叶子最远距离来实现，加入父亲只会造成 $O(1)$ 级别的影响。这样可以把复杂度优化到 $O(n)$ 。

但是单 $\log$ 的方法在 test 2 ILE 了，线性没调出来，后来写了个 vector 暴力删 过了。有点太逆天了。

其原理与用 set 维护一样，同样是删除与去重。但是由于 vector 删除复杂度高且去重也要手动所以不优。

以下是 $O(n^2)$ 的 vector 暴力删做法代码。

code

const int N=5e3+5;

struct edge{
	int v,nxt;
}e[N<<1];
int head[N],tott;
void add(int u,int v){e[++tott]={v,head[u]},head[u]=tott;}

vector<int> vec;

int dep[N],dfn[N],cnt;
int L[N],R[N];
int fa[N];
void dfs(int u,int faa){
	L[u]=dfn[u]=++cnt;
	dep[u]=dep[faa]+1;
	fa[u]=faa;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==faa)
			continue;
		dfs(v,u);
	}R[u]=cnt;
}

bool cmp(int x,int y){
	return dep[x]==dep[y]?dfn[x]<dfn[y]:dep[x]<dep[y];
}

bool tag[N];
int sum[N];
bool ask(){
	int id=vec.back();
	int num=vec.size()\/2;
	for(int i=vec.size()-1;i>=0;i--){
		int v=vec[i];
		sum[v]++;
		if(abs(sum[v]-num)<abs(sum[id]-num)||
		  (abs(sum[v]-num)==abs(sum[id]-num)&&sum[v]<sum[id]))
			id=v;
		if(tag[fa[v]])
			sum[fa[v]]+=sum[v];
	}
	for(int i:vec)
		sum[i]=0;\/\/清空
	cout<<"? "<<id<<endl;
	int opt=read();
	if(opt){
		for(int i=0;i<vec.size();i++){
			int v=vec[i];
			if(dfn[v]>R[id]||dfn[v]<L[id]){
				tag[v]=0;
				vec.erase(vec.begin()+i);
				i--;
			}
		}
	}else{
		for(int i=0;i<vec.size();i++){
			int v=vec[i];
			if(dfn[v]<=R[id]&&dfn[v]>=L[id]){
				tag[v]=0;
				vec.erase(vec.begin()+i);
				i--;
			}else if(v!=1){
				tag[v]=0;
				tag[fa[v]]=1;
				vec[i]=fa[v];
				if(i>0&&vec[i]==vec[i-1]){\/\/去重，在按照深度及dfn序排序后，若同时将数列中每一个点替换为其父亲，则相同的数字一定出现在连续的一段
					vec.erase(vec.begin()+i);
					i--;
				}
			}
		}
	}
	if(vec.size()==1){
		cout<<"! "<<vec[0]<<endl;
		vector<int> tmp;
		swap(tmp,vec);\/\/清空vector
		return 1;
	}return 0;
}

signed main(){
	signed _T=read();
	while(_T--){
		int n=read();
		for(int i=1;i<n;i++){
			int u=read(),v=read();
			add(u,v),add(v,u);
		}
		dfs(1,0);\/\/预处理
		for(int i=1;i<=n;i++)
			vec.pb(i),tag[i]=1;\/\/tag表示还存在于点集内
		sort(all(vec),cmp);
		while(!ask());
		for(int i=1;i<=n;i++)
			head[i]=tag[i]=0;
		tott=0;
		cnt=0;
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-18 21:01:47

已经给你了一个前置问题，求满足 $a_i|a_j$ 的有序对 $(i,j)$ 数，那么显然可以通过这个来容斥。

我的方法可能不是最简单的，如有更简单的方法欢迎爆破（

对于有序四元组 $(i,j,k,l)$ ，先计算出满足 $i\neq k\land j\neq l$ 的数量，然后分别排除掉满足 $i=j$，$k=l$，$i=l$，$j=k$ 的四元组数量。（这里后两者其实是一样的）

对于 $i=j$ ，固定了因数，直接找两个数字满足其都为 $a_i$ 的倍数即可。

对于 $k=l$ ，固定了倍数，直接找两个因数即可。

对于 $i=l$ 或 $j=k$，固定了处在中间的数字，分别找一个因数和一个倍数即可。

注意上述三个情况都仍需要满足所找的数字与固定的数字不是同一个数字（数值可以相同），但不需要保证找的两个数字不同。

都可以通过与解决前置问题类似的方法求解。

然后再加上多减掉的部分。其总共有六种，但其中有四种的贡献都是零。因为在限制了 $i\neq k\land j\neq l$ 的前提下不可能同时有三个数是同一个数字。

那么剩下的两种就是 $i=j\land k=l$ 与 $i=l\land j=k$ 。

前者数量其实就是前置问题的数量，对于后者需要简单分析一下，发现其等价于这四个数的数值相同。

那么就是选两个不同的数字且数值相同的方案数（选择数字有序，即选第 1，3 个数字与选 3，1 个数字算两种方案）。

没有下一层容斥了，因为后面的贡献都是零，原因与前面贡献为零的原因相同。

给出代码。

code

const int N=1e5+5;

int t[N],s[N];\/\/分别是桶和因数个数

signed main(){
	signed n=read();
	for(int i=1;i<=n;i++)
		t[read()]++;
	int ans=0;
	int w=1e5;
	for(int i=1;i<=w;i++){
		if(t[i]==0)
			continue;
		ans+=t[i]*(t[i]-1);
		for(int j=i*2;j<=w;j+=i)
			ans+=t[i]*t[j];
	}ans*=ans+1;\/\/加一是提前将第一个贡献加上，后面就不用再算一遍了
	for(int i=1;i<=w;i++){\/\/i=j
		if(t[i]==0)
			continue;
		int sum=t[i]-1;
		for(int j=i*2;j<=w;j+=i)
			sum+=t[j];
		ans-=t[i]*sum*sum;
	}
	for(int i=1;i<=w;i++){\/\/k=l
		if(t[i]==0)
			continue;
		s[i]+=t[i]-1;
		ans-=t[i]*s[i]*s[i];
		for(int j=i*2;j<=w;j+=i)
			s[j]+=t[i];
	}\/\/print(ans),pc('\n');
	
	for(int i=1;i<=w;i++){\/\/i=l||k=j
		if(t[i]==0)
			continue;
		int sum=t[i]-1;
		for(int j=i*2;j<=w;j+=i)
			sum+=t[j];
		ans-=t[i]*s[i]*sum*2;\/\/这里乘二是同时计算两种
	}\/\/print(ans),pc('\n');
	
	for(int i=1;i<=w;i++)
		if(t[i]>=2)
			ans+=t[i]*(t[i]-1);\/\/第二个贡献，有序地选两个相同的数字的方案数
	print(ans),pc('\n');
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-25 17:29:56

数据分治某一部分数组不够大/忘加模数

Splay带Tag在Find完还要pushdown一遍，否则tag可能会随这个点旋上去

写SPFA

在题目给了代码片段的时候，若要用这段片段，记得把所有可能导致CE的东西define掉，比如 uint64_t ，在liunx下可以正常运行，但windows上用lemon会寄，DEV正常运行。

组合数插板法没开两倍空间。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-25 20:23:26

题意：

给出长度为 $n$ 的数组 $a$ ，求三元组最大和，满足三元组严格升序且后两者差大于前两者差。

用 $(I,J,K)$ 分别表示其对应三元组中哪一个元素，考虑有效的点对 $(i,j)$ 个数。

发现对于每一个区间内的答案所对应的 $(i,j)$ 一定为一个子区间内的最大与次大值。

对于区间 $[i,j]$ ，若无右端点限制，这个区间内的 $(I,J)$ 最优值一定为最大与次大值。原因显然。

而所有区间的最大值与次大值点对数的数量级是 $\mathrm{O(n)}$ 的。（相同数值按照下标定优先级）

这里的证明可以考虑单调栈过程。寻找这些对也可以直接通过单调栈求解。

然后我们现在得到了 $\mathrm{O(n)}$ 对点对。怎么求答案呢。

我们可以把询问离线下来，按照下标顺序依次将点对丢进集合处理其对答案贡献。

可以这样维护：

枚举左端点，计算每一个位置作为 $k$ 的答案。所有以当前点为 $I$ 的点对 $(i,j)$ 对每一个合法位置造成的贡献。合法位置是一个后缀。

设 $b_x$ 表示上面说的以 $x$ 为 $K$ 的最大贡献，这个贡献的格式是 $b_x=max(b_x,a_x+val)$ ，后面的 $val$ 是 $a_i+a_j$ ，对同一对点对 $(i,j)$ 是定值。这个可以直接线段树维护。查询就直接区间最值即可。

int pre[N],suf[N];

int stk[N],tot;
int a[N];

struct Seg_Tree{
	int t[N<<2],mx[N<<2];
	int tag[N<<2];
	void pushup(int x){
		t[x]=max(t[ls],t[rs]);
		t[x]=max(t[x],mx[x]+tag[x]);
	}
	void pushdown(int x){
		if(tag[ls]<tag[x]){
			tag[ls]=tag[x];
			t[ls]=max(t[ls],mx[ls]+tag[ls]);
		}
		if(tag[rs]<tag[x]){
			tag[rs]=tag[x];
			t[rs]=max(t[rs],mx[rs]+tag[rs]);
		}
	}
	void update(int x,int l,int r,int L,int R,int val){
		if(L<=l&&r<=R){
			tag[x]=max(tag[x],val);
			t[x]=max(t[x],tag[x]+mx[x]);
		}else{
			pushdown(x);
			if(L<=mid)
				update(ls,l,mid,L,R,val);
			if(R>mid)
				update(rs,mid+1,r,L,R,val);
			pushup(x);
		}
	}
	int query(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R)
			return t[x];
		pushdown(x);
		int ans=0;
		if(L<=mid)
			ans=max(ans,query(ls,l,mid,L,R));
		if(R>mid)
			ans=max(ans,query(rs,mid+1,r,L,R));
		return ans;
	}
	void build(int x,int l,int r){
		tag[x]=0;
		if(l==r)
			t[x]=mx[x]=a[l];
		else{
			build(ls,l,mid);
			build(rs,mid+1,r);
			mx[x]=max(mx[ls],mx[rs]);
		}
	}
}T;

pir p[N<<1];

struct Que{
	int l,r,id;
	bool operator<(Que &ano)const{
		return l>ano.l;
	}
}Q[N];

int ans[N];

signed main(){
	int n=read(),q=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++){
		while(tot>0&&a[stk[tot]]<a[i])
			suf[stk[tot--]]=i;
		pre[i]=stk[tot];
		stk[++tot]=i;
	}
	for(int i=1;i<=n;i++){
		if(pre[i])
			p[++tot]={pre[i],i};
		if(suf[i])
			p[++tot]={i,suf[i]};
	}
	sort(p+1,p+1+tot);
	for(int i=1;i<=q;i++)
		Q[i]={read(),read(),i};
	sort(Q+1,Q+1+q);
	T.build(1,1,n);
	for(int l=n,nw=tot,nwq=1;l>=1&&nw>=1;l--){
		while(p[nw].fi==l){
			int L=p[nw].se+(p[nw].se-p[nw].fi),R=n;
			nw--;
			if(L>R)
				continue;
			T.update(1,1,n,L,R,a[p[nw+1].fi]+a[p[nw+1].se]);
		}
		while(Q[nwq].l==l){
			ans[Q[nwq].id]=T.query(1,1,n,Q[nwq].l,Q[nwq].r);
			nwq++;
		}
	}
	for(int i=1;i<=q;i++)
		print(ans[i]),pc('\n');
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-25 20:42:54

题意：

给出一个长度为 $n+m$ 的 01串，要求将其划分为两个子序列 $a$ 和 $b$ ，长度分别为 $n$ 和 $m$ ，使每一个元素都恰好在一个子序列内，使这两个子序列视为二进制数后加和最大，求出二进制下最大加和。

scallion 赛时的做法是：使 $n>m$ ，将前 $m$ 个位分给 $b$ ，后 $n$ 个位给 $a$ ，然后两个指针从分界处开始分别往左和右扫，对于左边扫到的 $1$ ，若右边扫到的 $0$ 位权比自己大则交换。

感觉有点对，但不知道为啥能取到上界。

code

const int N=1e6+5;

char s[N];

int ans[N];

signed main(){
	signed _T=read();
	while(_T--){
		int n=read(),m=read();
		scanf("%s",s+1);
		if(n>m)swap(n,m);
		int l=n,r=n+1;
		while(1){
			while(l>0&&s[l]=='0')
				l--;
			while(r<=n+m&&s[r]=='1')
				r++;
			if(l>0&&r<=n+m&&n+m-r>n-l)
				swap(s[l],s[r]);
			else
				break;
		}
		for(int i=1;i<=m;i++)
			ans[i]=s[n+m-i+1]-'0';
		for(int i=1;i<=n;i++)
			ans[i]+=s[n-i+1]-'0';
		for(int i=1;i<=n+m;i++)
			ans[i]+=ans[i-1]>>1,ans[i-1]&=1;
		int len=n+m;
		while(len>1&&ans[len]==0)len--;
		for(int i=len;i>=1;i--)
			pc(ans[i]+'0'),ans[i]=0;
		pc('\n');
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-26 19:49:19

喵喵题

题目来自某个不愿透露姓名的同学。

1. 有8节电池，4节有电，4节没电。每次可以测试其中两节是否全都有电，问最少几步能保证找到两节有电的电池。

如果按照分成4组，每组分别测一次，然后在每一组内部测是8步。

但是你可以直接分组为2，3，3然后分别内部枚举，答案是7。

2. 平面上 $n$ 个点，求是否存在一条恰好经过两个点的直线。

结论很简洁，不是全部共线就是存在。

考虑反证。设每一条直线上都存在至少3个点。每一个点都向所有直线做垂线。那么考虑最短的一条垂线（长度为正）AD，垂点是D，与BC垂直（BC是两端），这条垂线所垂的线中间的点（D，根据假设一定不是BC）与和它在垂线的同一侧的另一个点（B或C）与A的连线做的垂线一定更短（∠A一定大于等于90度）。与前提矛盾。

3. 平面上 $n$ 个红点，$n$ 个蓝点，任意3点不共线，任意4点不共圆，求是否存在方案使得红蓝配对，每对点连线互不交。

发现每对点的距离和最短时一定互不交，因为可以把一个交给拆开，长度一定严格变小。

4. 平面上 $n$ 个点，任意3点不共线，任意4点不共圆，有一条直线初始经过恰好一个点，接下来这条直线开始顺时针旋转，当恰好经过恰好两点时脱离初始经过的点，以后来的点为中心继续顺时针旋转。问是否存在初始方案使得每一个点都会被经过至少一次。

发现直线在转的时候，其两侧点的数量不变，且恰好改变一个点在左侧或右侧。

那么直接找一个角度满足这个角度下没有点共线，然后找到正中间那个点，其左右两侧的点数量最多相差1（其实可以无视这里的差，因为另一个满足相同条件的点也能够满足后面的），在这条直线旋转半周后，左边的点全都跑到了右边，右边的点全都到了左边，每一个点都至少被经过了一次。

5. 求 $\sum_{i=0}^n F_i^2$ 。

画图几何分析矩形面积发现其等于 $F_n\times F_{n+1}$ 。

6. 三个有交的圆，每一对相对应的交点相连，连出三条线段。证明三线共点。

唉唉，有点强了。把这三个圆作为赤道（确信）做三个球，显然只有两个点（对称）同时存在于三个球的表面。

也可以先构出两个球，其球面的交是一个垂直于平面的圆。这个圆与新的球面作交显然只会得到点。

7. 平面上有一个面积小于1大于0的不规则图形，定义横纵坐标都为整数的点为格点，证明一定存在一种方案，使得平移这个图形使得没有一个格点被图形包含或位于图形的边缘。

考虑移动格点，如何同时刻画所有格点？

我们先随便定一个点为原点，把所有格点划分出的单位矩形全都割下来叠在一起。把含有图形的部分看作不透明，不含图形的部分看作透明，那么不透明区域面积一定小于1。

然后直接找一个点满足这个点上没有图形（一定存在因为整个单位矩形的面积是1而在这个单位矩形上显示的图形面积一定小于等于原面积），直接把这个点作为原点新建坐标系即可让格点避开所有图形。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 21:30:27

其实是简单东西。

代码上唯一需要注意的点反而来自动态开点。

尽量不要把区间范围放进结构体，可能会爆空间。

模板的代码

code

const int N=1e5+5,limit=1e5;

struct edge{
	int v,nxt;
}e[N<<1];
int head[N],tott;
void add(int u,int v){e[++tott]={v,head[u]},head[u]=tott;}

struct Seg_Tree{
	struct hhh{
		int s[2];
		int mx,c;
	}t[N<<5];
	int idx;
	void pushup(int x){
		if(t[t[x].s[0]].mx>=t[t[x].s[1]].mx)
			t[x].mx=t[t[x].s[0]].mx,t[x].c=t[t[x].s[0]].c;
		else
			t[x].mx=t[t[x].s[1]].mx,t[x].c=t[t[x].s[1]].c;
	}
	void update(int x,int l,int r,int c,int a){
		if(l==r)
			t[x].mx+=a,t[x].c=c;
		else{
			if(c<=mid){
				if(!t[x].s[0])
					t[x].s[0]=++idx;
				update(t[x].s[0],l,mid,c,a);
			}else{
				if(!t[x].s[1])
					t[x].s[1]=++idx;
				update(t[x].s[1],mid+1,r,c,a);
			}
			pushup(x);
		}
	}
	int merge(int x,int y,int l,int r){
		if(!x||!y) return x+y;
		if(l==r){
			t[x].mx=t[x].mx+t[y].mx;
			return x;
		}
		t[x].s[0]=merge(t[x].s[0],t[y].s[0],l,mid);
		t[x].s[1]=merge(t[x].s[1],t[y].s[1],mid+1,r);
		pushup(x);
		return x;
	}
}T;

int fa[21][N],dep[N];
void dfs(int u,int faa){
	fa[0][u]=faa;
	dep[u]=dep[faa]+1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==faa)
			continue;
		dfs(v,u);
	}
}
void init(int n){
	for(int k=1;k<=19;k++)
		for(int i=1;i<=n;i++)
			fa[k][i]=fa[k-1][fa[k-1][i]];
}
int lca(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[fa[i][x]]>=dep[y])
			x=fa[i][x];
	if(x==y)
		return x;
	for(int i=19;i>=0;i--)
		if(fa[i][x]!=fa[i][y])
			x=fa[i][x],y=fa[i][y];
	return fa[0][x];
}

void dfs_merge(int u,int faa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==faa)
			continue;
		dfs_merge(v,u);
		T.merge(u,v,1,limit);
	}
}

signed main(){
	int n=read(),q=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	dfs(1,0);
	init(n);
	T.idx=n;
	while(q--){
		int u=read(),v=read(),x=read();
		T.update(u,1,limit,x,1);
		T.update(v,1,limit,x,1);
		int l=lca(u,v);
		T.update(l,1,limit,x,-1);
		if(fa[0][l])
			T.update(fa[0][l],1,limit,x,-1);
	}
	dfs_merge(1,0);
	for(int i=1;i<=n;i++)
		print(T.t[i].mx==0?0:T.t[i].c),pc('\n');
	return 0;
}