（T1）lnsyoj2212 刷数组

考场上切掉了，所以来说说考场上的做法。
首先看数据范围，线段树并不能拿满分，所以考虑在数组上操作。
如何处理区间覆盖：记录一下区间覆盖的数，然后记录第几次覆盖，单点修改或增加时查看次数被覆盖了几次，若与正常覆盖次数不符，则将此数设为新的覆盖数。
考场代码如下：

#include <cstdio>
#define int long
using namespace std;
int ans;
int a[10000005];
int qtcs[10000005];
int qtshu;
int yqtcs;
int n,q;
signed main(){
	scanf("%ld%ld",&n,&q);
	for(int i=1;i<=q;i++){
		int opt;
		scanf("%ld",&opt);
		if(opt==1){
			int x,y;
			scanf("%ld%ld",&x,&y);
			if(qtcs[x]<yqtcs){
				a[x]=qtshu;
				qtcs[x]=yqtcs;
			}
			ans+=y-a[x];
			a[x]=y;
		}
		else if(opt==2){
			int x,y;
			scanf("%ld%ld",&x,&y);
			if(qtcs[x]<yqtcs){
				a[x]=qtshu;
				qtcs[x]=yqtcs;
			}
			ans+=y;
			a[x]+=y;
		}
		else if(opt==3){
			int y;
			scanf("%ld",&y);
			qtshu=y;
			ans=y*n;
			yqtcs++;
		}
		printf("%ld\n",ans); 
	}
	return 0;
}

（T2）lnsyoj2213 LCA 的统计

（考场上还想以为有规律呢，最后提交时还忘了记忆化，真是服了）
首先设\(f_{i}\)为当根节点的权值为i时所有LCA的和，\(g_{i}\)为当根节点的权值为i时树的节点数。
转移为:\(f_{i}=\begin{cases}2f_{i/2}+i(g_{i}^{2}-2g_{i/2}^2)&i\%2==0\\f_{i/2}+f_{i/2+1}+i(g_{i}^{2}-g_{i/2}^2-g_{i/2+1}^2)&i\%2==1\end{cases}\)
\(g_{i}=\begin{cases}2g_{i/2}+1&i\%2==0\\g_{i/2}+g_{i/2+1}+1&i\%2==1\end{cases}\)
可以通过打表找规律得知\(g_{i}=2i-1\)。
原因：因为一个根节点为i的树的左右子树都为神奇的树，所以肯定将左右两个树的权值进行合并，然后需要考虑一下几种情况：
1.左子树与根节点的LCA总和，因为左子树与根节点的LCA一定为根节点，所以权值都采用根节点的。
2.右子树与根节点的LCA总和，与左子树相似。
3.左子树与右子树的LCA总和，因为左子树与右子树的LCA显然为根节点，所以权值都采用根节点的。
4.根节点与根节点的LCA总和，直接加一吧。
所以会发现除了左右子树内的贡献不采用根节点，其余的均采用根节点的权值。
dp时进行记忆化搜索，记忆化时用map或unordered_map维护，时间复杂度\(O(Tlog_{n})\)，取模细节超级多，说不定哪就挂了。。。。。。
代码如下：

#include <cstdio>
#include <algorithm>
#include <unordered_map>
#define int long long
#define mod 1000000007
using namespace std;
unordered_map<int,int> um;
inline int g(int i){
	return (2*i%mod-1+mod)%mod;
}
int dfs1(int i){
	if(um[i]!=0){
		return um[i];
	}
	if(i&1){
		um[i]=((dfs1(i/2+1)+dfs1(i/2))%mod+i%mod*(((g(i)*g(i)%mod-g(i/2+1)*g(i/2+1)%mod+mod)%mod-g(i/2)*g(i/2)%mod+mod)%mod)%mod)%mod;
		return um[i];
	}
	else{
		um[i]=((dfs1(i/2)*2)%mod+i%mod*(((g(i)*g(i)%mod-g(i/2)*g(i/2)%mod+mod)%mod-g(i/2)*g(i/2)%mod+mod)%mod)%mod)%mod;
		return um[i];
	}
}
int T;
signed main(){
	um[1]=1;
	scanf("%lld",&T);
	for(int i=1;i<=T;i++){
		int n;
		scanf("%lld",&n);
		printf("%lld\n",dfs1(n));
	}
	return 0;
}