精华内容
下载资源
问答
  • 线段树合并

    2021-01-23 17:10:55
    线段树合并 略谈 线段树合并说全来就是动态开点权值线段树合并,所以你需要掌握权值线段树的基本知识以及知道什么是动态开点 对于两个普通权值线段树如果暴力合并的话复杂度将会是nlog⁡nn \log nnlogn,更别说是...

    线段树合并

    略谈

    线段树合并说全来就是动态开点权值线段树合并,所以你需要掌握权值线段树的基本知识以及知道什么是动态开点

    对于两个普通权值线段树如果暴力合并的话复杂度将会是 n log ⁡ n n \log n nlogn,更别说是合并 n n n棵权值线段树了(炸空间,炸内存),但是在动态开点权值线段树中,这一操作是可以优化为 log ⁡ n \log n logn的。

    具体处理如下:

    当这两棵树中有一个已经是空的了,我们只需要把有权值的一部分返回即可。

    当合并进行到叶子节点了,我们就需要对叶子节点的权值进行累加,然后再返回。

    如果不是上述的两种情况,我们就只需要递归分别处理左右儿子即可。

    int merge(int x, int y, int l, int r) {
    	if (!x || !y) {
    		return x | y;
    	}
    	if (l == r) {
    		maxv[x] += maxv[y];
    		return x;
    	}
    	int mid = l + r >> 1;
    	ls[x] = merge(ls[x], ls[y], l, mid);
    	rs[x] = merge(rs[x], rs[y], mid + 1, r);
      push_up(x);
      return x;
    }
    

    下面是一些线段树合并的题目。

    P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

    由于修改是修改树上的一段,我们可以利用树上差分来实现操作,最后统计数量最多的点。

    注意输出的时候一定要特判 m a x v [ r t ] = = 0 maxv[rt] == 0 maxv[rt]==0,不能直接写 a n s [ r t ] = m a x p [ r t ] ans[rt] = maxp[rt] ans[rt]=maxp[rt]

    因为在树上差分的时候,我们可能会对某些节点进行了不必要的操作,这个时候会有 m a x p [ r t ] maxp[rt] maxp[rt]的错误记录。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int head[N], to[N << 1], nex[N << 1], cnt = 1;
    
    int n, m, tot, num, root[N], sz[N], fa[N], top[N], dep[N], son[N], ans[N];
    
    int ls[N * 60], rs[N * 60], maxv[N * 60], maxp[N * 60];
    
    void add(int x, int y) {
      to[cnt] = y;
      nex[cnt] = head[x];
      head[x] = cnt++;
    }
    
    void dfs1(int rt, int f) {
      fa[rt] = f, dep[rt] = dep[f] + 1, sz[rt] = 1;
      for (int i = head[rt]; i; i = nex[i]) {
        if (to[i] == f) {
          continue;
        }
        dfs1(to[i], rt);
        sz[rt] += sz[to[i]];
        if (!son[rt] || sz[to[i]] > sz[son[rt]]) {
          son[rt] = to[i];
        }
      }
    }
    
    void dfs2(int rt, int tp) {
      top[rt] = tp;
      if (!son[rt]) {
        return ;
      }
      dfs2(son[rt], tp);
      for (int i = head[rt]; i; i = nex[i]) {
        if (to[i] == fa[rt] || to[i] == son[rt]) {
          continue;
        }
        dfs2(to[i], to[i]);
      }
    }
    
    int lca(int x, int y) {
      while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
          swap(x, y);
        }
        x = fa[top[x]];
      }
      return dep[x] < dep[y] ? x : y;
    }
    
    void push_up(int rt) {
      if (maxv[ls[rt]] >= maxv[rs[rt]]) {
        maxv[rt] = maxv[ls[rt]];
        maxp[rt] = maxp[ls[rt]];
      }
      else {
        maxv[rt] = maxv[rs[rt]];
        maxp[rt] = maxp[rs[rt]];
      }
    }
    
    void update(int &rt, int l, int r, int x, int value) {
      if (!rt) {
        rt = ++num;
      }
      if (l == r) {
        maxv[rt] += value;
        maxp[rt] = l;
        return ;
      }
      int mid = l + r >> 1;
      if (x <= mid) {
        update(ls[rt], l, mid, x, value);
      }
      if (x > mid) {
        update(rs[rt], mid + 1, r, x, value);
      }
      push_up(rt);
    }
    
    int merge(int x, int y, int l, int r) {
    	if (!x || !y) {
    		return x | y;
    	}
    	if (l == r) {
    		maxv[x] += maxv[y];
    		return x;
    	}
    	int mid = l + r >> 1;
    	ls[x] = merge(ls[x], ls[y], l, mid);
    	rs[x] = merge(rs[x], rs[y], mid + 1, r);
      push_up(x);
      return x;
    }
    
    void dfs(int rt, int fa) {
      for (int i = head[rt]; i; i = nex[i]) {
        if (to[i] == fa) {
          continue;
        }
        dfs(to[i], rt);
        root[rt] = merge(root[rt], root[to[i]], 1, 100000);
      }
      if (maxv[root[rt]] == 0) {
        ans[rt] = 0;
      }
      else {
        ans[rt] = maxp[root[rt]];
      }
    }
    
    int main() {
      // freopen("in.txt", "r", stdin);
      // freopen("out.txt", "w", stdout);
      // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
      scanf("%d %d", &n, &m);
      for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        add(x, y); 
        add(y, x);
      }
      dfs1(1, 0);
      dfs2(1, 1);
      for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        int f = lca(x, y), ff = fa[f];
        update(root[x], 1, 100000, z, 1);
        update(root[y], 1, 100000, z, 1);
        update(root[f], 1, 100000, z, -1);
        if (ff) {
          update(root[ff], 1, 100000, z, -1);
        }
      }
      dfs(1, 0);
      for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i]);
      }
      return 0;
    }
    

    E. Lomsat gelral

    这题最简单的做法应该是 d s u   o n   t r e e dsu\ on\ tree dsu on tree,但是线段树合并同样也具有优秀的复杂度,可以来完成这一题。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 1e5 + 10;
    
    int head[N], to[N << 1], nex[N << 1], cnt = 1;
    
    int n, tot, value[N], root[N];
    
    int ls[N * 60], rs[N * 60], maxn[N * 60];
    
    ll ans[N], sum[N * 60];
    
    void push_up(int rt) {
      if (maxn[ls[rt]] > maxn[rs[rt]]) {
        maxn[rt] = maxn[ls[rt]];
        sum[rt] = sum[ls[rt]];
      }
      else if (maxn[rs[rt]] > maxn[ls[rt]]) {
        maxn[rt] = maxn[rs[rt]];
        sum[rt] = sum[rs[rt]];
      }
      else {
        maxn[rt] = maxn[ls[rt]];
        sum[rt] = sum[ls[rt]] + sum[rs[rt]];
      }
    }
    
    void update(int &rt, int l, int r, int x, int value) {
      if (!rt) {
        rt = ++tot;
      }
      if (l == r) {
        maxn[rt] += value;
        sum[rt] = x;
        return ;
      }
      int mid = l + r >> 1;
      if (x <= mid) {
        update(ls[rt], l, mid, x, value);
      }
      else {
        update(rs[rt], mid + 1, r, x, value);
      }
      push_up(rt);
    }
    
    int merge(int x, int y, int l, int r) {
      if (x == 0 || y == 0) {
        return x | y;
      }
      if (l == r) {
        maxn[x] += maxn[y];
        return x;
      }
      int mid = l + r >> 1;
      ls[x] = merge(ls[x], ls[y], l, mid);
      rs[x] = merge(rs[x], rs[y], mid + 1, r);
      push_up(x);
      return x;
    }
    
    void dfs(int rt, int fa) {
      for (int i = head[rt]; i; i = nex[i]) {
        if (to[i] == fa) {
          continue;
        }
        dfs(to[i], rt);
        root[rt] = merge(root[rt], root[to[i]], 1, n);
      }
      update(root[rt], 1, n, value[rt], 1);
      ans[rt] = sum[root[rt]];
    }
    
    void add(int x, int y) {
      to[cnt] = y;
      nex[cnt] = head[x];
      head[x] = cnt++;
    }
    
    int main() {
      // freopen("in.txt", "r", stdin);
      // freopen("out.txt", "w", stdout);
      // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
      scanf("%d", &n);
      for (int i = 1; i <= n; i++) {
        scanf("%d", &value[i]);
      }
      for (int x, y, i = 1; i < n; i++) {
        scanf("%d %d", &x, &y);
        add(x, y);
        add(y, x);
      }
      dfs(1, 0);
      for (int i = 1; i <= n; i++) {
        printf("%lld%c", ans[i], i == n ? '\n' : ' ');
      }
      return 0;
    }
    

    P3224 [HNOI2012]永无乡

    并查集,加权值线段树上区间查找第 k k k大,只不过是并查集要用线段树合并来维护信息,然后把查找第 k k k大放到了动态开点线段树上。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int n, m, fa[N], value[N];
    
    int tot, root[N], ls[N * 60], rs[N * 60], sum[N * 60];
    
    int find(int rt) {
      return fa[rt] == rt ? rt : fa[rt] = find(fa[rt]);
    }
    
    void push_up(int rt) {
      sum[rt] = sum[ls[rt]] + sum[rs[rt]];
    }
    
    void update(int &rt, int l, int r, int x, int value) {
      if (!rt) {
        rt = ++tot;
      }
      if (l == r) {
        sum[rt] += value;
        return ;
      }
      int mid = l + r >> 1;
      if (x <= mid) {
        update(ls[rt], l, mid, x, value);
      }
      if (x > mid) {
        update(rs[rt], mid + 1, r, x, value);
      }
      push_up(rt);
    }
    
    int merge(int x, int y, int l, int r) {
      if (x == 0 || y == 0) {
        return x | y;
      }
      if (l == r) {
        sum[x] += sum[y];
        return x;
      }
      int mid = l + r >> 1;
      ls[x] = merge(ls[x], ls[y], l, mid);
      rs[x] = merge(rs[x], rs[y], mid + 1, r);
      push_up(x);
      return x;
    }
    
    int find_k_th(int rt, int l, int r, int k) {
      if (sum[rt] < k) {
        return 0;
      }
      if (l == r) {
        return l;
      }
      int mid = l + r >> 1;
      if (k > sum[ls[rt]]) {
        return find_k_th(rs[rt], mid + 1, r, k - sum[ls[rt]]);
      }
      return find_k_th(ls[rt], l, mid, k);
    }
    
    int main() {
      // freopen("in.txt", "r", stdin);
      // freopen("out.txt", "w", stdout);
      // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
      scanf("%d %d", &n, &m);
      for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        value[x] = i;
        update(root[i], 1, n, x, 1);
        fa[i] = i;
      }
      for (int i = 1, x, y; i <= m; i++) {
        scanf("%d %d", &x, &y);
        int fx = find(x), fy = find(y);
        if (fx != fy) {
          fa[fx] = fy;
          root[fy] = merge(root[fy], root[fx], 1, n);
        }
      }
      value[0] = -1;
      scanf("%d", &m);
      char op[10];
      for (int i = 1, x, y; i <= m; i++) {
        scanf("%s %d %d", op, &x, &y);
        if (op[0] == 'Q') {
          printf("%d\n", value[find_k_th(root[find(x)], 1, n, y)]);
        }
        else {
          int fx = find(x), fy = find(y);
          if (fx != fy) {
            fa[fx] = fy;
            root[fy] = merge(root[fy], root[fx], 1, n);
          }
        }
      }
      return 0;
    }
    

    P3521 [POI2011]ROT-Tree Rotations

    逆序对的统计分成了三种

    一、在左儿子上。

    二、在右儿子上。

    三、左右儿子互相产生的。

    递归处理,先处理左儿子的逆序对,再处理右儿子的逆序对,这里已经处理好了(一、二)两种情况了,接下来只要处理第三种。

    不管左右儿子如何交换,是不会影响(一、二)种情况的逆序对的产生,座所以只要记录第三种情况的最小值,然后累加到答案上即可。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 6e6 + 10;
    
    int ls[N], rs[N], value[N], tot, n;
    
    ll ans, ans1, ans2;
    
    void push_up(int rt) {
      value[rt] = value[ls[rt]] + value[rs[rt]];
    }
    
    void update(int &rt, int l, int r, int x, int w) {
      if (!rt) {
        rt = ++tot;
      }
      if (l == r) {
        value[rt] += w;
        return ;
      }
      int mid = l + r >> 1;
      if (x <= mid) {
        update(ls[rt], l, mid, x, w);
      }
      else {
        update(rs[rt], mid + 1, r, x, w);
      }
      push_up(rt);
    }
    
    int merge(int x, int y, int l, int r) {
      if (x == 0 || y == 0) {
        return x | y;
      }
      if (l == r) {
        value[x] += value[y];
        return x;
      }
      ans1 += 1ll * value[ls[x]] * value[rs[y]];
      ans2 += 1ll * value[ls[y]] * value[rs[x]];
      int mid = l + r >> 1;
      ls[x] = merge(ls[x], ls[y], l, mid);
      rs[x] = merge(rs[x], rs[y], mid + 1, r);
      push_up(x);
      return x;
    }
    
    void dfs(int &x) {
      int cur, ls, rs;
      x = 0;
      scanf("%d", &cur);
      if (!cur) {
        dfs(ls), dfs(rs);
        ans1 = ans2 = 0;
        x = merge(ls, rs, 1, n);
        ans += min(ans1, ans2);
      }
      else {
        update(x, 1, n, cur, 1);
      }
    }
    
    int main() {
      // freopen("in.txt", "r", stdin);
      // freopen("out.txt", "w", stdout);
      // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
      scanf("%d", &n);
      int rt = 0;
      dfs(rt);
      printf("%lld\n", ans);
      return 0;
    }
    
    展开全文
  • 普通线段树 基于将区间拆分为$O(logn)$区间的并这一思想来实现。其中附加信息的维护方式变化很灵活。 区间加。利用懒标记直接维护。 区间加&区间乘。两个懒标记同时维护,其中乘法更新要带动加法更新。 ...

    普通线段树

    基于将区间拆分为$O(logn)$区间的并这一思想来实现。其中附加信息的维护方式变化很灵活。

    • 区间加。利用懒标记直接维护。
    • 区间加&区间乘。两个懒标记同时维护,其中乘法更新要带动加法更新。
    • 区间染色。一个懒标记直接覆盖即可。
    • 区间gcd。
    • 树上。有点类似树剖,直接利用DFS序转化为线性,然后普通维护就好了。
    • 维护最小值的位置。query函数的类型作为结构体,每次返回最小值及其位置。
    • 利用取模之后缩小一半的性质,一个数$a$最多被模$loga$次。因此暴力做即可。还要需要维护最大值判断不用取模的情况。

    Codeforces 292 E. Copying Data

    给出两个序列$a,b$。动态对$b$进行修改,修改操作是指定$a$的一段区间$[x,x+k]$,粘贴到$b$的$[y,y+k]$上。单点询问$b$。

    如果我们知道某一个位置最后一次是被哪一次操作覆盖的,那么就可以知道这个位置对应的值。

    由此问题转化为求解某一个位置最后一次被哪个操作覆盖。这显然是一个区间赋值(染色)问题。利用线段树维护——只需要用懒标记强行覆盖即可。

    Codeforces 914 D. Bash and a Tough Math Puzzle

    给出一个序列。动态单点更新。每次询问一段区间,并给出一个数字$x$。问能不能通过修改区间内的一个数字,使区间的$gcd=x$。

    这道题告诉我gcd也是满足区间性质的。假如一段区间内所有数都是$x$的倍数,那么我可以将其中一个修改为$x$使得所有数的$gcd$为$x$;假如一段区间内只有一个数不是$x$的倍数,那么我可以将那个数修改为$x$使得所有数的$gcd$为$x$;假如一个区间内有超过一个数不是$x$倍数则无解。由此解决这个问题只需要统计区间内有多少个数不是$x$的倍数即可。

    我们可以像维护区间和一样来维护区间$gcd$。如果一个区间的$gcd$是$x$的倍数,意味着这里面全是$x$的倍数;否则,继续深究,如果到达叶节点那么直接判断并返回。注意,这样的做法违背了线段树$O(logn)$查询的原则,所以需要做一些优化——一旦总数超过1就跳出。复杂度玄学。

    Codeforces 877 E. Danil and a Part-time Job

    给出一棵树,点权为bool。动态询问子树和,同时会对点权进行修改。修改的规则是:选择一棵子树$v$,子树中所有节点的点权都异或1。

    用DFS序将问题转化为线性。然后考虑如何完成取反操作。很像Splay里面的那个区间翻转操作,因此我们的标记的更新时异或1即可。然后将总和与总数作差即可。

    Codeforces 383 C. Propagating tree

    给出一棵树,有点权,动态查询子树和。其中会对点权进行修改,修改的规则是:选择一颗子树$v$,给$v$这个点+k,$v$的直接儿子-k,$v$的孙子+k……以此类推。

    首先利用树的DFS序转化为线性问题。关键在于分层有正负的问题。虽然哪一层正哪一层负不确定,但是相对正负关系一定是确定的。我们可以假设奇数层为正,偶数层为负。假设偶数层要更新为正,则更新一个负数。最后统计的时候依然按照奇数正偶数负的方式来统计就能得到正确答案。这种思想感觉还是很神奇很重要的。

    树的深度统计是要放在递归之前做的,这里我写挂了。

    Codeforces 438 D. The Child and Sequence

    给出一个序列$a_i$($n \leq 10^5, a_i \leq 1e9$),动态询问区间和,单点修改,修改操作是区间取模。

    区间取模貌似不能直接维护。事实上我们可以暴力,加上一点小小的优化。假设我们要让一段区间对$P$取模。那么如果区间内的最大值小于$P$,那么可忽略此操作。另外我们发现,一个数取模以后至少缩小一半。由此$a_i$最多被模$loga_i$次。由此,复杂度近似是$O(nlognlog1e9)$。

    取模之后缩小一半的性质证明:设$a%b=c$,其中$a>b>c$。可表示为$a=kb+c$,其中$k\geq 1$。因为$b>c,k \geq 1$,所以$kb>c$。所以$a>2c$

     


    主席树

    单点更新仅产生$O(logn)$个点。故复杂度为$O(mlogn)$

    (一)维护区间第$k$小。通过维护区间内每个数的出现次数,然后在线段树上二分实现。所谓区间,就是指两个历史版本的差。这里利用了前缀和的思想。

    (二)维护树上路径上的第$k$小。转化为路径上每个数的出现次数。利用树上差分的思想。

    Codeforces 961 E. Tufurama

    给出一个序列$a_i$($a_i \leq 1e9$),问有多少对$(x,y)$满足$a_x \geq y$且$a_y \geq x$。其中$1 \leq x<y \leq n$

    对于每一个$y$,考虑$x∈[1,y-1]$。那么$x$要满足的条件有$x \leq a_y$,$a_x \geq y$。由前者结合前提可得$x∈[1,min\{y-1,a_y\}]$。

    至此,问题转化为求解$x∈[1,min\{y-1,a_y\}]$里,$a_x \geq y$的$x$个数。这是一个求解区间大于$k$的个数问题,利用主席树解决即可。注意需要离散化,细节很多。

     


    一类特殊的出现次数问题

    Codeforces 813 E. Army Creation

    给出一个序列$a_i$($n,a_i \leq 10^5$),动态询问区间内元素的最大个数,满足相同元素不超过$k$个。

    不能维护每个元素出现次数,这样的话非常难$log(n)$统计答案。这里有一个巧妙的转化:预处理出$a_i$之后的第$k$个元素的位置,记为$b_i$。如果$b_i \leq r$,那么就不选$a_i$;如果$b_i > r$,那么就选。这样很巧妙地限制了一段区间内我们最多只取靠后的$k$个相同元素。因此我们利用$b_i$建立主席树,问题转化为求解区间内大于$r$的元素个数,相当于求$(r,+\infty)$的区间和。

    luogu 1972 HH的项链

    给出一个序列$a_i$($n,a_i \leq 5·10^5$),动态询问区间不同的元素个数。

    容易发现这就是上面那题$k=1$的特殊情况。理论上直接主席树解决即可。

    但我们考虑一种线段树的离线做法。对于一个区间的右边界,如果我们只统计每种元素最靠近右边界的那个位置,就不会重复了,这样区间和就是不同元素的个数了。我们可以这样解决:预处理出与$a_i$相等的元素上一次出现的位置$las_i$。将所有询问区间按照右端点排序,用线段树维护每个位置,0表示不算,1表示算。右端点往右扩展时,碰到的这个数如果之前出现过,就在先前那个位置将1改为0。这样就保证了只统计最靠后的。

    Codeforces 1000 F. One Occurrence

    给出一个序列$a_i$($n,a_i \leq 5·10^5$),动态询问一个区间内只出现一次的数(多解可任意)。

    考虑线段树离线(或主席树)。我们同样只考虑最靠近右边界的,对于这样的$a_i$,如果上一次出现的位置$<L$,那么它一定只出现一次。于是我们只需要记录每个位置上的数的上一次出现位置,用线段树维护最小值以及最小值的位置即可。

    Codeforces 833 B. Bakery

    给出一个序列$a_i$($n,a_i \leq 35000$),要求把序列划分为$k$段($k \leq 50$),每段的价值为其中不同的数的个数。求最大总价值。

    明显是一个划分DP的模型。有$dp_{i,j}=max\{dp_{k,j-1}+distinct(k+1,i)\}$。直接转移需要枚举$k$,复杂度就是$O(kn^2)$级别的。因此需要考虑别的方法。

    考虑已知$dp_{k,j-1}$,要考虑它对转移的贡献就是要求出所有的$distinct(k+1,i)$。考虑对于区间$(k,i]$内的一个位置$p$能不能对它产生贡献——一种数值的数最多只能产生一个贡献,不如规定最左侧的数产生贡献。这就让我们联想到去维护一个$pre_p$,我们只考虑$pre_p \leq k$的位置。针对这种问题,我们让每一个$p$去覆盖区间$[pre_p,p)$。于是位置$k$被覆盖了几次就代表了$distinct(k+1,i)$。用线段树维护区间修改和最大值查询即可。

     

    总结

    这类要维护区间内出现了多少个不同的数的问题,我们的处理方法都是:对于重复的元素,只看其中一个。或是最左侧的,或是最右侧的。判断最左最右的方法就是维护一个$pre$或者$nxt$数组。线段树维护的一般是位置,附加值表示这个位置算不算或者总共被后面覆盖几次之类的。

     


    可持久化数组

    可通过主席树来维护。数组就是主席树的叶节点,上面那些节点其实是不存放附加信息的。

     

     


    线段树合并

    在树上要求解各子树的答案时,并且用线段树维护时,要合并子树的信息来得到整个树的信息,这时就要用到线段树合并。

    线段树合并的思想很简单,就是合并。考虑到空间的限制,要求动态开点(时空复杂度$O(n \log n)$)

    当合并根节点为$a,b$的两个线段树时,有两种代码实现的方法。一种是直接将合并后的结果放在$a$上,一种是每次合并新开一个节点作为新的根。对于题目仅仅要我们输出一次每个节点的答案时,可以使用第一种方法,因为我们不需要历史信息。而如果题目是在线的多次询问,那么此时显然需要利用到历史信息的,此时就要选择方法二了。因为第一种方法我们会在合并的时候直接继承某一个子树,这样在modify操作的时候就会直接影响到历史的线段树导致答案错误了。

    Codeforces 600 E. Lomsat gelral

    给出一颗树,每个节点有一个颜色。询问每个子树内颜色数量最多的那些颜色的总和(颜色的值)

    用线段树维护最大值,再附加维护所有最大值的颜色总和。线段树合并即可。

    luogu 3605 Promotion Counting

    给出一颗树,每个点有一个权值。询问每个节点,其所有子树内的节点中权值比它大的节点个数。

    离散化后,权值线段树维护和,线段树合并即可。

    luogu 3899 谈笑风生

    给出一棵树,每次询问一个$a$节点,问有多少个有序数对$(a,b,c)$,满足$a,b$都是$c$的祖先,且$a,b$之间距离不超过$k$

    显然要用线段树来维护某一个深度的节点,关键是维护什么?我们发现应该维护每个深度的$size$,这样才可以直接计算答案。因为题目是在线询问的,所以每一次合并的时候要开点。

     

    转载于:https://www.cnblogs.com/qixingzhi/p/10936540.html

    展开全文
  • 摘抄自 styx的博客 ...所以不是所有情况下的线段树合并都是 O(nlog⁡n)O(n \log n)O(nlogn) 的。 一般情况下我们只会对每个节点开动态开一条链,所以 N=nlog⁡nN=n\log nN=nlogn ,复杂度才会是 O(nlog⁡n)O(...

    摘抄自 styx的博客

    假如初始所有的线段树点数总和为 N N N 。因为只要合并两个节点,节点总个数就会少掉一个,所以复杂度应该是 O ( N ) O(N) O(N) 的。

    所以不是所有情况下的线段树合并都是 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的。

    一般情况下我们只会对每个节点开动态开一条链,所以 N = n log ⁡ n N=n\log n N=nlogn ,复杂度才会是 O ( n log ⁡ n ) O(n \log n) O(nlogn)

    展开全文
  • 这题两种主流的做法: 1.线段树合并,用set维护树的根结点。合并的时候直接暴力遍历set容器,合并两棵树的复杂度是logn的,分裂

    这题两种主流的做法:

    1.线段树合并。复杂度mlogn

    2.二分+01线段树mlognlogn

    主要讲第一种吧。第一种更快。这里我们要巧妙地运用线段树的合并和分裂,一开始全都是只有一个叶子的n棵线段树,假如l到r需要排序,就把l到r合并了,讲升序和降序记录在左端点l。用set维护树根,一开始set里面有n个树根1~n,以及一个虚根n+1。树set[i]维护的区间set[i]~set[i+1]-1的信息

    假如set里面是 1 2 5 6 (n=5,6是虚根)

    那么就维护了三棵树1 2 5 分别维护 区间1~1,2~4,5~5的信息

    最开始set里面是 1 2 3 4 5 6 分别维护区间1~1,2~2,,,,5~5的信息

    假如有个操作是 0 2 4 把2~4升序排序 

    我们就暴力把3~4这些树合并到2上面  然后在2位置标记是升序还是降序   并且在set中删除根3 4

    就变成了 1 2 5 6 

    假如下一个操作是 1 3 4 显然在上一步我们把3~4并到2了  我们要用lower_bound去找到2 然后从2这棵树中把3,4分裂出来,由于2出的标记是升序(上一次操作标记的) 于是我们就把较大的两个数 分出去就行了 反之如果是降序标记 我们把较小的两个数分出去就行

    #include<bits/stdc++.h>
    using namespace std;
    #define R register int
    #define mid (l+r>>1)
    #define il inline
    typedef set<int>::iterator IT;
    int n,m;
    const int N = 1e5+10,M = 5e6+10;
    il int read(){
    	int w=0,x=0;char c=0;
    	while(c>'9'||c<'0') w|=c=='-',c=getchar();
    	while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    	return w?-x:x;
    }
    int ls[M],rs[M],s[M],tot,op[N],rt[N],mem[M],ct;
    set<int>srt;
    il int newnode(){
    	return ct?mem[ct--]:++tot;
    }
    il void del(R x){
    	mem[++ct]=x;s[x]=ls[x]=rs[x]=0;
    }
    void update(R &x,R l,R r,R pos){
    	if(!x) x=newnode();s[x]=1;
    	if(l==r) return;
    	if(pos<=mid) update(ls[x],l,mid,pos);
    	else update(rs[x],mid+1,r,pos);
    }
    int merge(R x,R y){
    	if(!x||!y) return x+y;
    	s[x]+=s[y];
    	ls[x]=merge(ls[x],ls[y]);
    	rs[x]=merge(rs[x],rs[y]);
    	del(y);
    	return x;
    }
    int query(R x,R l,R r){
    	if(l==r) return l;
    	if(ls[x]) return query(ls[x],l,mid);
    	else return query(rs[x],mid+1,r);
    }
    void split(R x,R &y,R k,R op){
    	if(s[x]==k) return;
    	s[y=newnode()]=s[x]-k,s[x]=k;
    	if(op){
    		if(k<=s[rs[x]]) split(rs[x],rs[y],k,op),swap(ls[x],ls[y]);
    		else split(ls[x],ls[y],k-s[rs[x]],op);
    	}else{
    		if(k<=s[ls[x]]) split(ls[x],ls[y],k,op),swap(rs[x],rs[y]);
    		else split(rs[x],rs[y],k-s[ls[x]],op);
    	} 
    }
    il IT spl(R x){
    	IT w = srt.lower_bound(x);
    	if(*w==x) return w;
    	--w;split(rt[*w],rt[x],x-*w,op[x]=op[*w]);
    	return srt.insert(x).first;
    }
    int main(){
    	n=read(),m=read();
    	srt.insert(n+1);
    	for(R i = 1; i <= n; i++){
    		R g;
    		g=read();
    		update(rt[i],1,n,g);
    		srt.insert(i);
    	}
    	for(R i = 1; i <= m; i++){
    		R o,l,r;
    		o=read(),l=read(),r=read();
    		IT IL=spl(l),IR=spl(r+1);
    		for(IT i=++IL;i!=IR;i++) rt[l]=merge(rt[l],rt[*i]);
    		op[l]=o;srt.erase(IL,IR);
    	}
    	R qp;
    	qp=read();
    	spl(qp),spl(qp+1);
    	printf("%d\n",query(rt[qp],1,n));
    	return 0;
    }

     

    展开全文
  • 性感理解线段树合并
  • 线段树合并:从入门到放弃

    千次阅读 2019-03-14 15:02:03
    线段树合并,就是指建立一颗新的线段树,保存原有的两颗线段树的信息。 那么就是: 假设现在合并到了线段树的a、b某一个pos 如果a在这个区间有pos,b没有,那么新的线段树pos位置赋值为a 如果b在这个区间有pos,a...
  • 对每个节点开一颗线段树,标程的写法很节省空间:预处理出每个数字的因数,对题目中给定的权值建线段树,如果子树区间中没有根节点权值的因数,那么直接剪掉。然后通过改变每个根节点左右孩子数组的值,来改变其指向...
  • 线段树分治 适用范围 对X的操作在一个时间段生效,询问一些时间点(或时间段)上的X的状态 核心操作 1.用时间段建一颗线段树,将操作放到对应的一些(或一个)结点上 2.遍历线段树,每进入一个节点就执行上面的操作...
  • 题目链接 题意: 给你一棵n个点的树,边的边权都是1。有q次询问,每次询问给一个a一个x,表示询问...这个题的做法好像很多,我在这里只介绍一种用线段树合并做的在线做法。 我们考虑告诉你了a之后,b和c会是怎么组...
  • 异或树-线段树合并

    2021-08-06 23:23:11
    由于这是一棵异或,所以,如果一个数出现了两次,那么这两个点的权值就消失了(点并没有消失,即的形态没有发生变化,只是在计算时忽略这两个点的权值。)消失过程发生在一次询问时,如果子树内两个点的权值一样...
  • 顾名思义,就是合并两个同构(就是维护的区间长度一样)线段树,其实也没啥比较nb的算法,就是一个一个...另外线段树合并还可以和线段树分裂一起构成维护一组线段树森林的方法 我们每次合并一个点,就是综合两个线段树表示...
  • 给定一颗有nnn个点的,有mmm个人在上移动,第iii个人从sis_isi​点,移动到tit_iti​点,且他们按照最短路移动,每秒移动一条边的距离, 点iii在wiw_iwi​时刻有一个观察员,我们需要对每个点统计,在wiw_iwi​...
  • 文章目录基操T1 板/[Vani有约会]雨天的尾巴 /【模板】线段树合并 基操 T1 板/[Vani有约会]雨天的尾巴 /【模板】线段树合并 Portkey 多次给树上路径上的点加一个数,求每个节点上加得最多的数 差分,然后加回来 普通...
  • 线段树合并 线段树合并,一般指两棵(亦可延伸为多棵)权值线段树之间进行横向地信息维护,比如将同一权值处的两个信息相加、取max之类的,最后得到了一棵新线段树。 为了节约空间,最好采用动态开点线段树。 关键...
  • 线段树合并暴力合并子树 #include<bits/stdc++.h> using namespace std; using ll=long long; constexpr int N=300010; int h[N],e[2*N],ne[2*N],idx; void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx...
  • 两个月前打了个主席树……今天又打了个线段树合并,发现线段树合并的代码挺短的……(其实也差不多) 主席树: #include #include #include #include #define maxn 100010 using namespace std; int A[maxn],b[maxn]...
  • 线段树合并模板
  • 题意:给你一棵n个节点的树,根为1,问你每个节点,它的子树中有几个节点比它大。...还有一个方法是对于每个节点建立一颗权值线段树,然后自底向上合并,每次合并后就可以直接查找比它大的数的个数,因

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,747
精华内容 9,098
关键字:

线段树合并