发现自己对于一些不用动脑子的数据结构题还是有微弱的冲击力的。
A.BZOJ3722
为什么想不到？？？？？？？？？？？？？？？？？？？？？？？？
先不考虑 \(0\) 跑一遍，每个非叶结点取其子结点中 \(-1,-2\) 的众数，若相等则为 \(0\)。
此时若根节点为 \(-1\)，那么其有偶数个值为 \(0\) 的儿子，对于每个 \(0\) 第一个对它子树中为 \(0\) 的叶子进行操作的人会将这个结点定为其对应的值，那么最优决策下根结点为 \(0\) 的儿子将会被 \(-1\) 和 \(-2\) 平分，此时根结点仍为 \(-1\)，必输。
若根节点为 \(-2\)，那么同 \(-1\) 类似，必胜，此时先手选择任意一个为 \(0\) 的叶子结点即可。
若根节点为 \(0\)，则看其能否变为 \(-2\)。具体的，看先手能否把它的一个值为 \(-1\) 的儿子变为 \(0\)，或者值为 \(0\) 的儿子变为 \(-1\)，递归下去即可。
B.P5882 [CTSC2015] misc
若 \(v\) 在 \(s\rightarrow t\) 的最短路上，那么 \(\sigma_{st}(v)=\sigma_{sv}\cdot\sigma_{vt}\)。
那么我们枚举源点 \(s\)，此时 \(R(v)=\sum\limits_{s \ne v \ne t} a_s\sigma_{sv}\frac{ a_t \sigma_{vt}}{\sigma_{st}}\)，\(\sigma_{sv}\) 在最短路的过程中可以求出，后面的可以在以 \(s\) 为源点跑最短路形成的 \(DAG\) 上预处理出来。
C.Souvenirs
我：欸这个题怎么记得在萌熊的一次练习赛中见过，但是当时好像没有改，寄。
不过这回算是场切了。
首先一个很暴力的思路就是莫队的同时用数据结构维护最小差值，复杂度 \(m\sqrt n\log n\)，极限数据要跑七秒多。
试图把数据结构换成 \(\text{bitset}\)，时间复杂度 \(\frac{nm\sqrt n}{w}\)，难评。
发现修改有 \(O(m\sqrt n)\) 个但是询问只有 \(O(m)\) 个，是不是可以根号平衡一下呢。
值域分块，发现修改和查询都是 \(\sqrt n\)，时间复杂度 \(O(nm)\)。
块内套上一个数据结构维护呢，时间复杂度 \(O(m\sqrt n\log \sqrt n)\)，由于 \(\log\sqrt n\) 和 \(\log n\) 相差无几，所以依然是寄掉的。
md 跟你爆了，每个块内开一个 \(\text{bitset}\) 维护答案，修改复杂度为 \(\frac{\sqrt n}{w}\approx5\)，虽然不算很小，但是请相信 \(\text{bitset}\)！绝对卡不满，近似 \(O(1)\)。
但是现在删数不太好删，写个回滚莫队就行了。
写到一半会想起来 \(\text{bitset}\) 根本没有 _Find_prev 这个函数（差评），于是每个块内还要再开一个反着的 \(\text{bitset}\) 来实现 _Find_prev 操作。
时间复杂度 \(O(\frac{nm}{w}+m\sqrt n)\)，实测能过。
好看的码
#include <bits/stdc++.h>
#define fr first
#define se second
#define Un unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define ld long double
#define VE vector<LL>
#define db double
#define Ve vector<int>
using namespace std;
inline int read()
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
return x*f;
}
const int N = 1e5+5,INF = 1e9;
int a[N],c[N],bl[N],ct,mn[N],mx[N],mnt[N],mxt[N],Ans[320],tmp[320],pos[N],B,stk[N],top,n,ans[N<<2];
bitset < 320 > b1[320],b2[320];
struct Que{int l,r,id;}que[N<<2];
bool cmp(Que x,Que y){return bl[x.l] == bl[y.l] ? x.r < y.r : x.l < y.l;}
inline void add(int p)
{
if (b1[bl[p]][pos[p]]) Ans[bl[p]] = 0;
else
{
int q = b1[bl[p]]._Find_next(pos[p]);
if (q < B) Ans[bl[p]] = min(Ans[bl[p]],a[(bl[p]-1)*B+q+1]-a[p]);
q = b2[bl[p]]._Find_next(B-1-pos[p]);
if (q < B) Ans[bl[p]] = min(Ans[bl[p]],a[p]-a[(bl[p]-1)*B+B-q]);
b1[bl[p]][pos[p]] = b2[bl[p]][B-1-pos[p]] = 1,mx[bl[p]] = max(mx[bl[p]],p),mn[bl[p]] = min(mn[bl[p]],p);
}
}
inline void add1(int p)
{
if (b1[bl[p]][pos[p]]) Ans[bl[p]] = 0;
else
{
int q = b1[bl[p]]._Find_next(pos[p]);
if (q < B) Ans[bl[p]] = min(Ans[bl[p]],a[(bl[p]-1)*B+q+1]-a[p]);
q = b2[bl[p]]._Find_next(B-1-pos[p]);
if (q < B) Ans[bl[p]] = min(Ans[bl[p]],a[p]-a[(bl[p]-1)*B+B-q]);
b1[bl[p]][pos[p]] = b2[bl[p]][B-1-pos[p]] = 1,stk[++top] = p,mx[bl[p]] = max(mx[bl[p]],p),mn[bl[p]] = min(mn[bl[p]],p);
}
}
inline int Q(int l,int r)
{
for (int i = l;i <= r;i++) add1(c[i]);
int res = INF,lst = 0;
for (int i = 1;i <= bl[n];i++)
{
res = min(res,Ans[i]);
if (lst && mn[i] < INF) res = min(res,a[mn[i]]-a[lst]);
lst = mx[i] ? mx[i] : lst;
}
while(top) b1[bl[stk[top]]][pos[stk[top]]] = b2[bl[stk[top]]][B-1-pos[stk[top]]] = 0,top--;
for (int i = 1;i <= bl[n];i++) mx[i] = 0,Ans[i] = mn[i] = INF;
return res;
}
int main()
{
n = read(),B = sqrt(n);
for (int i = 1;i <= n;i++) a[i] = c[i] = read(),bl[i] = (i-1)/B+1,pos[i] = (i-1)%B;
sort(a+1,a+n+1),ct = unique(a+1,a+n+1)-a-1;
for (int i = 1;i <= n;i++) c[i] = lower_bound(a+1,a+ct+1,c[i])-a;
int m = read();
for (int i = 1;i <= m;i++) que[i] = {read(),read(),i};
sort(que+1,que+m+1,cmp);
int j = 1;
for (int i = 1;i <= bl[n];i++)
{
for (int k = 1;k <= bl[n];k++)
mx[k] = 0,Ans[k] = mn[k] = INF,b1[k].reset(),b2[k].reset();
int ed = i*B,l = ed+1,r = ed;
while(j <= m && bl[que[j].l] == i)
{
if (bl[que[j].r] == i) ans[que[j].id] = Q(que[j].l,que[j].r);
else
{
while(r < que[j].r) add(c[++r]);
for (int k = 1;k <= bl[n];k++) mxt[k] = mx[k],mnt[k] = mn[k],tmp[k] = Ans[k];
while(l > que[j].l) add1(c[--l]);
int res = INF,lst = 0;
for (int k = 1;k <= bl[n];k++)
{
res = min(res,Ans[k]);
if (lst && mn[k] < INF) res = min(res,a[mn[k]]-a[lst]);
lst = mx[k] ? mx[k] : lst;
}
ans[que[j].id] = res;
for (int k = 1;k <= bl[n];k++) mx[k] = mxt[k],mn[k] = mnt[k],Ans[k] = tmp[k];
while(top) b1[bl[stk[top]]][pos[stk[top]]] = b2[bl[stk[top]]][B-1-pos[stk[top]]] = 0,top--;
}
j++,l = ed+1;
}
}
for (int i = 1;i <= m;i++) printf("%d\n",ans[i]);
return 0;
}
但是由于写到一半被拉去加训信息会考了，所以没打完，最后交的还是 \(O(m\sqrt n\log n)\) 暴力。
也算是把这题给补了。
