10.1闲话做题纪要10.2闲话做题纪要10.3闲话做题纪要luoguP3241[HNOI2015]开店不难发现两个点在点分树上的\(\operatorname{LCA}\)是一个求距离的好的分割点，考虑点分树。暂且不考虑\([l,r]\)的限制，因为只是一个限制范围的查找。设\(siz_{x}\)表示点分树

MyBlogs[ARC174E]ExistenceCounting比较机械的处理方式。和NOID2T2是一个性质，只不过简单多了。枚举生成序列和\(P\)的第一个不同位置\(i\)，则第\(i\)个位置能填的数的个数\(g_i\)是\(<a_i\)并且之前没有出现过的数，\(g_i\)可以简单用树状数组求出。然后考虑如何

MyBlogs[ARC179E]RectangleConcatenation唐完了。稍微观察一下发现矩形只有两种形态。考虑暴力：从每个\(i\)开始向后扫，设\(f_{j,0}\)表示能否拼在左右，\(f_{j,1}\)表示能否拼在上下。设\(S_{l,r}\)表示\([l,r]\)内矩形的面积和，没想到用面积判就败了：\[\begin{aligned

MyBlogs杜教筛是一种能在\(\mathcalO(n^{\frac23})\)的时间复杂度内求积性函数前缀和的筛法。虽然复杂度比较优秀，但是被筛的积性函数需要满足特殊性质。Min_25筛由Min_25发明，相对更通用，其时间复杂度为\(\mathcalO(\frac{n^{\frac34}}{\logn})\)。首先构造一个完

（一）注意到\(x_i\)的绝对值\(\len\)。那么统计每一个位置的血量和。先从靠近的击杀必定最优，剩余的子弹用\(sum\)存储。还是直接上代码吧。（二）AC代码。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intt,n,k,a[300010],dis[300010],s[300010];

CF396C考虑将贡献表示出来：\(\forallv\in\text{subtree}_u\)，\(v\)会加上\(x-(dep_v-dep_u)k\)，然后发现这个东西可以维护整棵子树，即把\(x,dep_u\timesk\)和\(dep_v\timesk\)分开计算，然后\(dep_v\)可以最后再管，就变为子树加，单点和了。用树状数组维护dfs序即可。

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'intn,a[300010],c[300010],t[300010],s;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(intx,i=1;i<=n;i++){

CSP模拟17T1弹珠游戏考虑贪心，枚举右端点，产生贡献的是没有填满的人，所以先让某些人填满是最优的。优先填满已经填了2个的，再填1个的。方案数就是每次填了相同个数的人数的乘积。code#include<iostream>#include<cstdio>#include<cstring>#include<vector>usingnamespaces

前言传送门blog思路首先看数据范围$10^5$，$O(n\log_2n)$可以过，自然想到二分。二分具有单调性，那么如何确保整个$a$序列按顺序排列呢？我们可以使用st表维护区间最大值，如果在这个距离中已经有了$a_i\geb_j$那么最大值一定指向的是新加入进来的那个值，否则在之前二分就