题意：
$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”
[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query
题意：
给定 $N$ 个数字， $Q$ 次询问，每次询问为查询下标在 $[l,r]$ 之间的所有数字中所有可能的子段的 $gcd$ 有多少种。$N,Q < 10^5 , a_i < 10^6$
题解：
首先一个重要的结论：以固定点为结尾的子段的 $gcd$ 种数不超过 $max(n,log(max(a_i)))$ 证明：每次往原有的序列里加入一个数字的话， $gcd$ 要么不变，要么至少变为原来的1/2，因此为指数级减小。
有了这个结论，我们可以试着来枚举一个端点考虑本题，不妨枚举每个段的右端点$r_j$ , 假设集合$S$表示以$r_{j-1}$ 为结尾的所有 $gcd$ ，那么要求出以$r_j$为结尾的所有 $gcd$ ，只需遍历S中的每个数字$d_k$，计算其与$a_j$ 的 $gcd$ ，放入新集合$S^{‘}$即可。这样的话我们可以得到一个空间为$O(nlogn)$的结果，表示以每个点为结尾的所有段的 $gcd$ 都是哪些数字。
现在来考虑查询。每次查询的话是要求出来$[l,r]$之间所有可能的 $gcd$ 。直接暴力不可取，由上面的结果可以试着考虑能否转化为前缀问题。可以发现，如果我们对所有的$[l,r]$离线处理，按$r$从小到大排序，并且按照这个顺序来调整已经遇到过的 $gcd$ 的信息的话，每次的查询只需要考虑有多少个 $gcd$ 出现的最右左端点大于等于l，这句话具体的意思是，一个 $gcd$ 可能出现过了很多次，不同的段都可以得到这个 $gcd$ ，但是我们只考虑这些段中左端点l_j最大的那个点$p_j$，这样的话如果$l<=p_j$那么可以确定$[l,r]$中一定有这个 $gcd$ （种类+1），这就就转化成了一个计数问题。 继续阅读“[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query”
[补题][线段树][权值区间离散化] 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”
[数据结构][带权并查集][异或] UVALive 4487 Exclusive-OR
一道不是那么传统的带权并查集
题目特殊的地方在于运算是异或，不是像经典的带权并查集那样可以有一个恒定的子节点与父结点的递推关系。比如传统的求一个结点到根结点的距离的并查集可以这样写
int findfat(int x)
{
if(fat[x] == x) return x;
int tmp=fat[x];
fat[x]=findfat(fat[x]);
//在此处修改val比如：
value[x]=value[tmp]+1;
return fat[x];
}
这样写的正确性在于这个递推关系一定是正确的，即使在森林里改变任意一个点的数值，在他的后代执行findfat的时候也一定能更新所有的数值。但是异或是不太一样的，如果直接写 value[x]=value[x]^value[tmp]，的话，仅仅是对x求两次查找根结点而不做任何其他操作就会使得数值出现错误，因为w[x]等于和自己又异或了一次，就会出现不正常的结果。
思考了一下，我直接把w数组定义为：w[i]表示 继续阅读“[数据结构][带权并查集][异或] UVALive 4487 Exclusive-OR”
[线段树+][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过程中就把所有的操作处理完了。