数据结构训练

· · 个人记录

Mivik的神力

这个题如果用裸的线段树板子，会发现时间复杂度比暴力多一个log。题解里面提出了三种不同的用线段树来维护的方法，但感觉码量大，细节多，难以维护。

此时看到出题人的思路，算是拓宽了我对于此类问题的思考与切入角度吧。

可以发现，实际上不是所有的数都是有价值的。如果当前的数比前面的数要小，那么当访问的左端点在这个数前面的时候，访问这个数是没有意义的，可以直接跳过。依照这个原则，我们可以把遍历一个完整的区间变成访问几个有意义的节点，把一个区间转化成一条链，在这条链上来进行操作。

当然，这个还不是最优的。最坏情况下这种做法也是线性的，一个严格单调递增的序列就可以轻松卡掉。因此我们搞一个倍增。

我们维护一个类似于st表的东西，用nxt表示我们下一个能够产生作用的数组的编号。这个过程类似于倍增LCA。在倍增的同时，我们顺手把答案计算一下，这样就是O(1)查询，O(nlogn)的预处理了（勉强蹭过去）

先辈

这道恶臭无比的题在题面上疯狂搞你。当你手模一遍发现，实际上就是让你用线段树维护区间加然后判断区间是否单调。可以参考小白逛公园那道题，但难度要远远低于那道题

还有，屑题卡int

语文——理理思维

刚开始看到这道题，感觉就是一个十分显然的二维线段树+区间覆盖。当时在好奇为啥会是紫题，结果受教育了……

这道题最值得总结的两点吧：

  1. 不要指望自己可以短时间内调出大数据结构，遇到奇奇怪怪的问题不妨代码重构

  2. 在代码功能类似的情况下，优先选择码量小且符合自己习惯的代码

通过这个题算是学到了两点

第一点是二维线段树的一种写法，下面直接给出代码

struct Tree{
    struct node{
        int l,r,sum,lz;
        bool f;
    }tree[N*4];
    void pushup(int id)
    {
        tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
    }
    void pushdown(int id)
    {
        if(!tree[id].f)return;
        int mid=(tree[id].l+tree[id].r)/2;
        tree[id*2].f=tree[id*2+1].f=1;
        tree[id*2].lz=tree[id*2+1].lz=tree[id].lz;
        tree[id*2].sum=(mid-tree[id].l+1)*tree[id].lz;
        tree[id*2+1].sum=(tree[id].r-mid)*tree[id].lz;
        tree[id].f=0;
    }
    void build(int id,int l,int r,char qwq)
    {
        tree[id].l=l;tree[id].r=r;
        if(l==r)
        {
            if(qwq==s[l-1])tree[id].sum=1;
            return;
        }
        int mid=(l+r)/2;
        build(id*2,l,mid,qwq);
        build(id*2+1,mid+1,r,qwq);
        pushup(id);
    }
    void make(int id,int l,int r,int k)
    {
        if(tree[id].lz==k&&tree[id].f)return;
        if(l<=tree[id].l&&tree[id].r<=r)
        {
            tree[id].f=1;
            tree[id].lz=k;
            tree[id].sum=k*(tree[id].r-tree[id].l+1);
            return;
        }
        pushdown(id);
        int mid=(tree[id].l+tree[id].r)/2;
        if(l<=mid)make(id*2,l,r,k);
        if(r>mid)make(id*2+1,l,r,k);
        pushup(id);
    }
    int find(int id,int l,int r)
    {
        if(!tree[id].sum)return 0;
        if(l<=tree[id].l&&tree[id].r<=r)return tree[id].sum;
        int mid=(tree[id].l+tree[id].r)/2;
        int sum=0;
        pushdown(id);
        if(l<=mid)sum+=find(id*2,l,r);
        if(r>mid)sum+=find(id*2+1,l,r);
        return sum;
    }
}T[200];

这样写相当于直接封装好了，调用时比较方便

第二个就是，关于区间覆盖问题时的剪枝

  1. 区间覆盖时待操作区间的lazy tag与即将进行的操作相同，可以不进行当前操作

  2. 区间求和时，发现当前区间的sum为0，直接返回0

两个剪枝的使用可以大幅提高运行速度

还有，别忘了及时写pushup和pushdown（不知道为啥最近总是忘写）

避难所

本题需要维护两个操作

  1. 修改一个点的点权
  2. 将该点的状态进行改变。如果被封锁，则其子树所有节点的值求和时不必进行计算。如果解封，需要进行计算

本题的一个难点在于如何封锁一棵子树后又再次解封

实际上，我们可以维护从当前节点到根节点一共有多少节点被封锁了。如果存在节点被封锁，那么求和时就不需要计算该节点的值

为了方便维护，我们直接维护区间被封锁的节点的数目的最小值

注意，线段树在维护区间sum的时候的pushup函数有所改变。如果线段树左右子树的最小值相等，说明左右子树维护的区间内都没有被封锁的节点，直接正常计算计算就可以，反之，sum就等于数量较少的那部分的和

CODE;

void pushup(int id)
{
    if(tree[id<<1].minx==tree[id<<1|1].minx)
        tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
    else if(tree[id<<1].minx>tree[id<<1|1].minx)
        tree[id].sum=tree[id<<1|1].sum;
    else tree[id].sum=tree[id<<1].sum;
    tree[id].minx=min(tree[id<<1].minx,tree[id<<1|1].minx);
}

长时间不写数据结构题有点手生了，这个题的这个思路也是比较清晰的，不过对于封锁后又解封这个操作维护起来不是很方便，这也是本题的难点。本题相当于是拓展一下思路吧