【uoj#46】 [清华集训2014] 玄学

题目传送门：uoj46

题意简述：要求在序列上维护一个操作间支持结合律的区间操作，查询连续一段时间内的操作对单点的作用效果，\(n \leq 10^5,m \leq 6 \times 10^5\)。

刚开始看到这道题的时候想到树套树，然而需要用到的空间太大，时间复杂度无法承受，再一看有8s的时限，就试着强行对操作分块，看看能不能\(O(m \sqrt m)\)卡过去，不过极限数据下再怎么优化也要10s，卡不过去。

正解可以用二进制分组的思想，对操作序列维护一棵线段树，每个结点维护子树内的操作对序列每个元素的影响（相邻两个元素的影响相同合并成一个区间表示）。然而不同于普通线段树的是，该线段树仅在左右儿子都塞满操作的时候才更新父节点的信息，这样每个结点只会被更新一次。在更新父节点的时候，可以归并地把左右儿子的信息叠加，可以证明这样的修改复杂度均摊是\(O(m\log m)\)的。查询时可以把查询的时间区间分割到线段树的\(\log m\)个结点上，然后在在这些结点上二分查找待查询点的操作效果。总时间复杂度\(O(m\log^2m)\)，但实际上常数较小，能很快通过极限数据。

代码：

uoj46

```cpp
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 100010
#define maxm 600010
inline ll read()
{
ll x=0; char c=getchar(),f=1;
for(;cseq;
int full;
}sgt[4*maxm];
void merge(std::vector&a,std::vector&b,std::vector&ret)
{
int sza=a.size(),szb=b.size(),pa=0,pb=0;
a.push_back((Data){n+1,n+1,one}); b.push_back((Data){n+1,n+1,one});
ret.clear();
while(pa1)sgt[now].seq.push_back((Data){1,x-1,one});
sgt[now].seq.push_back((Data){x,y,k});
if(y>1;
if(!sgt[now&a,int pos)
{
int l=0,r=a.size()-1;
while(l>1;
if(a[mid].r>1;
Opt cur=one;
if(x

巴特西

【uoj#46】 [清华集训2014] 玄学

最新文章

热门文章