题意：
$n$ 个集合，每个集合最多32个unsigned int范围的整数， $m$ 个询问，每次问下标在 $[l,r]$ 之间的集合能否表示出 $x$ 。数据范围 $1\le n,m\le 50000$，每个数字都在 unsigned int 以内。
题解：
线段树维护线性基即可。学习了一发板子。
继续阅读“[线性基][线段树][模板] 牛客多校第四场 B xor”
[比赛补题][线段树][连通分量][二分图] codeforces gym 102055 B Balance of the Force (CCPC 2018 Final)
题意：
给定 $N$ 个人，每个人可以选择加入黑暗 $Dark$ 或者光明 $Light$ 两种阵营，他们加入不同的阵营之后获得的力量值是不同的，即 $D_i$ 和 $L_i$ 。然后有些人之间有矛盾，是不能加入同一阵营的，矛盾的对数共有 $M$ 对，现在给出所有的矛盾和所有的 $L_i D_i$，问在所有可能存在的最终阵营分配情况中，力量值最大的人和力量值最小的人之间的差最小可能是多少？如果说不可能分配的话输出$IMPOSSIBLE$。其中 $1\le N\le 2*10^5$, $0\le M\le 2*10^5$, $1\le L_i D_i \le 10^9$ ,共20组test，时限4S
题解：
一个非常有意思的，看上去像是图论其实是数据结构的题目。。其实以前做过类似的？应该是今年西安邀请赛时候，区别在于那个题目应该是一种背包的性质，一个联通分量要么选，要么不选，而这个题是每个连通分量都得选，但是要从两套孪生方案中选择一种，每一种都会有一个最大值和一个最小值。
把两两不能在一起的人之家连一条无向边，那么一堆互相有关系的人就形成了一个连通分量，不在同一个分量里的人互相是完全没有影响的，无论这个人是选择D还是L都跟我的选择没关系。而在同一个联通分量里的情况的话，可以发现只要有一个人的状态确定了就可以用二分染色的方法确定连通分量里其他所有人的状态。因此我们首先用染色法对每个连通分量判定，如果能染色成功那么就说明有可行解存在，否则输出$IMPOSSIBLE$，另外，在dfs的过程中还要顺便把每个连通分量的两种方案的最大值最小值总共四个数分别求出来（这里我当时就写假了emmm）。之后考虑如何让差值最小化，一般让某个东西最小化很容易想到二分，但是这个题目的条件下，如果要二分就必须再 $O(n)$ 枚举一个下界，乘上 $O(n)$ 的check的话就n方了，显然无法接受。这时候观察这个题目，此时的每个元素(连通分量)正好有两个属性，发现我们可以用一个常用的套路来尝试，那就是按照其中一个属性排序然后对另一个属性套某种log的数据结构。。对这个题来说，回想我们刚才考虑的二分，他必须有一个操作就是枚举出一个下界or上界，那么如果我们就着这个操作进行下去会怎么样？如果我们能一边枚举一边很快的计算出来当当前枚举到的最小值是最小值的时候最大值最小是多少，那么这个问题就可以解决了。
继续阅读“[比赛补题][线段树][连通分量][二分图] codeforces gym 102055 B Balance of the Force (CCPC 2018 Final)”
[线段树][多标记][欧拉降幂] ZOJ 3998 Yet Another Data Structure Problem
题意：
给一个长度1e5的序列，两种操作：操作1 把区间内元素都乘以一个v，操作2：把区间内元素都变为原来的k次方
然后有1e5个询问，问 $[l,r]$ 之间的区间积
题解：
线段树上双标记问题。维护两个 $lazy tag$ ，一个负责次幂一个负责乘，其实相当一个加法和一个乘法然后求区间和。我这里维护的思路是每次都保证维护的点是一个 $k*(a_l a_{l+1}… a_{r} )^w$ 这样一种形式。这样的话每次标记下传的时候，先把w的次幂传下去，注意这时候儿子的k也要变成 $k_{son}^w$ ,然后再把k传下去，即给儿子的 $k_{son}$ 再乘上 $k$ ，这两个顺序搞清楚之后就很好写了。
wa点是，维护$w$次幂对质数取模的时候不能写 $\%mod$ ，而应该用欧拉定理降幂， $\%(mod-1)$ 貌似我因为这个错过很多次了听说用BSGS预处理的话会更快不过我没试过emmm
继续阅读“[线段树][多标记][欧拉降幂] ZOJ 3998 Yet Another Data Structure Problem”
[权值线段树][比赛失误][x] HDU 6609 Find the answer
题意：
给了 $N$ 个数 $W_k$ , 对于每个 $1 \le i \le n$, 在 $i$ 以前不包括 $i$ 的所有 $W$ 里选取最少的一些 $W$ 将其变为 $0$ ， 使得 从 $1$ 到 $i$ 的和不大于 $m$ 。要求对于每个 $i$ 输出最小的数目。
题解：
做的时候傻了，一直用set乱搞，搞来搞去总是tle，主要是用set维护真的会被卡。。用平衡树板子又有点大材小用，于是就米勒很久。
所以说遇到一个简单题很久没出的话，可能就得考虑全盘否定直接从来了。。。
如果一开始就没有被赵老师带着想set，而是直奔线段树去的话，就很好搞了，直接把问题转化为在前 i-1 个数里找出最少的数字使得之和大于 $pre[i]-m$ ，其中 $pre[i]$ 是前缀和。这样的话直接用权值线段树来做，每个节点存两个域，一个是数字的个数，一个是数字的和。。然后query的时候利用线段树天然的二分性质来搞就行了。。。
这题其实动机真的不难，就是因为不用数据结构的话每次要排序，然后权值线段树天生有排序的特性在里面。。。所以遇事不决还是先考虑线段树。。。不能一开始就想骚操作emmmmm
继续阅读“[权值线段树][比赛失误][x] HDU 6609 Find the answer”
[补题][线段树][权值区间离散化] 2019牛客第七场 E Find the median
本质上是一个离散化的权值线段树，其实很简单，比赛时候没写出来是个遗憾，主要当时没考虑清楚离散化的对象，结果和之后的处理方式。
刚开始看题面里一个数据生成公式，以为是强制在线的，后来发现其实是假的，输入是可以全部离线处理出来的。这样的话就可以先把每一步中的L，R求出来了。之后的话，注意到题目的操作实质上相当于权值线段树的操作就可以计数了，我这里当时以为是add值的操作，其实只是增加了数字的个数而已。但是数字范围会很大，所以要离散化一下。这里要特别注意的是在这种区间的离散化之后，就不是原来线段树了（原来的我们所谓正常的线段树其实相当于是个点树），因此要用[l,r)这种左闭右开的区间来计算，否则二分的时候会漏掉中间的一段[mid,mid+1]。
wa点的话有一个是查询的时候参考值要用long long，因为他最大可能是4e5*1e9的,另一个是要开8倍空间，因为4e5个操作其实有8e5个l(r)值。。。
继续阅读“[补题][线段树][权值区间离散化] 2019牛客第七场 E Find the median”
[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E
http://codeforces.com/contest/1062/problem/E
这题两个难点，第一个是如何快速找到一堆不一定在一起的节点的公共LCA，第二个是如何确定这一堆节点中需要剔除哪一个。
可以先想一下，设原集合的lca为p1，可以取得最优答案的点为x，其他点为vi，那么x一定不在lca(所有的vi)这个点的子树上。这时候，任意一个vi和x的lca都是p1。这时假如维护一个S[l,r]表示[l,r]的公共LCA，根据上面说的性质，这个S序列一定存在一个断点，从这个点开始所有的S==p1,这样的话就可以利用二分查找找到这个断点，可以确定这个断点一定是候选答案之一。另外一个在二分的过程中其实是所有的lca都是基于最左边那个点积累过来的，所以除了分界点之外另外一个可能影响到答案的就是最左边这个点。到这里就算是找到了唯二可能影响答案的点，只需要对他们分别验证就可以了。从dalao的代码里学到了lca也可以作为线段树维护的变量。。。 继续阅读“[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E”
[线段树+][并查集][区间信息维护] UVALive 4730 Kingdom
利用并查集处理合并，并保存每个块对应的覆盖范围(在y轴上的)上下界；利用线段树（更新区间的范围从并查集维护的信息中得到）维护每个x.5的点对应的州数和城市数。区间修改单点查询，只要确定好x.5这些点在线段树中的对应的下标就可以了，我这里是x.5在线段树中下标为(x+1)。由于我写的是1-n的线段树写完了才发现题目说的0-n-1，只能把读进来的东西都++。具体的操作：对于road，先找两个点是否在一个块里，如果是了那就不用任何操作（画图可以看出来如果这俩是一个块里的那么他们覆盖范围之间一定已经有线了），否则先把这两个的分别的块对应的区域在线段树中减去他的影响，再将两个块合并之后，再在线段树中加上这一新块的影响。先减后加，这样就可以避免繁杂的分类讨论了。。。
第一版正经的线段树ac之后想了想感觉在这个情境下只需要保证叶子节点的信息有效就行了，推了一下感觉可以去掉maintain的操作。。。试了下果然可以，而且快了很多，在vjudge上已经是用线段树的跑的最快的了（前几名都是用的BIT emmm
wa的点：本来一气呵成写完很舒服但是没想到出了很多bug，因为一些愚蠢的bug调试了很久。。。。数据结构这块还是太弱了。
继续阅读“[线段树+][并查集][区间信息维护] UVALive 4730 Kingdom”
[CF][补题][线段树][树] codeforces 1076E Vasya and a Tree
这个题自己当时主要还是思维限制，只想着怎么能有类似于dfs序线段树那种操作，或者是就某个点对他的子树做一个什么类似于线段树的打标记处理。。但是感觉太复杂了，没搞出来，而且也没有把可以离线这个点利用起来，还是too young
正解是在dfs过程中维护一个线段树，这棵树的下标是代表了当前dfs到的深度（而非节点），看到这儿就感觉是个很妙的操作，这样的话只需要每次进入到一个节点的时候把对应的属于该节点的所有的操作（这个需要离线处理，把对应的操作存用个vector存起来就可以了）都处理一遍，也就是把对应的所有的区间上的数值加上，dfs离开的时候把对应的区间上的数值减去，回滚一下，就可以保证在dfs过程中就把所有的操作处理完了。
[线段树][字符串hash][假算法] bzoj2124 等差子序列
这个题在codeforces上有几乎一模一样的：http://codeforces.com/contest/452/problem/F
cf上的题说的是考虑长度为3的等差序列，bzoj这个说的是等差序列其实也是找长度为3的，因为显然能找到长度大于3的肯定也能找到等于3的。cf那个题有个假算法可以过掉所有数据，就是暴力枚举中点，然后往左右延伸的时候不超过5个就行。。之所以能这么做是因为这个题目要想构造出来NO的数据确实很难。。不过假算法依然是假算法。。
正解是每次出现过一个点之后把他在线段树上值变为1，然后求一个中点左右两边有没有相同的时候需要判断左右两边是不是完全一样，如果不是一定有解。这里判断的方法是hash。。。分别在两个线段树上维护正反两个方向的左右01字符串的hash值就可以了。
wa点：首先是对于这种多项式形式的线段树合并的时候要分三种情况，完全在左/完全在右/跨越中点；其次是跨越中间点的情况下一定要考虑清楚应该累加的数值是多少。。在这里是pw[mid-max(ql,l)]；最后是当ai==1和ai==n时候的特判，这时候不能query，但是必须update，我一开始写了单独处理1，然后i从2开始循环，后来忽然意识到a1并不一定等于1啊。。。傻了。。。
[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array
http://codeforces.com/contest/1042/problem/D
嗯，大概是发现了自己以前一直没有正确理解mergesort。。。。
vp时候发现一开始这个题目过的人竟然比C多然后就提前去看了，但是竟然并没想出来正解emmmmmm，想过分治但是不知道怎么在线性合并左右段，看了前排dalao代码恍然大悟，其实就是逆序数的推广，这里把前缀和当成要处理的对象即可，如果是逆序数的话就是输出来一个数字右边有多少个比他大的，这里的话是sum[i]的右边有多少个比sum[i]+t小的，而t是常数所以其实几乎和逆序数一样。。如果仔细考虑逆序数的分治算法的话，会发现他能保证合并的时候线性是因为每次左右两边都是排好序的，这样的话就可以线性合并，而为什么排序这个操作不会影响到结果呢？因为在合并的时候左右两边各自的结果已经被计算过了，需要计算的仅仅是跨越中点的那些lr对！而这些计算和左右两边各自的顺序没有关系，只要保证左边的在左边右边的在右边就行了：因为我们是计算合法的数量，只要存在就+1，跟他什么时候存在早存在晚存在没关系。 继续阅读“[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array”