APIO2018
T1
线段树分治即可
当然set的做法也很神...这个还没有写
T2
KD树 考场上没有写对
回家被卡成87然后卡常ing
经网上高人指点卡过了
T3
圆方树
圆点点权-1 方点点权为该点双大小
统计一下所有经过圆点的路径权值和即可
bzoj2125
仙人掌上多次询问两点最短路
建圆方树
然后就是LCA + 分类讨论
bzoj4137
火星商店问题
线段树分治然后可持久化Trie维护异或。。。
本来有一个很明显的树套树做法但会被卡空间
bzoj5358
给一个数列$a$
每次查询$prod_{i = l}^{r}a_i$是不是$d$的倍数
考虑到100000内的数可以表示成不超过30个数的乘积
分解质因数然后直接上主席树
或者可以维护一下每个质因数在序列上每次出现的位置
然后二分
bzoj5248
一双木棋...
重写一遍是因为听人说状态只有300000+
所以开map对抗搜索一下就可以了
bzoj4025
一个图 每次可以加边或者删边 查询当前的图是不是二分图
线段树分治+可持久化并查集维护环的奇偶性
bzoj4418
求若干个扇形的面积并集
线段树
bzoj3620
KMP
bzoj3585
查询区间mex
离散化主席树