1001
LYF签到
1005
WD签到 贪心
1008
LYF签到 单调栈
1006
WD签到 trie树 细节稍微有些复杂
1009
LYF ZRC 签到(英语题面意义不清)
1007
WD BSGS
题意：
n个人，刚开始球在1号脚下，每秒钟都把球踢给别人，经过t秒回到1号脚下的方案数%998244353是x。问最少经过了几秒。
解：
记f[i][0]表示时间为i，球在1号脚下的方案数，f[i][1]表示在别人脚下的。
推导可知f[i][0]=f[i-2][0]*(n-2)+f[i-1][0]*(n-1).f[0]=1,f[1]=0
特征根法求通项，$f[i]=\frac{(n-1)^{i}+(n-1)\cdot (-1)^{i}}{n}$
分奇偶讨论，BSGS求离散对数即可。
补1010
好题！！！
题意：
给定n1e5的值域1e5的a数组，m1e5个询问，在下标l到r中，值域d到u中有多少个不同的数。离线
比赛时想法：
比赛时先想到主席树，写了半天发现是假做法，又没有发现更好的维护方案。想别的方法时想到了莫队，但是要根号套log估计过不了（但是比赛时确实有人过了，数据水+评测机快）；也有树套树做法（但是一时半会儿写不出来）。一直在刚这题，结果却没做出来。
解：
莫队真的要靠线段树来维护吗？不是的。考虑莫队在运行时的情况，修改O(m*sqrt(n))，查询O(m)；如果利用线段树，那就在修改和查询时都套上log。但是如果采取最简单的分块策略，修改可以做到O(1)，而查询在O(sqrt(n))。取长补短，相得益彰。这样两边乘起来，最终复杂度就是O(m*sqrt(n))啦！
补1002
题意：
给n1e5个点，每个点有两个属性，r和v。当一个点在另一个点为圆心的半径为r的圆内的时候，答案增加v。问v
解：
圆数点。kdtree裸题