头像

imnoob




离线:10小时前


最近来访(68)
用户头像
DXLR
用户头像
揽苟
用户头像
淡末初夏
用户头像
QWQdcy
用户头像
努力学习鸭
用户头像
Daysgone
用户头像
Selflocking
用户头像
上下求索
用户头像
_不知道
用户头像
Sun@Wind
用户头像
33号花卷
用户头像
Zero_Two
用户头像
吃掉这个脆脆鲨
用户头像
今天AC了吗
用户头像
肖肖_6
用户头像
心牢
用户头像
lihua777
用户头像
Nijiiro
用户头像
忘打周赛
用户头像
白日做梦家


imnoob
1个月前

LCA算法

向上标记 BF $O(n)$

利用最朴素的思想,类似我将到根节点路上所有节点全标记一遍。当遍历另外一个点时,继续向上遍历,当我遇到我已经标记过的第一个点时,这个点必定是我当前最近的一个点。
lca1

相较于其他两种方法,这种方法占用空间小,但是时间效率低下,在实在做不了的情况下在考虑这种方法。

类似题

CCCC天梯赛L2T3 没有让你求LCA但是用到了这种思想。考试没有做出来T_

倍增LCA $O(logn)$

preview

此问题说的是用倍增法求解LCA问题, 那么我们可以推测这种方法还可以解决其他的一些问题(不在当下讨论范围). 在学习的过程中, 我是这么理解的: 它是一种类似于二分的方法, 不过这里不是二分, 而是倍增, 以2倍, 4倍, 等等倍数增长

首先任意两个节点有两种情况

  1. 两个节点深度相同

  2. 两个节点深度不同

其实1是2的一种特殊情况,所以我们将2特化成1,每当两个节点深度不同时,将其特化为同一深度。同时我们需要获取每个节点的深度信息和它的父节点信息,利用DFSorBFS皆可

又如何将其转换为同一深度呢,这里用到倍增法,快速转换到同一层。

同一深度后我们又怎么办呢?与BF法不同的是,我们这次有两点不同

  1. 这次两个节点同时向上迭代
  2. 迭代停止条件不同

现在无法理解上面的几个过程没关系,只要知道我们用递增法解决了上述的两个问题.

算法框架与实现

那么过了一遍上面的思路引导之后, 我们可以大概想一想怎么实现整个的问题了.

其实用求LCA这个问题可以分为两块: 预处理 + 查询, 其中预处理是$O(nlogn)$, 而一次查询是$O(logn)$, $n$代表结点数量. 所以总时间复杂度为$O(nogn +Qlogn)$. $Q$为查询次数

其步骤是这样的:

  1. 存储一棵树(邻接表法)
  2. 获取树各结点的上的深度(dfsbfs)
  3. 获取2次幂祖先的结点, 用parents[maxn][20]数组存储, 倍增法关键
  4. 用倍增法查询LCA

步骤一 预处理深度与父节点

首先我们处理每一个节点的父节点和深度

int depth[N], int parent[N][30];
void pre(int u, int root){
  parent[u][0] = root;
  depth[u] = depth[root] + 1;
  for(auto i : h[u]){
    if(i == root)
      continue;
    else
      pre(i, u);
  }
}

步骤二 构造父母数组

需要一个数组parent[i][n],n代表$2^n$
$2^0$ 即为 1 为当前节点的父亲
$2^1$ 即为 2 为当前节点的父亲的父亲
$2^2$ 即为 4 为当前节点的(父亲的父亲)的(父亲的父亲)

void getParents()
{
    for (int up = 1; (1 << up) <= n; ++up) {
        for (int i = 1; i <= n; ++i) {
            parents[i][up] = parents[parents[i][up - 1]][up - 1];
        }
    }
}

步骤三 查询$O(logV)$

int lca(int x, int y){
  if(depth[y] > depth[x])
    swap(x, y);
  int i = 0, j;
  while(1 << (i + 1) <= depth[x]) ++ i;
  for(j = i;~j;j --){
    if(depth[x] - (1 << j) >= depth[y])
      x = parent[x][j];
  }
  if(x == y)
    return y;
  for(j = i;~j;j --){
    if(parent[x][j] != parent[y][j]){
      x = parent[x][j];
      y = parent[y][j];
    }
  }
  return parent[x][0];
}

例题

acwing模板题

// 代码拼装后有问题 **getParent**
// 放在DFS中没有问题。。。
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;

const int N = 1e5 + 10;

vi h[N];
int parent[N][25];
int depth[N];
int n, m;

void pre(int u, int root) {
  parent[u][0] = root;
  depth[u] = depth[root] + 1;
  for (int k = 1; k <= 20; k++) {
    parent[u][k] = parent[parent[u][k - 1]][k - 1];
  }
  for (auto i : h[u]) {
    if (i == root)
      continue;
    else
      pre(i, u);
  }
}

int LCA(int x, int y) {
  if (depth[x] < depth[y])
    swap(x, y);
  int i = -1, j;
  while ((1 << (i + 1)) <= depth[x])
    i++;
  for (j = i; j >= 0; j--) {
    if (depth[x] - (1 << j) >= depth[y])
      x = parent[x][j];
  }
  if (x == y)
    return x;
  for (j = i; j >= 0; j--) {
    if (parent[x][j] != parent[y][j]) {
      x = parent[x][j];
      y = parent[y][j];
    }
  }
  return parent[x][0];
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  int root;
  depth[0] = -1;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    if (b == -1) {
      root = a;
    } else {
      h[a].push_back(b);
      h[b].push_back(a);
    }
  }
  pre(root, 0);
  cin >> m;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    int t = LCA(x, y);
    if (t == x)
      puts("1");
    else if (t == y)
      puts("2");
    else
      puts("0");
  }
}

hdu带权LCA

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;

const int N = 4e4 + 10;
int h[N], e[N * 3], ne[N * 3], w[N * 3], idx;
int depth[N], prefix[N], parent[N][30], in[N];

void add(int a, int b, int c) {
  e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void init() {
  memset(h, -1, sizeof h);
  memset(parent, 0, sizeof parent);
  memset(depth, 0, sizeof depth);
  memset(prefix, 0, sizeof prefix);
  memset(in, 0, sizeof in);
}
void pre(int u, int root) {
  depth[u] = depth[root] + 1;
  parent[u][0] = root;
  for (int i = 1; i <= 20; i++) {
    parent[u][i] = parent[parent[u][i - 1]][i - 1];
  }
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (j == root)
      continue;
    prefix[j] = prefix[u] + w[i];
    pre(j, u);
  }
}
int lca(int x, int y) {
  if (depth[y] > depth[x])
    swap(x, y);
  int i = -1, j;
  while ((1 << (i + 1)) <= depth[x])
    i++;
  for (j = i; ~j; j--) {
    if (depth[x] - (1 << j) >= depth[y])
      x = parent[x][j];
  }
  if (x == y)
    return x;
  for (j = i; j >= 0; j--) {
    if (parent[x][j] != parent[y][j]) {
      x = parent[x][j];
      y = parent[y][j];
    }
  }
  return parent[x][0];
}
void sol() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
    in[b]++;
  }
  int root;
  for (int i = 1; i <= n; i++)
    if (!in[i]) {
      root = i;
      break;
    }
  pre(root, 0);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    int t = lca(a, b);
    cout << prefix[a] + prefix[b] - 2 * prefix[t] << '\n';
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    init();
    sol();
  }
}

tarjanLCA $O(1)$ 常数级 重要,常考点

tarjan算法是一种离线算法,常数大,但是单次查询是基本为
$O(1)$复杂度,需要用并查集记录其祖先节点

步骤一

首先接受输入(邻接表存储) 再将询问输入(邻接表存储)。查询边其实是虚拟加上去的边,为了方便,每次输入查询边的时候,将这个边及其反向边都加入到 queryEdge 数组里。

步骤二

然后对其进行一次 DFS 遍历,同时使用 visited 数组进行记录某个结点是否被访问过、parent 记录当前结点的父亲结点。

步骤三

其中涉及到了回溯思想,我们每次遍历到某个结点的时候,认为这个结点的根结点就是它本身。让以这个结点为根节点的DFS全部遍历完毕了以后,再将这个结点的根节点设置为这个结点的父一级结点

步骤四

回溯的时候,如果以该节点为起点,queryEdge 查询边的另一个结点也恰好访问过了,则直接更新查询边的 LCA 结果。

复杂度分析

Tarjan 算法需要初始化并查集,所以预处理的时间复杂度为 $O(n)$,Tarjan 算法处理所有 $m$ 次询问的时间复杂度为$O(n + m)$。但是 Tarjan 算法的常数比倍增算法大。

模板

acwing模板题

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 10010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N]; //每个点和1号点的距离
int p[N];
int res[M];
int st[N];
vector<PII> query[N]; //把询问存下来
// query[i][first][second] first存查询距离i的另外一个点j,second存查询编号idx

void add(int a, int b, int c) {
  e[idx] = b;
  ne[idx] = h[a];
  w[idx] = c;
  h[a] = idx++;
}

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void dfs(int u, int fa) {
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (j == fa)
      continue;
    dist[j] = dist[u] + w[i];
    dfs(j, u);
  }
}

void tarjan(int u) {
  st[u] = 1; //当前路径点标记为1
  // u这条路上的根节点的左下的点用并查集合并到根节点
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (!st[j]) {
      tarjan(j); //往左下搜
      p[j] = u;  //从左下回溯后把左下的点合并到根节点
    }
  }
  // 对于当前点u 搜索所有和u
  for (auto item : query[u]) {
    int y = item.first, id = item.second;
    if (st[y] == 2) //如果查询的这个点已经是左下的点(已经搜索过且回溯过,标记为2)
    {
      int anc = find(y); // y的根节点
      // x到y的距离 = d[x]+d[y] - 2*d[lca]
      res[id] = dist[u] + dist[y] - dist[anc] * 2; //第idx次查询的结果 res[idx]
    }
  }
  //点u已经搜索完且要回溯了 就把st[u]标记为2
  st[u] = 2;
}

int main() {
  cin >> n >> m;
  // 建图
  memset(h, -1, sizeof h);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c), add(b, a, c);
  }

  // 存下询问
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    if (a != b) {
      query[a].push_back({b, i});
      query[b].push_back({a, i});
    }
  }
  for (int i = 1; i <= n; i++)
    p[i] = i;

  dfs(1, -1);
  tarjan(1);
  for (int i = 0; i < m; i++)
    cout << res[i] << '\n'; //把每次询问的答案输出
  return 0;
}


新鲜事 原文

imnoob
1个月前
# LCA算法 ## 向上标记 BF $O(n)$ 利用最朴素的思想,类似我将到根节点路上所有节点全标记一遍。当遍历另外一个点时,继续向上遍历,当我遇到我已经标记过的第一个点时,这个点必定是我当前最近的一个点。 ![lca1](https://s1.328888.xyz/2022/07/09/ZEmR.png) 相较于其他两种方法,这种方法占用空间小,但是时间效率低下,在实在做不了的情况下在考虑这种方法。 类似题 [CCCC天梯赛L2T3](https://pintia.cn/problem-sets/994805046380707840/problems/1518582482059845632) 没有让你求LCA但是用到了这种思想。考试没有做出来T_ ## 倍增LCA $O(logn)$ ### preview > 此问题说的是用倍增法求解LCA问题, 那么我们可以推测这种方法还可以解决其他的一些问题(不在当下讨论范围). 在学习的过程中, 我是这么理解的: 它是一种类似于二分的方法, 不过这里不是二分, 而是倍增, 以2倍, 4倍, 等等倍数增长 首先任意两个节点有两种情况 1. 两个节点深度相同 2. 两个节点深度不同 其实1是2的一种特殊情况,所以我们将2特化成1,每当两个节点深度不同时,将其特化为同一深度。同时我们需要获取每个节点的深度信息和它的父节点信息,利用`DFS`or`BFS`皆可 又如何将其转换为同一深度呢,这里用到倍增法,快速转换到同一层。 同一深度后我们又怎么办呢?与BF法不同的是,我们这次有两点不同 1. 这次两个节点同时向上迭代 2. 迭代停止条件不同 现在无法理解上面的几个过程没关系,**只要知道我们用递增法解决了上述的两个问题.** ### 算法框架与实现 那么过了一遍上面的思路引导之后, 我们可以大概想一想怎么实现整个的问题了. 其实用求`LCA`这个问题可以分为两块: `预处理 + 查询`, 其中预处理是$O(nlogn)$, 而一次查询是$O(logn)$, $n$代表结点数量. 所以总时间复杂度为$O(nogn +Qlogn)$. $Q$为查询次数 其步骤是这样的: 1. 存储一棵树(邻接表法) 2. 获取树各结点的上的深度(`dfs`或`bfs`) 3. 获取2次幂祖先的结点, 用`parents[maxn][20]`数组存储, 倍增法关键 4. 用倍增法查询`LCA` #### 步骤一 预处理深度与父节点 首先我们处理每一个节点的父节点和深度 ```cpp int depth[N], int parent[N][30]; void pre(int u, int root){ parent[u][0] = root; depth[u] = depth[root] + 1; for(auto i : h[u]){ if(i == root) continue; else pre(i, u); } } ``` #### 步骤二 构造父母数组 需要一个数组`parent[i][n]`,n代表$2^n$ $2^0$ 即为 1 为当前节点的父亲 $2^1$ 即为 2 为当前节点的父亲的父亲 $2^2$ 即为 4 为当前节点的(父亲的父亲)的(父亲的父亲) ... ```cpp void getParents() { for (int up = 1; (1 << up) <= n; ++up) { for (int i = 1; i <= n; ++i) { parents[i][up] = parents[parents[i][up - 1]][up - 1]; } } } ``` #### 步骤三 查询$O(logV)$ ```cpp int lca(int x, int y){ if(depth[y] > depth[x]) swap(x, y); int i = 0, j; while(1 << (i + 1) <= depth[x]) ++ i; for(j = i;~j;j --){ if(depth[x] - (1 << j) >= depth[y]) x = parent[x][j]; } if(x == y) return y; for(j = i;~j;j --){ if(parent[x][j] != parent[y][j]){ x = parent[x][j]; y = parent[y][j]; } } return parent[x][0]; } ``` ### 例题 [acwing模板题](https://www.acwing.com/activity/content/problem/content/1537/) ```cpp // 代码拼装后有问题 **getParent** // 放在DFS中没有问题。。。 #include <algorithm> #include <bitset> #include <cmath> #include <cstring> #include <deque> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define int ll #define Max 0x3f3f3f3f #define Min 0x0c0c0c0c0; using ll = long long; using vi = vector<int>; using vvi = vector<vector<int>>; const int N = 1e5 + 10; vi h[N]; int parent[N][25]; int depth[N]; int n, m; void pre(int u, int root) { parent[u][0] = root; depth[u] = depth[root] + 1; for (int k = 1; k <= 20; k++) { parent[u][k] = parent[parent[u][k - 1]][k - 1]; } for (auto i : h[u]) { if (i == root) continue; else pre(i, u); } } int LCA(int x, int y) { if (depth[x] < depth[y]) swap(x, y); int i = -1, j; while ((1 << (i + 1)) <= depth[x]) i++; for (j = i; j >= 0; j--) { if (depth[x] - (1 << j) >= depth[y]) x = parent[x][j]; } if (x == y) return x; for (j = i; j >= 0; j--) { if (parent[x][j] != parent[y][j]) { x = parent[x][j]; y = parent[y][j]; } } return parent[x][0]; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; int root; depth[0] = -1; for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; if (b == -1) { root = a; } else { h[a].push_back(b); h[b].push_back(a); } } pre(root, 0); cin >> m; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; int t = LCA(x, y); if (t == x) puts("1"); else if (t == y) puts("2"); else puts("0"); } } ``` [hdu带权LCA](https://www.acwing.com/activity/content/problem/content/1537/) ```cpp #include <algorithm> #include <bitset> #include <cmath> #include <cstring> #include <deque> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define int ll #define Max 0x3f3f3f3f #define Min 0x0c0c0c0c0; using ll = long long; using vi = vector<int>; using vvi = vector<vector<int>>; const int N = 4e4 + 10; int h[N], e[N * 3], ne[N * 3], w[N * 3], idx; int depth[N], prefix[N], parent[N][30], in[N]; void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } void init() { memset(h, -1, sizeof h); memset(parent, 0, sizeof parent); memset(depth, 0, sizeof depth); memset(prefix, 0, sizeof prefix); memset(in, 0, sizeof in); } void pre(int u, int root) { depth[u] = depth[root] + 1; parent[u][0] = root; for (int i = 1; i <= 20; i++) { parent[u][i] = parent[parent[u][i - 1]][i - 1]; } for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == root) continue; prefix[j] = prefix[u] + w[i]; pre(j, u); } } int lca(int x, int y) { if (depth[y] > depth[x]) swap(x, y); int i = -1, j; while ((1 << (i + 1)) <= depth[x]) i++; for (j = i; ~j; j--) { if (depth[x] - (1 << j) >= depth[y]) x = parent[x][j]; } if (x == y) return x; for (j = i; j >= 0; j--) { if (parent[x][j] != parent[y][j]) { x = parent[x][j]; y = parent[y][j]; } } return parent[x][0]; } void sol() { int n, m; cin >> n >> m; for (int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c); in[b]++; } int root; for (int i = 1; i <= n; i++) if (!in[i]) { root = i; break; } pre(root, 0); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; int t = lca(a, b); cout << prefix[a] + prefix[b] - 2 * prefix[t] << '\n'; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { init(); sol(); } } ``` ## tarjanLCA $O(1)$ 常数级 重要,常考点 `tarjan`算法是一种离线算法,常数大,但是单次查询是基本为 $O(1)$复杂度,需要用并查集记录其祖先节点 ### 步骤一 首先接受输入(邻接表存储) 再将询问输入(邻接表存储)。查询边其实是虚拟加上去的边,为了方便,每次输入查询边的时候,将这个边及其反向边都加入到 queryEdge 数组里。 ### 步骤二 然后对其进行一次 DFS 遍历,同时使用 visited 数组进行记录某个结点是否被访问过、parent 记录当前结点的父亲结点。 ### 步骤三 其中涉及到了`回溯`思想,我们每次遍历到某个结点的时候,认为这个结点的根结点就是它本身。让以这个结点为根节点的`DFS`全部遍历完毕了以后,再将`这个结点的根节点`设置为`这个结点的父一级结点`。 ### 步骤四 回溯的时候,如果以该节点为起点,queryEdge 查询边的另一个结点也恰好访问过了,则直接更新查询边的 LCA 结果。 ### 复杂度分析 Tarjan 算法需要初始化并查集,所以预处理的时间复杂度为 $O(n)$,Tarjan 算法处理所有 $m$ 次询问的时间复杂度为$O(n + m)$。但是 Tarjan 算法的常数比倍增算法大。 ### 模板 [acwing模板题](https://www.acwing.com/problem/content/1173/) ```cpp #include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <vector> using namespace std; typedef pair<int, int> PII; const int N = 10010, M = N * 2; int n, m; int h[N], e[M], w[M], ne[M], idx; int dist[N]; //每个点和1号点的距离 int p[N]; int res[M]; int st[N]; vector<PII> query[N]; //把询问存下来 // query[i][first][second] first存查询距离i的另外一个点j,second存查询编号idx void add(int a, int b, int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void dfs(int u, int fa) { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; dist[j] = dist[u] + w[i]; dfs(j, u); } } void tarjan(int u) { st[u] = 1; //当前路径点标记为1 // u这条路上的根节点的左下的点用并查集合并到根节点 for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!st[j]) { tarjan(j); //往左下搜 p[j] = u; //从左下回溯后把左下的点合并到根节点 } } // 对于当前点u 搜索所有和u for (auto item : query[u]) { int y = item.first, id = item.second; if (st[y] == 2) //如果查询的这个点已经是左下的点(已经搜索过且回溯过,标记为2) { int anc = find(y); // y的根节点 // x到y的距离 = d[x]+d[y] - 2*d[lca] res[id] = dist[u] + dist[y] - dist[anc] * 2; //第idx次查询的结果 res[idx] } } //点u已经搜索完且要回溯了 就把st[u]标记为2 st[u] = 2; } int main() { cin >> n >> m; // 建图 memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } // 存下询问 for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; if (a != b) { query[a].push_back({b, i}); query[b].push_back({a, i}); } } for (int i = 1; i <= n; i++) p[i] = i; dfs(1, -1); tarjan(1); for (int i = 0; i < m; i++) cout << res[i] << '\n'; //把每次询问的答案输出 return 0; } ```



imnoob
2个月前

线段树版本,常数无敌大,本来$o(nlogn)$我估摸着我有$o(9*nlogn)$的复杂度,没有用vector。
如果你仔细看抽风巨巨的题解,他其实是将vector当成固定长度的数组在使用了,所以我选择了直接上原生数组。
同时修改值时,将其利用类std::merge_sort的操作作为pushup操作。
查询值时,我们只需要收到有效区间的数组即可,则用ans数组缓存,又最后ans数组有效值为8的倍数,那么最后排序后输出第start - 8元素即可。

中间夹杂各种大常数操作,如果有大佬能指点一下就好了

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

struct node{
    int l, r;
    int top8[8];
} tr[N << 2];

int ans[1010], start;

void pushup(int n){
    int pl = 0, pr = 0, pu = 0;
    while(pu < 8){
        if(tr[n << 1].top8[pl] >= tr[n << 1 | 1].top8[pr])
            tr[n].top8[pu ++] = tr[n << 1].top8[pl ++];
        else
            tr[n].top8[pu ++] = tr[n << 1 | 1].top8[pr ++];
    }
}

void build(int u, int l, int r){
    tr[u].l = l, tr[u].r = r;
    if(l == r)
        return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int x, int v){
    if(tr[u].l == x && tr[u].r == tr[u].l)
        tr[u].top8[0] = v;  
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

void query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r){
        for(int i = 0;i < 8;i ++){
            ans[start ++] = tr[u].top8[i];
        }
    }else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(mid >= l)
            query(u << 1, l , r);
        if(r > mid)
            query(u << 1 | 1, l, r);
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    build(1, 1, n);
    for(int i = 0;i < m;i ++){
        char t;
        int op1, op2;
        cin >> t >> op1 >> op2;
        if(t == 'C'){
            modify(1, op1, op2);
            // cerr << op2 << '\n';
        }else{
            start = 0;
            query(1, op1, op2);
            sort(ans, ans + start);
            cout << ans[start - 8] << '\n';
        }
    }
}


活动打卡代码 AcWing 1085. 不要62

imnoob
2个月前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 100;
int f[N][N];
int a[N], al;

int dp(int pos, int st, int op) {
  if (!pos)
    return 1;
  if (!op && ~f[pos][st])
    return f[pos][st];
  int res = 0, maxn = op ? a[pos] : 9;
  for (int i = 0; i <= maxn; i++) {
    if ((st == 6 && i == 2) || i == 4)
      continue;
    res += dp(pos - 1, i, op && i == a[pos]);
  }
  return op ? res : f[pos][st] = res;
}
int calc(int n) {
  al = 0;
  memset(f, -1, sizeof f);
  int t = n;
  while (n) {
    a[++al] = n % 10;
    n /= 10;
  }
  return dp(al, 0, 1);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int a, b;
  while (cin >> a >> b, a || b) {
    cout << calc(b) - calc(a - 1) << "\n";
  }
}


活动打卡代码 AcWing 1084. 数字游戏 II

imnoob
2个月前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
int aa, bb, cc;
const int N = 100;
int f[N][N], a[N], al;
int dp(int pos, int st, int op) {
  if (!pos)
    return st % cc == 0;
  if (!op && ~f[pos][st])
    return f[pos][st];
  int res = 0, maxn = op ? a[pos] : 9;
  for (int i = 0; i <= maxn; i++) {
    res += dp(pos - 1, st + i, op && i == a[pos]);
  }
  return op ? res : f[pos][st] = res;
}
int calc(int n) {
  al = 0;
  memset(f, -1, sizeof f);
  while (n) {
    a[++al] = n % 10;
    n /= 10;
  }
  return dp(al, 0, 1);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  while (cin >> aa >> bb >> cc) {
    cout << calc(bb) - calc(aa - 1) << '\n';
  }
}


活动打卡代码 AcWing 1083. Windy数

imnoob
2个月前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 50;
int f[N][N];
int a[N], al;
int dp(int pos, int st, int op) {
  if (!pos)
    return 1;
  if (!op && ~f[pos][st])
    return f[pos][st];
  int res = 0, maxn = op ? a[pos] : 9;
  for (int i = 0; i <= maxn; i++) {
    if (abs(i - st) < 2)
      continue;
    res += dp(pos - 1, !i && st == -2 ? -2 : i, op && a[pos] == i);
  }
  return op && st == -2 ? res : f[pos][st] = res;
}
int calc(int n) {
  al = 0;
  memset(f, -1, sizeof f);
  while (n) {
    a[++al] = n % 10;
    n /= 10;
  }
  return dp(al, -2, 1);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int a, b;
  cin >> a >> b;
  cout << calc(b) - calc(a - 1);
}


活动打卡代码 AcWing 1277. 维护序列

imnoob
3个月前
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n, p, m;
int w[N];
struct Node {
  int l, r, sum, add, mul;
} tr[4 * N];

void pushup(int u) { tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p; }

void eval(Node &root, int add,
          int mul) //计算在该区间加或乘一个数,数据可能会爆int
{
  root.sum = ((LL)root.sum * mul + (LL)(root.r - root.l + 1) * add) % p;
  root.mul = (LL)root.mul * mul % p;         //根据推的公式
  root.add = ((LL)root.add * mul + add) % p; //根据推的公式
}

void pushdown(int u) {
  eval(tr[u << 1], tr[u].add, tr[u].mul);
  eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
  tr[u].add = 0;
  tr[u].mul = 1;
}

void build(int u, int l, int r) {
  tr[u].r = r, tr[u].l = l;
  if (l == r)
    tr[u].sum = w[l], tr[u].add = 0, tr[u].mul = 1;
  else {
    int mid = l + r >> 1;
    tr[u].add = 0, tr[u].mul = 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u); //回溯时通过子区间更新父区间信息
  }
}

void modify(int u, int l, int r, int add, int mul) {
  if (tr[u].l >= l && tr[u].r <= r)
    eval(tr[u], add, mul); //若当前访问区间在查询区间内
  else {
    pushdown(u); //区间分列时需先处理懒标记
    int mid = tr[u].r + tr[u].l >> 1;
    if (mid >= l)
      modify(u << 1, l, r, add, mul); //递归处理左右子区间
    if (mid < r)
      modify(u << 1 | 1, l, r, add, mul);
    pushup(u);
  }
}

int query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r)
    return tr[u].sum; //若当前访问区间在查询区间内
  else {
    pushdown(u); //区间分列时需先处理懒标记
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (mid >= l)
      sum = query(u << 1, l, r) % p; //递归处理左右子区间
    if (mid < r)
      sum = (sum + query(u << 1 | 1, l, r)) % p;
    return sum;
  }
}

int main() {
  scanf("%d%d", &n, &p);
  for (int i = 1; i <= n; i++)
    scanf("%d", &w[i]);
  build(1, 1, n);
  scanf("%d", &m);
  while (m--) {
    int t, l, r, d;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      scanf("%d", &d);
      modify(1, l, r, 0, d);
    } else if (t == 2) {
      scanf("%d", &d);
      modify(1, l, r, d, 1);
    } else
      printf("%d\n", query(1, l, r));
  }
  return 0;
}



活动打卡代码 AcWing 4342. 就一勾子

imnoob
3个月前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 1e5 + 10;
struct node {
  int l, r, v, t;
} tr[N << 2];
void pushup(int u) { tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v; }
void pushdown(int u) {
  auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
  if (root.t) {
    l.t = root.t, l.v = (l.r - l.l + 1) * root.t;
    r.t = root.t, r.v = (r.r - r.l + 1) * root.t;
    root.t = 0;
  }
}
int query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r) {
    return tr[u].v;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int k = 0;
    if (l <= mid)
      k += query(u << 1, l, r);
    if (mid < r)
      k += query(u << 1 | 1, l, r);
    return k;
  }
}
void modify(int u, int l, int r, int c) {
  if (tr[u].l >= l && tr[u].r <= r) {
    tr[u].v = c * (tr[u].r - tr[u].l + 1);
    tr[u].t = c;
    return;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
      modify(u << 1, l, r, c);
    if (r > mid)
      modify(u << 1 | 1, l, r, c);
    pushup(u);
  }
}
void build(int u, int l, int r) {
  tr[u] = {l, r, 1, 0};
  if (l == r) {
    return;
  } else {
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    memset(tr, 0, sizeof tr);
    int n, m;
    cin >> n >> m;
    build(1, 1, n);
    for (int i = 0; i < m; i++) {
      int l, r, c;
      cin >> l >> r >> c;
      modify(1, l, r, c);
    }
    printf("Case %lld: The total value of the hook is %lld.\n", i,
           query(1, 1, n));
  }
}



imnoob
3个月前

传统线段树

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define int ll
#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const int N = 1e5 + 10;
struct node {
  int l, r, v, t;
} tr[N << 2];
void pushup(int u) { tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v; }
void pushdown(int u) {
  auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
  if (root.t) {
    l.t = root.t, l.v = (l.r - l.l + 1) * root.t;
    r.t = root.t, r.v = (r.r - r.l + 1) * root.t;
    root.t = 0;
  }
}
int query(int u, int l, int r) {
  if (tr[u].l >= l && tr[u].r <= r) {
    return tr[u].v;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int k = 0;
    if (l <= mid)
      k += query(u << 1, l, r);
    if (mid < r)
      k += query(u << 1 | 1, l, r);
    return k;
  }
}
void modify(int u, int l, int r, int c) {
  if (tr[u].l >= l && tr[u].r <= r) {
    tr[u].v = c * (tr[u].r - tr[u].l + 1);
    tr[u].t = c;
    return;
  } else {
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
      modify(u << 1, l, r, c);
    if (r > mid)
      modify(u << 1 | 1, l, r, c);
    pushup(u);
  }
}
void build(int u, int l, int r) {
  tr[u] = {l, r, 1, 0};
  if (l == r) {
    return;
  } else {
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    memset(tr, 0, sizeof tr);
    int n, m;
    cin >> n >> m;
    build(1, 1, n);
    for (int i = 0; i < m; i++) {
      int l, r, c;
      cin >> l >> r >> c;
      modify(1, l, r, c);
    }
    printf("Case %lld: The total value of the hook is %lld.\n", i,
           query(1, 1, n));
  }
}



imnoob
3个月前
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define Max 0x3f3f3f3f
#define Min 0x0c0c0c0c0;

// using ll = long long;
// using vi = vector<long long>;
// using vvi = vector<vector<long long>>;
const long long N = 1e5 + 10;
struct node {
  long long l, r, v, t;
} tr[N << 2];
__inline__ void pushup(long long u) { tr[u].v = tr[u << 1 | 1].v + tr[u << 1].v; }
__inline__ void pushdown(long long u) {
  if (tr[u].t) {
    node &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.t += root.t;
    l.v += (l.r - l.l + 1) * root.t;
    r.v += (r.r - r.l + 1) * root.t;
    r.t += root.t;
    root.t = 0;
  }
}
void build(long long u, long long l, long long r) {
  tr[u] = {l, r, 0, 0};
  if (l == r) {
    cin >> tr[u].v;
    return;
  }
  long long mid = (tr[u].l + tr[u].r) >> 1;
  build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  pushup(u);
}
void modify(long long u, long long l, long long r, long long c) {
  if (l <= tr[u].l && r >= tr[u].r) {
    tr[u].t += c;
    tr[u].v += (tr[u].r - tr[u].l + 1) * c;
  } else {
    pushdown(u);
    long long mid = (tr[u].r + tr[u].l) >> 1;
    if (l <= mid)
      modify(u << 1, l, r, c);
    if (r > mid)
      modify(u << 1 | 1, l, r, c);
    pushup(u);
  }
}
long long query(long long u, long long l, long long r) {
  if (l <= tr[u].l && r >= tr[u].r) {
    return tr[u].v;
  } else {
    pushdown(u);
    long long mid = (tr[u].r + tr[u].l) >> 1;
    long long v = 0;
    if (l <= mid)
      v = query(u << 1, l, r);
    if (r > mid)
      v += query(u << 1 | 1, l, r);
    return v;
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, m;
  cin >> n >> m;
  build(1, 1, n);
  // cerr << 1;
  for (long long i = 0; i < m; i++) {
    char op;
    cin >> op;
    if (op == 'Q') {
      long long a, b;
      cin >> a >> b;
      cout << query(1, a, b) << '\n';
      // cerr << 1;
    } else {
      long long a, b, c;
      cin >> a >> b >> c;
      modify(1, a, b, c);
    }
  }
}