树状数组和线段树的应用

线段树的一些技巧

单点修改的写法

有单点修改操作时，使用map记录数组某个位置的点在线段树中的位置可以更快更好写地修改。

void build(int l, int r, int rt)
{
    if (l == r)
    {
        //...
        map[l] = rt;
        return;
    }
    //...
}
void update(int rt, int v)
{
    rt = map[rt];
    tree[rt] += v;
    while (rt >>= 1)
        update(rt);
}

一些封装思想

传统面向过程的线段树在维护复杂信息时可能有很多不便，把一些lazytag相关操作封装起来比如：

pushdown(rt)
init_lazy(rt) //初始化/还原lazy
cal_lazy(rt) //计算lazy对当前节点的影响
union_lazy(rt, son) //传递标记

之后所有线段树题直接套板子，只需要重新设计lazytag就好了

在E题疯狂WA之后被教做人了。。改了波码风怎么就A了（躺）

动态DP

Dynamic Dynamic Progarmming

本质上是线段树维护转移矩阵。

由DAG引入，假设现在有这个图（行表示起点列表示终点）：
$$
对其中矩阵乘法进行扩展：

矩阵中对乘法的operator这里： tmp[i][j] = a[i][k] * a[k][j] 改成 tmp[i][j] = min(a[i][k] + a[k][j], tmp[i][j]) 就变成了Floyd。

然后把这个矩阵放到线段树中维护，就可以做DAG上的带修Flyod。

题目

K 矩阵表示

题意

上场E题传送门

在此基础上增加单点修改，即某次操作可能会修改某个中间楼梯的方向。

思路

显然可以树状数组维护前缀和，但不如线段树更优美。

因为树状数组需要矩阵求逆，但线段树只需要考虑区间合并（仅矩阵乘法）。

代码

#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define root 1,n,1
#define mid (l+r)>>1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 233;
const ll MOD = 1e9 + 7;
int n, M;
struct Matrix
{
  ll a[2][2];
  Matrix()
  {
    a[0][0] = a[1][1] = 1;
    a[1][0] = a[0][1] = 0;
  }
  Matrix(ll a00, ll a01, ll a10, ll a11)
  {
    a[0][0] = a00;
    a[0][1] = a01;
    a[1][0] = a10;
    a[1][1] = a11;
  }
  Matrix operator * (const Matrix &B)
  {
    Matrix C(0, 0, 0, 0);
    rep (i, 0, 1)
      rep (j, 0, 1)
        rep (k, 0, 1)
          C.a[i][j] = (C.a[i][j] + a[i][k] * B.a[k][j]) % MOD;
    return C;
  }
} mtx[MAXN];
struct Tnode
{
  Matrix sum;
};
struct Tree
{
  Tnode t[MAXN << 2];
  int mp[MAXN]; //树节点，与数组的映射
  void update(int rt)
  {
    t[rt].sum = t[rt << 1].sum * t[rt << 1 | 1].sum;
  }
  void build(int l, int r, int rt)
  {
    if (l == r)
    {
      t[rt].sum = mtx[l];
      mp[l] = rt;
      return;
    }
    int m = mid;
    build(lson);
    build(rson);
    update(rt);
  }
  void modify(int p, Matrix v)
  {
    int rt = mp[p];
    t[rt].sum = v;
    while (rt >>= 1)
      update(rt);
  }
  Matrix query(int l, int r, int rt, int nl, int nr)
  {
    if (nl <= l && r <= nr)
    {
      return t[rt].sum;
    }
    int m = mid;
    if (nl <= m)
      if (m < nr)
        return query(lson, nl, nr) * query(rson, nl, nr);
      else
        return query(lson, nl, nr);
    else
      return query(rson, nl, nr);
  }
} ST;
int main()
{
  //freopen("in.txt", "r", stdin);
  scanf("%d%d ", &n, &M);
  char ch;
  rep (i, 2, n) //写法有关，这里记录的是到达这层的楼梯
  {
    scanf("%c", &ch);
    if (ch == '/')
      mtx[i] = Matrix(1, 1, 0, 1);
    else
      mtx[i] = Matrix(1, 0, 1, 1);
  }
  ST.build(root);
  int opt, l, r, s, t;
  Matrix x;
  while (M--)
  {
    scanf("%d", &opt);
    if (!opt)
    {
      scanf("%d %c", &l, &ch);
      if (ch == '/')
        x = Matrix(1, 1, 0, 1);
      else
        x = Matrix(1, 0, 1, 1);
      ST.modify(l + 1, x);
    }
    else
    {
      scanf("%d%d%d%d", &l, &r, &s, &t);
      printf("%lld\n", ST.query(root, l + 1, r).a[s][t]);
    }
  }
  return 0;
}

J DDP

题意

在原题的基础上添加了：

  • 像K题一样可以修改中间楼梯的结构（单点）。

  • 每个楼梯都有权值，走过有一定花费，可以进行修改（单点）。

  • 查询最短路，而不是方案数。

思路

类似最短路，矩阵里的每个数字改为表示权值（没有楼梯就置为inf）。

在矩阵乘法中做一些修改，相乘改成类似Floyd的求min操作。

用线段树维护即可。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define root 1,n,1
#define mid (l+r)>>1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 233;
const ll INF = 1e15 + 233;
int n, M;
struct Matrix
{
  //矩阵除了对乘法的operator以外与上题完全一致
  Matrix operator * (const Matrix &B)
  {
    Matrix C(INF, INF, INF, INF);
    rep (i, 0, 1)
      rep (j, 0, 1)
        rep (k, 0, 1)
          C.a[i][j] = min(C.a[i][j], a[i][k] + B.a[k][j]); //改成类似floyd的做法
    return C;
  }
} mtx[MAXN];
struct Tnode
{
  Matrix sum;
};
struct Tree
{
    //线段树部分与上题完全一致
} ST;
char str[MAXN];
int main()
{
  freopen("in.txt", "r", stdin);
  scanf("%d%d ", &n, &M);
  scanf("%s", str + 2);
  int v0, v1, v2;
  rep (i, 2, n)
  {
    scanf("%d%d%d", &v0, &v1, &v2);
    if (str[i] == '/')
      mtx[i] = Matrix(v0, v2, INF, v1); //跟图论题一样的初始化emm
    else
      mtx[i] = Matrix(v0, INF, v2, v1);
  }
  ST.build(root);
  int opt, l, r, s, t;
  char ch;
  Matrix x;
  while (M--)
  {
    scanf("%d", &opt);
    if (opt == 0)
    {
      scanf("%d %c", &l, &ch);
      char nowch = mtx[l + 1].a[1][0] == INF ? '/' : '\\';
      if (ch != nowch)
      {
        swap(mtx[l + 1].a[0][1], mtx[l + 1].a[1][0]);
        ST.modify(l + 1, mtx[l + 1]);
      }
    }
    else if (opt == 1)
    {
      scanf("%d", &l);
      scanf("%d%d%d", &mtx[l + 1].a[0][0], &mtx[l + 1].a[1][1],
        (mtx[l + 1].a[1][0] == INF) ? &mtx[l + 1].a[0][1] : &mtx[l + 1].a[1][0]);
      ST.modify(l + 1, mtx[l + 1]);
    }
    else
    {
      scanf("%d%d%d%d", &l, &r, &s, &t);
      Matrix ans = ST.query(root, l + 1, r);
      printf("%lld\n", ans.a[s][t] >= INF ? -1 : ans.a[s][t]);
    }
  }
  return 0;
}

H 线段树的二分思想

题意

给出一堆箱子（），每个箱子最多放大小（），有一些物品（）序列，每个物品有大小（），每个箱子不能超过个（）物品。

每次从左到右寻找能放下当前物品的箱子并放下，询问放在哪里。

思路

二分思想，线段树维护区间max。

每次按照以下流程：

  • 根节点能不能放下，放不下直接输出"-1"。
  • 看左右子树能不能放下，按题意优先左子树。
  • 一直到叶子节点，进行单点加操作，再一路合并上去。

代码

#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define mid (l+r)>>1
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = 3e5 + 233;
int n, M, k, T, tr[MAXN << 2], cnt[MAXN]; //tr记录区间最大值，cnt记录每个箱子的物品个数
void update(int rt)
{
  tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
  if (l == r)
  {
    tr[rt] = M;
    return;
  }
  int m = mid;
  build(lson);
  build(rson);
  update(rt);
}
int modify(int l, int r, int rt, int ai)
{
  if (l == r)
  {
    if (tr[rt] >= ai)
    {
      tr[rt] -= ai;
      if (++cnt[l] == k) //放k个之后直接把剩余容量变成-1
        tr[rt] = -1;
      return l;
    }
    return -1;
  }
  int m = mid, ans;
  if (tr[rt << 1] >= ai) //优先往左，然后往右
    ans = modify(lson, ai);
  else if (tr[rt << 1 | 1] >= ai)
    ans = modify(rson, ai);
  else
    return -1;
  update(rt);
  return ans;
}
int main()
{
  //freopen("in.txt", "r", stdin);
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d%d", &n, &M, &k);
    rep (i, 1, n)
      cnt[i] = 0;
    build(root);
    int ai;
    rep (i, 1, n)
    {
      scanf("%d", &ai);
      printf("%d\n", modify(root, ai));
    }
  }
  return 0;
}

B&C 区间不同颜色数

[SDOI2009]HH的项链

题意

给出一个颜色序列，每次询问区间的不同颜色数，数据范围都 1e6。

思路

离线处理，按右端点排序。有两个位置颜色相同时，记录靠右的地方。

  • 从左到右扫一遍颜色数组。
    • 当前位置的颜色没出现过：树状数组这个位置 + 1
    • 当前位置的颜色出现过：上一个位置 -1， 这个位置 + 1
  • 若当前位置恰好是某一个查询的右端点，统计答案 。（也就是为什么优先靠右记录）

核心代码：

sort(q + 1, q + m + 1, cmp1); //右端点排序
int j = 1;
rep (i, 1, n)
{
    if (pos[a[i]])
    modify(pos[a[i]], -1);    //出现过，现在不再统计原来的
    modify(i, 1); //去统计新的
    pos[a[i]] = i;
    while (q[j].r == i) //记得用while
    {
        q[j].ans = query(q[j].r) - query(q[j].l - 1);
        j++;
    }
    if (j == m + 1)
        break;
}
sort(q + 1, q + m + 1, cmp2); //按id排序
rep (i, 1, m)
    printf("%d\n", q[i].ans);

[HEOI2012]采花

题意

跟上题一样，要求所查询区间内具有这个颜色的花至少有两朵。

思路

开两个数组 和 分别表示颜色 在上次和上上次出现的时间。

要扩展区间右端点时，先看当前颜色有没有出现过。

出现过的话这样子：add(lst[col[i]], 1);

还有别忘了： add(llst[col[i]], -1); //如果llst不是0的话

也就是只有出现两次之后才会把前一次出现的位置对应BIT加一，大概不难想的样子qwq

代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int MAXN = 2e6 + 233;
int n, c, m;
int col[MAXN], tr[MAXN], lst[MAXN], llst[MAXN];
struct query
{
  int l, r, id, ans;
} q[MAXN];
bool cmp(query xx, query yy)
{
  return (xx.r == yy.r) ? xx.l < yy.l : xx.r < yy.r;
}
bool cmp2(query xx, query yy)
{
  return xx.id < yy.id;
}
int lb(int x)
{
  return (x) & (-x);
}
void add(int p, int v)
{
  for (; p <= n; p += lb(p))
    tr[p] += v;
}
int getsum(int p)
{
  int ans = 0;
  for (; p; p -= lb(p))
    ans += tr[p];
  return ans;
}
int main()
{
  //freopen("in.txt", "r", stdin);
  scanf("%d%d%d", &n, &c, &m); //n点c颜色(这个值在这个做法里好像没用qwq)m询问
  rep (i, 1, n)
    scanf("%d", &col[i]);
  rep (i, 1, m)
  {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q + 1, q + m + 1, cmp);
  int nowr = 1;
  rep (i, 1, m)
  {
    while (nowr <= q[i].r)
    {
      if (llst[col[nowr]])
        add(llst[col[nowr]], -1);
      if (lst[col[nowr]])
      {
        add(lst[col[nowr]], 1);
        llst[col[nowr]] = lst[col[nowr]];
        lst[col[nowr]] = nowr;
      }
      else
        lst[col[nowr]] = nowr;
      nowr++;
    }
    q[i].ans = getsum(q[i].r) - getsum(q[i].l - 1);
  }
  sort(q + 1, q + m + 1, cmp2);
  rep (i, 1, m)
    printf("%d\n", q[i].ans);
  return 0;
}

F 综合应用

题意

给出一个长 的数组，元素大小 ， 次询问每次给出区间 ，问将区间内元素离散化之后有多少个元素与原来不同。

思路

权值线段树。

区间MEX：区间最小的未出现正整数。

大于MEX的数都会发生改变。

用 表示值为 的数最后一次在数组中出现的下标，线段树维护区间 最小值。

离线对查询区间右端点排序，对每个询问区间都可以通过区间 值查询出MEX。

问题进一步简化：求区间中小于MEX的数有多少个。

用 表示值为 的数字有多少个

代码

排序尽量用cmp别operator（operator莫名RE改了好久QAQ）

#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define root 1,n,1
#define mid (l+r)>>1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = 3e5 + 233;
int n, M, a[MAXN], ans[MAXN], q2tot;
struct query1 // q1记录原题询问，对右端点排序
{
  int id, l, r;
} q1[MAXN];
struct query2 // q2记录需要查询出现次数的数字
{
  int id, pos, num, type; //pos位置，num数字，左右端点type分别取1/-1，配合id直接统计到ans里
} q2[MAXN << 1];
bool cmpq1(query1 x, query1 y)
{
  return x.r < y.r;
}
bool cmpq2(query2 x, query2 y)
{
  return x.pos < y.pos;
}
struct Seg
{
  int t[MAXN << 2], mp[MAXN]; //权值线段树，维护lastpos最小值，mp用于快速modify
  void update(int rt)
  {
    t[rt] = min(t[rt << 1], t[rt << 1 | 1]);
  }
  void build(int l, int r, int rt)
  {
    if (l == r)
    {
      t[rt] = 0;
      mp[l] = rt;
      return;
    }
    int m = mid;
    build(lson);
    build(rson);
    update(rt);
  }
  void modify(int rt, int v)
  {
    rt = mp[rt];
    t[rt] = v;
    while (rt >>= 1)
      update(rt);
  }
  int query(int l, int r, int rt, int nl) //查询nl以后的mex
  {
    if (l == r)
    {
      return l;
    }
    int m = mid;
    if (t[rt << 1] < nl) //左边有数字最后一次出现在nl之前，优先往左查
      return query(lson, nl);
    else
      return query(rson, nl);
  }
} ST;
struct Bit
{
  int t[MAXN << 1]; //统计数字出现次数的BIT
  int lb(int x)
  {
    return x & (-x);
  }
  void modify(int p, int v)
  {
    for (; p <= n; p += lb(p))
      t[p] += v;
  }
  int query(int p)
  {
    int tmp = 0;
    for (; p; p -= lb(p))
      tmp += t[p];
    return tmp;
  }
} BIT;
int main()
{
  //freopen("in.txt", "r", stdin);
  scanf("%d", &n);
  rep (i, 1, n)
  {
    scanf("%d", &a[i]);
    if (a[i] > n)
      a[i] = n + 1;
  }
  scanf("%d", &M);
  rep (i, 1, M)
  {
    scanf("%d%d", &q1[i].l, &q1[i].r);
    q1[i].id = i;
    //一开始认为区间所有数字的值都会改变，后面去查有多少不变（有多少数字小于等于mex）
    ans[i] = q1[i].r - q1[i].l + 1;
  }
  sort(q1 + 1, q1 + M + 1, cmpq1);
  int now = 1;
  ST.build(root);
  rep (i, 1, n)
  {
    ST.modify(a[i], i); //更新当前数字最后出现位置
    while (now <= M && q1[now].r == i)
    {
      q2[++q2tot].id = q1[now].id;
      q2[q2tot].num = ST.query(root, q1[now].l); //查询当前mex
      //前缀和，出现次数 = [1, r] - [1, l - 1]，ans是要减去这个数，右端点记-1
      q2[q2tot].pos = q1[now].r;
      q2[q2tot].type = -1;
      if (q1[now].l != 1)
      {
        q2[++q2tot].id = q1[now].id;
        q2[q2tot].num = q2[q2tot - 1].num;
        q2[q2tot].pos = q1[now].l - 1;
        q2[q2tot].type = 1;
      }
      now++;
    }
  }
  //按pos排序，边添加数字边查询，就能避免用可持久化数据结构了emm
  sort(q2 + 1, q2 + q2tot + 1, cmpq2);
  now = 1;
  rep (i, 1, n)
  {
    BIT.modify(a[i], 1);
    while (now <= q2tot && q2[now].pos == i)
    {
      ans[q2[now].id] += BIT.query(q2[now].num) * q2[now].type;
      now++;
    }
  }
  rep (i, 1, M)
    printf("%d\n", ans[i]);
  return 0;
}
全部评论

相关推荐

10-23 17:49
门头沟学院 Java
面试紧张破防现场
最近面试还好，表现还可以，但是以前刚开始面试以及遇到压力面和自己不会的题目的时候，就容易紧张。1.&nbsp;嘴巴先“掉链子”：越想说好越说不顺平时能说会道，但面试紧张起来，嘴就像被粘住了，脑子和嘴完全不同步。说话卡壳还重复：比如想介绍项目经历，本来准备好说“我负责后端接口开发”，结果一开口变成“我…我负责那个…就是后端…后端接口的开发，对，就是接口开发”，一句话翻来覆去说，还总在“然后”“那个”“嗯”这种词上卡壳，越卡越慌，越慌越说不明白。忘词后大脑空白：要是面试官突然问个没准备到的问题，比如“这个项目里你遇到的最大困难是什么”，瞬间脑子就“嗡”一下，之前想的案例全没影了，只能盯着面试官傻笑，半天憋出...
面试紧张时你会有什么表现...
点赞 评论 收藏
分享
10-20 09:45
顺丰集团_大数据挖掘与分析工程师(准入职员工)
顺丰内推，顺丰内推码
已经来工作一个多月啦，感觉幸福度很高，顺丰真的是很值得来的一家公司！公司里的氛围很好，同事们很nice很好沟通，和大家私下相处也贼融洽。工作很充实但是没什么压力，领导带教都不push，感觉每天来公司都很开心~💼&nbsp;公司岗位数据分析💢&nbsp;工作强度在整个集团里算卷的，顺丰科技大多数部门965美滋滋，但是我进的部门业务多975，双休基本可以保证，需求多的话周末也要赶一下进度。🫶️&nbsp;团队氛围进的团队好，前辈都很热心教人，有问必答。❤️&nbsp;职场感受希望我这次转正能通过吧，能过的话会来报喜😊顺丰集团2026届校招启动！【公司简介】：顺丰集团是世界500强企业第377位，中国第一大、世界第四大快递物流服务...
顺丰集团工作强度 274人发布
点赞 评论 收藏
分享
10-10 19:11
华东交通大学 Java
点赞 评论 收藏
分享
10-10 01:10
已编辑
深圳大学 测试开发
为啥0面试啊家人们
😇😇😇&nbsp;&nbsp;
面了100年面试不知...：六月到九月，四个项目一个实习，是魔丸吗
投了多少份简历才上岸
点赞 评论 收藏
分享
10-22 09:38
三一重能_C++研发工程师(准入职员工)
三一重能内推，三一重能内推码
三一重能&nbsp;结构设计工程师&nbsp;面经一面&nbsp;7.14&nbsp;（15-20min）技术面&nbsp;自我介绍针对简历项目提问（个人项目）]涉及到结构疲劳&nbsp;分析方法解决问题的思路&nbsp;理论知识面试官的研究方向可能刚好和我相契合问的问题都很专业英文面&nbsp;8.2（5min）三到四个问题对于结构分析这类问题的思路为什么实验测试很重要你对三一重能的了解&nbsp;为什么来三一面试官口语很地道&nbsp;不难听懂终面&nbsp;8.4&nbsp;（20min）也是技术面&nbsp;比一面问的更加具体面试官问了比较多关于材料的问题（个人有一个叶片设计的项目）包括整个结构的设计思路选用什么材料&nbsp;材料性能具体的工艺&nbsp;以及一些详细的参数反问总的来说&nbsp;两轮面试都比较专业&nbsp;问题有深度8.7&nbsp;收到面...
点赞 评论 收藏
分享
评论
点赞
1
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 怎么给家人解释你的工作？ #
10966次浏览 74人参与
# 应届生被毁约被毁意向了怎么办 #
45845次浏览 280人参与
# 快手技术岗信息交流阵地 #
3042次浏览 28人参与
# 你的mentor是什么样的人？ #
15933次浏览 110人参与
# 牛客周边新品开箱 #
10207次浏览 90人参与
# 帮我看看，领导说这话什么意思？ #
20640次浏览 98人参与
# 求职中的尴尬瞬间 #
3655次浏览 42人参与
# 牛友的志愿填报指南 #
34714次浏览 185人参与
# 国企还是互联网，你怎么选？ #
169816次浏览 1272人参与
# 牛客树洞，我想对你说 #
8631次浏览 97人参与
# 机械人集合！你是什么工程师？ #
19703次浏览 91人参与
# 如何KTV领导 #
72499次浏览 502人参与
# 大疆工作体验 #
18598次浏览 85人参与
# 今年形式下双非本找得到工作吗 #
237383次浏览 1433人参与
# 三一集团提前批进度交流 #
38226次浏览 225人参与
# 求职低谷期你是怎么度过的 #
12562次浏览 249人参与
# 26届秋招公司红黑榜 #
27946次浏览 115人参与
# 校招泡的最久的公司是哪家？ #
12704次浏览 81人参与
# 从哪些方向判断这个offer值不值得去？ #
16622次浏览 189人参与
# 得物app工作体验 #
28193次浏览 66人参与
# 大厂无回复，继续等待还是奔赴小厂 #
247919次浏览 1634人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务