day2:215
这一天的题目相对比较模板化
t1:50
看错了数据范围
求n个点到给出的点哈夫曼距离的最小值
我想到的是一种非常zz的做法
我们二分答案，然后判断是否在这个距离内有点
但是这样前缀和不是很好维护
于是我们利用哈夫曼距离和切比雪夫距离的转化
(x+y,x-y)
然后就变成了简单的二维前缀和
另外坐标有负数，所以要都加一个值
其实有更简单的做法
直接做多源最短路就可以了
t2:100
首先我们可以按照ai排序
然后动态维护最小生成树（支持加边）
这个本身是lct裸题
但是因为这题目里有点数限制
所以我们可以暴力访问两点之间的路径
怎么找路径呢？（直接dfs就可以了）
t3:65
65就是个基本的暴力（因为没有时间就没有搞正解了）
首先我们要把撤销操作给搞掉
其实就是倒着访问搜索树
然后就变成了维护颜色
然后我们发现那个操作是等价于对二分图的点搞
所以按照行+列分类
然后问题就变成了子矩形覆盖查询最终颜色的问题
注意这个东西是不能直接树套树维护的
因为并不能保证先后顺序
可行的树套树维护方案是
我们倒着做，那么每个点被第一次覆盖就是最终颜色
于是这个是经典的线段树问题了，记录区间内是否有没有覆盖颜色的地方
复杂度n^2log^2
另外题解给出了并查集的维护方法
考虑如果是序列问题
维护每一个下一个没有凃颜色的地方
本质和树套树是一样的
然后推广到二维就直接暴力推广
复杂度(nq+n^2)*logn
下面这个是代码
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define mid ((h+t)>>1)
char c;
const int N=;
const int N2=2e6;
bool f[N][N],ans[N2];
bitset<> g[][N][N];
struct re{
int a,b,c,d,e;
}a[N2],b[N2];
int n,m;
void fz(int h,int t,int h1,int t1)
{
dep(i,mid,h)
dep(j,m,)
{
g[][i][j]=;
if (f[i][j])
{
if (i==mid) g[][i][j][j]=;
if (j+<=m&&f[i][j+]) g[][i][j]|=g[][i][j+];
if (i+<=mid&&f[i+][j]) g[][i][j]|=g[][i+][j];
}
}
rep(i,mid,t)
rep(j,,m)
{
g[][i][j]=;
if (f[i][j])
{
if (i==mid) g[][i][j][j]=;
if (j->=&&f[i][j-]) g[][i][j]|=g[][i][j-];
if (i->=mid&&f[i-][j]) g[][i][j]|=g[][i-][j];
}
}
int h2=h1-,t2=t1+;
rep(i,h1,t1)
{
if (a[i].a<=mid&&a[i].c>=mid)
ans[a[i].e]=(g[][a[i].a][a[i].b]&g[][a[i].c][a[i].d]).any();
else if (a[i].c<mid) b[++h2]=a[i];
else b[--t2]=a[i];
}
rep(i,h1,h2) a[i]=b[i];
if (h<=mid-) fz(h,mid-,h1,h2);
rep(i,t2,t1) a[i]=b[i];
if (mid+<=t) fz(mid+,t,t2,t1);
}
int main()
{
freopen("boardgame.in","r",stdin);
freopen("boardgame.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
rep(i,,n)
{
rep(j,,m)
{
cin>>c;
if (c=='.') f[i][j]=;
else f[i][j]=;
}
}
int k;
cin>>k;
rep(i,,k)
{
int x,y,x1,y1;
cin>>x>>y>>x1>>y1;
a[i].a=x; a[i].b=y; a[i].c=x1; a[i].d=y1; a[i].e=i;
}
fz(,n,,k);
rep(i,,k)
if (ans[i]) printf("Yes\n");
else printf("No\n");
return ;
}
其实我们有更优秀的方法来解决大范围问题
矩形问题还是应该多考虑一下扫描线
于是现在我们要维护的其实是每个点出现颜色的最晚的值
这个我们可以线段树套平衡树来维护
（注意具体的我们要标记永久化来维护，因为这个标记是不支持down的）
于是假设不是要求出所有位置的颜色
我们的复杂度就是qlog^2了
相比之前的有很大进展
另外要注意一下这个东西不能用kd-tree来做
我写完才发现很有问题。。
kd-tree支持的操作是，修改一定要对在kd-tree上的点进行修改
也就是说kd-tree维护的是单点修改区间查询操作
而这道题如果要维护就得把所有点加入
而kd-tree的最坏复杂度是sqrt(n) 此时n=n^2
所以退化成暴力
day3：280
我感觉是非常zz的一天
考完？？？为什么两道线段树 然后正解都不需要这个东西
第一题瞎模拟就不说了
第二题其实很简单，想复杂了
支持三个操作
1.在某一个邮箱放一封新的信
2.删除某个邮箱里的所有信
3.删除前k封信
我都已经忘记我怎么想出来这么zz的线段树了
正解就是对于删前k封信这个操作记录一下
然后对删某个邮箱里的信暴力进行（先把那个标记进行一下）
因为每个信最多被删一次，所以就是O(n)的了
然后写线段树的时候
我写了个dfs函数，当f[x]==0的时候才停止
也就是说查到了h==t的点的儿子
于是造成了需要8倍空间的事情
而我只写了4倍空间 就炸了20分
第三题 还是比较水的
我们枚举它最终降到几分
那么比它低的肯定就比它低了
对于比它高的，我们肯定要让比较容易翻车的先翻车
然后 我考场上想的是
插入到线段树里，用线段树二分来做这个东西
虽然复杂度和正解是一样的nlogn 但现在想想非常zz
·