上午模拟赛100+50+0+0.
T3本来能拿更高的分数，但是预处理放到里面了。
T1\((kruskal+lca)\)
最小瓶颈生成树/最短路。
其实仔细想想，让他们之间最大边最短，其实就是最短的代价连通。据此得到解决。
T2
构造序列a：
\[i\&1 ：a[i] = i + 1 / 2 \]\[i \% 2 == 0：a[i] = n + 1 - i / 2 \]现在有\(q<=1e5\)次询问：有多少区间的和=s?
观察性质咯。
这个序列可以写成
观察区间和->相邻和？
\[i\&1 ：a[i] + a[i + 1] = n + 1 \]\[i \% 2 == 0：a[i] + a[i + 1] = n + 2 \]据此分类讨论。
具体来说：
l奇，r偶。块是固定的=s/(n + 1),也就是问有多少个间隔为这个的组。
l偶r奇同理。用刚刚的图看来是斜线。
lr同奇偶。我们取出模数，则模数其实就是ar。则取出模数下标(直接根据上面取），判断l=r-bk是否合法即可。
T3：
观察popcount()的性质。
这个性质。
接下来如何做？看60分给予我们启发：可以先不用管上界。
接下来考虑枚举popcount=i,然后把i-1,i+1固定，接下来就变成了一个组合数问题。预处理组合数，over。带上上界呢？也很简单，如果r此位为1，令此位为0算答案，继续递归，这样就变成了logn个无限制数，over。
T4：
套了层博弈论壳子。
g:我感觉至多一部分是博弈，用来表达某种约束（充要条件）。
->必胜？（每个数选的个数）c1^c2..!=0
->如果带上bob,异或和>m才行,否则失败。
->表达限制：sigma aici<=k，ci异或 >m，
->异或按位独立，按位DP，
f[pos,i, lmt, cnt, op] = f[位数, 第几个数, 顶到下界，剩余钱数（单位是2^pos)，当前填了奇/偶个1]，转移就行。
动态开点
用来优化空间复杂度，有些情况我们必须开大，比如
询问要多少，我就开多少。
具体来说如何做？
动态开点就是首先不能用堆式编号，然后额外处理下当前节点为空情况，其他一样。
Node中记录lson,rson。modify时记录当前区间，特殊处理!u，开引用u,over
老师代码。
#define mid ((l+r)>>1)
void ins(int &x,int l,int r,int p){
if(!x) x=++tot;
if(l==r){
tr[x].siz=1;
tr[x].sum=p;
tr[x].pf=1ll*p*p;
return;
}
if(p<=mid) ins(tr[x].ls,l,mid,p);
else ins(tr[x].rs,mid+1,r,p);
pushup(x);
}
线段树合并
例题T6：
->不考虑修改，好像可以线段树二分（考虑
->修改呢？我们想要快速维护合并子树信息，这就可以线段树合并了。
线段树二分。
void up(int u){
s[u]=s[ch[u][0]]+s[ch[u][1]];
}
void add(int &u,int l,int r,int v){
if(!u) u=++node;
if(l==r){s[u]++;return;}
int mid=(l+r)>>1;
if(v<=mid) add(ch[u][0],l,mid,v);
else add(ch[u][1],mid+1,r,v);
up(u);
}
int query_kth(int u,int l,int r,int k){
if(l==r) return l;
int mid=(l+r)>>1;
if(k<=s[ch[u][0]]) return query_kth(ch[u][0],l,mid,k);
return query_kth(ch[u][1],mid+1,r,k-s[ch[u][0]]);
}
void merge(int &a,int b,int l,int r){
if(!a){a=b;return;}
if(!b) return;
if(l==r){s[a]+=s[b];return;}
int mid=(l+r)>>1;
merge(ch[a][0],ch[b][0],l,mid);
merge(ch[a][1],ch[b][1],mid+1,r);
up(a);
}
T7:
几乎是裸板。
->子树与自己维护信息相同，需要快速合并，且子树信息可以使用线段树
->线段树合并
T8：
->树上路径修改
->树上差分行不行？
->迅速维护子树信息，考虑线段树合并维护计数器咯
or
->树上路径修改
->树链剖分！
->这样就要写树套树了，就根本没有可写性了。
->区间加，差分呗，查的时候查前缀。
->修改总早于查询，最后查的时候从小到大线段树维护。
T9：
->式子挺有特点，推式子呗。
->考虑ai总作为大数贡献，则线段树需要维护个数，权和。
->维护子树信息，线段树合并。
->咋合并？合并时左对左/右对右递归，左对右呢？一块计算式子，over。
T10（**攒着：
![]
(/i/l/?n=24&i=blog/3203093/202407/3203093-20240724214010106-1404433267.png)
T11
此题注意链表模拟deque,当年挂了一车人MLE。
->其他都是线段树合并裸板，2有意思，咋办呢？
->又不能合并，就仿照思想，一块递归就行了，因为个数>1/2。
->老师fxj当年做法：
区间随机选点30次，选不到的概率1/(2^30)，基本认为正确。
天才!他说要是他写合并就现在站不到这里了。