想了想 还是得先把短板补起来

今天要是完成不了约定的任务那就明天别给自己放假了(笑

预期中今天下午放学之前要结束掉txt里的标星题   然后之后晚上要去补下字符串

另外markdown太蛋疼了QAQ 真不想用了

UOJ228 区间开根 

首先我们可能是想到转为减法 因为每次开根怎么想都不对吧

然后我们试一下 会发现开根取下整之后 一段连续的区间都会是一个值（这不废话吗……相当于把10000的区间压缩到100以内当然都是一个值啊

然后……然后我就很可耻地不记得了

我一开始的想法是记录最大和最小值 如果他们开方之后变为一个值，那么就直接进行区间覆盖(说着就否决了区间减法)

但是这样不仅会很不好写 而且当遇到我们下面提到的情况是没有很好的处理办法的_(:зゝ∠)_

然后又很可耻地不记得了 于是滚去看了一眼

发现别人都是当区间全为一个值的时候就打标记 (maya势能分析好可怕我真的不敢信这个复杂度啊

由于我记得有什么89899之类的数据能卡 所以就加了一句如果只差1而且开方后也只差1就打标记 然后就过去了

区间最值有助于判定一个区间有无修改的必要 而且经常出奇迹 要注意特殊数据

还有10题……瘫

bzoj4066 kdt

怀疑自己之前学的是假的

我以为kdt只能查询什么距离 因为它看上去复杂度很不对 而之所以能查询距离是因为有估价函数帮忙剪枝所以才行

结果被打脸了 原来kdt可以当二维线段树用啊(瘫

按照我的理解 为什么二维线段树空间大？因为有很多节点相当于是专门用于存和的

但kdt是一个点它既要代表一个实际存在的点 又要存下下面所包含的二叉子树信息

这也就是为什么build的时候是递归下去是l,mid-1 和 mid+1,r了

因为当前的mid已被且仅被当前点所记录

这也是为什么每次up都需要

t[x].mn[i]=t[x].mx[i]=t[x][i]; 以及 t[x].sum=t[l].sum+t[r].sum+t[x].w;

另外每次rebuild的范围应当是1-sz！

还记录一下很妙的写法

struct po{

    int d[2],l,r,w,sum,mn[2],mx[2];

    inline int& operator [] (int x) { return d[x]; }

    inline friend bool operator == (po a,po b) { return a[0]==b[0]&&a[1]==b[1]; }

    inline friend bool operator < (po a,po b) { return a[f]<b[f]; }

}p[N],t[N],h;

感觉这个结构体超好

还有一个问题就是我们是把单点加值变为了插入

那么判重的话就这么处理就好了

if (!x) {

    x=++sz;

    t[x][0]=t[x].mn[0]=t[x].mx[0]=h[0];

    t[x][1]=t[x].mn[1]=t[x].mx[1]=h[1];

}

if (t[x]==h) { t[x].w+=h.w,t[x].sum+=h.w; return ; }

   其中h为全局变量

另外我现在能理解为什么有人那么痴迷替罪羊了

暴力重构 非常优美