您的位置: 首页  >  IT文章  >  AcWing算法进阶课 莫队

AcWing算法进阶课 莫队

分类: IT文章 • 2022-04-12 20:15:01

AcWing算法进阶课 莫队

 基础莫队

2492. HH的项链

题目：

HH 有一串由各种漂亮的贝壳组成的项链。

HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。

HH 不断地收集新的贝壳，因此他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？

这个问题很难回答，因为项链实在是太长了。

于是，他只好求助睿智的你，来解决这个问题。

输入格式

第一行：一个整数 N，表示项链的长度。

第二行：1000000 之间的整数）。

第三行：一个整数 M，表示 HH 询问的个数。

接下来 R，表示询问的区间。

输出格式

M 行，每行一个整数，依次表示询问对应的答案。

数据范围

1≤L≤R≤N

输入样例：

6
1 2 3 4 3 5
3
1 2
3 5
2 6

输出样例：

2
2
4

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 50010, M = 200010, S = 1000010;
int n, m, T;
int w[N], ans[M];
struct Q{
  int l, r, i, x, y;
  inline Q() {}
  inline Q(int l, int r, int i) : l(l), r(r), i(i) {x = l / T, y = r;}
  inline friend bool operator< (const Q &a, const Q &b)
  {
      return a.x == b.x ? (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
  }
}q[M];
int cnt[S];

void add(int x, int& res)
{
  //第一次出现，说明出现了新的贝壳，标记+1
  if (!cnt[x]) res ++;
  cnt[x] ++;
}

void del(int x, int& res)
{
  //将当前-1，如果-1为0，则贝壳种类-1
  cnt[x] --;
  if (!cnt[x]) res --;
}

int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  scanf("%d", &m);
  T = sqrt((double) n * n / m);

  for (int i = 0; i < m; i ++ )
  {
    int l, r; scanf("%d%d", &l, &r);
    q[i] = {l, r, i};
  }
  sort(q, q + m);
//   for (int i = 0; i < m; i ++ ) 
//     printf("[l = %d, r = %d]
", q[i].l, q[i].r);
  for (int k = 0, l = 1, r = 0, res = 0; k < m; k ++ )
  {
    while (l < q[k].l) del(w[l ++ ], res);
    while (l > q[k].l) add(w[-- l ], res);
    while (r < q[k].r) add(w[++ r ], res);
    while (r > q[k].r) del(w[r -- ], res);
    ans[q[k].i] = res; 
  }
  for (int i = 0; i < m; i ++ ) printf("%d
", ans[i]);
  
  return 0;
}

　　

待修莫队

2521. 数颜色

题目：

墨墨购买了一套 N 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。

墨墨会像你发布如下指令：

  1. Q L R 代表询问你从第 R 支画笔*有几种不同颜色的画笔。
  2. R P Col 把第 Col。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入格式

第 N,M，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第 i 支画笔的颜色。

第 2+M 行，每行分别代表墨墨会做的一件事情，格式见题*分。

输出格式

对于每一个 Query 的询问，你需要在对应的行中给出一个数字，代表第 R 支画笔*有几种不同颜色的画笔。

数据范围

106。

输入样例：

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

输出样例：

4
4
3
4

分析：

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 10010, S = 1000010;
int n, m, mq, mc, len;
int w[N], cnt[S], ans[N];
struct Query{
  int id, l, r, t;
}q[N];
struct Modify{
  int p, c; 
}c[N];
int get(int x)
{
  return x / len;
}
bool cmp(const Query& a, const Query& b)
{
  int al = get(a.l), ar = get(a.r);
  int bl = get(b.l), br = get(b.r);
  if (al != bl) return al < bl;
  if (ar != br) return ar < br;
  return a.t < b.t;
}
void add(int x, int& res)
{
  if (!cnt[x]) res ++;
  cnt[x] ++; 
}
void del(int x, int& res)
{
  cnt[x] --;
  if (!cnt[x]) res --;
}
int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  for (int i = 0; i < m; i ++ )
  {
    char op[3];
    int a, b; 
    scanf("%s%d%d", op, &a, &b);
    if (*op == 'Q')
    {
      //多加一维，t，表示在查询区间[L,R]的时候，已经修改了t次，可以将t理解为时间范围[1,m]
      q[++ mq] = {mq, a, b, mc};
    }
    else 
    { 
      c[++ mc] = {a, b};
    }
  }

  len = cbrt((double)n * mc) + 1;
  sort(q + 1, q + 1 + mq, cmp);
  for (int i = 1, l = 1, r = 0, t = 0, res = 0; i <= mq; i ++ )
  {
    while (l < q[i].l) del(w[l ++ ], res);
    while (l > q[i].l) add(w[-- l ], res);
    while (r < q[i].r) add(w[++ r ], res);
    while (r > q[i].r) del(w[r -- ], res);
    while (t < q[i].t)
    {
      t ++;
      if (c[t].p >= l && c[t].p <= r) 
      {
        del(w[c[t].p], res);
        add(c[t].c, res);
      }
      swap(w[c[t].p], c[t].c);
    }
    while (t > q[i].t)
    {
      if (c[t].p >= l && c[t].p <= r)
      {
        del(w[c[t].p], res);
        add(c[t].c, res);
      }
      swap(w[c[t].p], c[t].c);
      t --;      
    }
    ans[q[i].id] = res;
  }
  for (int i = 1; i <= mq; i ++ ) printf("%d
", ans[i]);
  return 0;
}

　　

回滚莫队

2523. 历史研究

题目：

IOI 国历史研究的第一人——JOI 教授，最近获得了一份被认为是古代 IOI 国的住民写下的日记。

JOI 教授为了通过这份日记来研究古代 IOI 国的生活，开始着手调查日记中记载的事件。

日记中记录了连续 N 天发生的时间，大约每天发生一件。

事件有种类之分。第 Xi 越大，事件的规模就越大。

JOI 教授决定用如下的方法分析这些日记：

  1. 选择日记中连续的一些天作为分析的时间段
  2. 事件种类 t 的事件数)
  3. 计算出所有事件种类的重要度，输出其中的最大值

现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

输入格式

第一行两个空格分隔的整数 Q 次。

接下来一行 i 天发生的事件的种类。

接下来 [Ai,Bi]。

输出格式

输出 i 次询问的最大重要度。

数据范围

1≤Xi≤109

输入样例：

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

输出样例：

9
8
8
16
16

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m, T;
int a[N], cnt[N];
LL ans[N];
struct Query{
  int id, l, r;
}q[N];
vector<int> nums;
int get(int x)
{
  return x / T;
}
bool cmp(const Query& a, const Query& b)
{
  int x = get(a.l), y = get(b.l);
  if (x != y) return x < y;
  return a.r < b.r;
}
void add(int x, LL& ans)
{
  if (!cnt[x]) ans ++;
  cnt[x] ++;
}
int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i ++ ) 
  {
    scanf("%d", &a[i]);
    nums.push_back(a[i]);
  }
  sort(nums.begin(), nums.end());
  nums.erase(unique(nums.begin(), nums.end()), nums.end());
  for (int i = 1; i <= n; i ++ ) 
    a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin();
  for (int i = 0; i < m; i ++ )
  {
    int l, r; scanf("%d%d", &l, &r);
    q[i] = {i, l, r};
  }
  sort(q, q + m);
  for (int x; x < m;)
  {
    int y = x;
    //将左区间在同一块内的所有区间找到
    while (y < m && get(q[x].l) == get(q[y].l)) y ++;
    //找到当前块的区间右端点
    int right = get(q[x].l) * T + T - 1;
    //将所有在同一块内的所有询问暴力求解
    while (x < y && q[x].r <= right)
    {
      LL res = 0;
      for (int i = q[x].l; i <= q[x].r; i ++ ) add(a[i], res);
      ans[q[x].id] = res;
      //这里的每个询问的区间左端点是按照分块排序的，所以，在分块内，不具有递增性
      //所以，我们不可能只进行add操作就可以将区间求解出来，而是需要不断地反复求取
      //所以，在求解的时候，需要add，再清空，再add
      for (int i = q[x].l; i <= q[x].r; i ++ ) cnt[a[i]] --;
      x ++;
    }
    //求块间的询问，询问的区间左端点在同一块中，右端点在其他块中，按递增顺序
    LL res = 0;
    int l = right + 1, r = right;
    while (x < y)
    {
      //将r扩展到当前询问的区间右端点，在后面的块内
      while (r < q[x].r) add(a[++ r], res);
      //res在后面的分块内是不变的，但是会被l所在分块修改，所以，先备份后面分块的res
      LL backup = res;
      //将l扩展到当前询问的区间左端点，在l所在的块内
      while (l > q[x].l) add(a[-- l], res);
      ans[q[x].id] = res;
      //将l所在块内造成的影响清除掉[保证了只会删到第一个区间的right]
      while (l < right + 1) cnt[a[x ++ ]] --;
      //恢复后面分块的res，消除l所在分块的影响
      res = backup;
      x ++;
    }
    //每移动到新的分块后，我们的区间左端点的add要重算，不如直接清空了
    memset(cnt, 0, sizeof cnt);
  }
  for (int i = 0; i < m; i ++ ) printf("%lld
", ans[i]);
  return 0;
}

　　

树上莫队

2534. 树上计数

题目：

给定一棵 N，每个节点都有一个整数权值。

现在，我们要进行 v 的路径上（包括两端点）共有多少种不同的点权值。

输入格式

第一行包含两个整数 N,M。

第二行包含 i 的权值。

接下来 y 之间存在一条边。

最后 u,v，表示一个询问。

输出格式

共 M 行，每行输出一个询问的答案。

数据范围

int 范围内。

输入样例：

8 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
3 8

输出样例：

4
4

分析：

树上的莫队，通过DFS序，或者说欧拉序列将树上的节点，映射成下标

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, len;
int h[N], e[N], ne[N], idx;
int w[N];
vector<int> nums;
int fa[N][17], depth[N];
int seq[N], top, first[N], last[N];
int cnt[N], st[N], ans[N];
struct Query{
  int id, l, r, p;
}q[N];

void add_edges(int a, int b)
{
  e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int x, int father)
{
  seq[++ top] = x;
  first[x] = top;
  for (int i = h[x]; ~i; i = ne[i])
  {
    int y = e[i];
    if (y == father) continue;
    dfs(y, x);
  }
  seq[ ++ top] = x;
  last[x] = top;
}
void bfs()
{
  memset(depth, 0x3f, sizeof depth);
  depth[0] = 0, depth[1] = 1;
  queue<int> q;
  q.push(1);
  while (!q.empty())
  {
    int x = q.front();
    q.pop();
    for (int i = h[x]; ~i; i = ne[i])
    {
      int y = e[i];
      if (depth[y] > depth[x] + 1)
      {
        depth[y] = depth[x] + 1;
        q.push(y);
        fa[y][0] = x;
        for (int k = 1; k <= 16; k ++ )
          fa[y][k] = fa[fa[y][k - 1]][k - 1];
      }
    }
  }
}
int LCA(int x, int y)
{
  if (depth[x] < depth[y]) swap(x, y);
  for (int k = 16; k >= 0; k -- )
    if (depth[fa[x][k]] >= depth[y])
      x = fa[x][k];
  if (x == y) return y;
  for (int k = 15; k >= 0; k -- )
    if (fa[x][k] != fa[y][k])
    {
      x = fa[x][k];
      y = fa[y][k];
    }
  return fa[x][0];
}
int get(int x)
{
  return x / len;
}
bool cmp(const Query& a, Query& b)
{
  int x = get(a.l), y = get(b.l);
  if (x != y) return x < y;
  return a.r < b.r;
}
void add(int x, int& res)
{
  //注意这里的x是传入的树的节点，也就是我们映射后的数组下标，并不是元素值
  st[x] ^= 1;
  if (st[x] == 0)
  {
    cnt[w[x]] --;
    if (!cnt[w[x]]) res --;
  }
  else
  {
    if (!cnt[w[x]]) res ++;
    cnt[w[x]] ++;
  }
}
int main()
{
  memset(h, -1, sizeof h);
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i ++ )
  {
    scanf("%d", &w[i]);
    nums.push_back(w[i]);
  }
  sort(nums.begin(), nums.end());
  nums.erase(unique(nums.begin(), nums.end()), nums.end());
  for (int i = 1; i <= n; i ++ )
    w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();
  for (int i = 0; i < n - 1; i ++ )
  {
    int x, y; scanf("%d%d", &x, &y);
    add_edges(x, y); add_edges(y, x);
  }
  dfs(1, -1);
  bfs();
  for (int i = 0; i < m; i ++ )
  {
    int x, y; scanf("%d%d", &x, &y);
    if (first[x] > first[y]) swap(x, y);
    int father = LCA(x, y);
    if (father == x) q[i] = {i, first[x], first[y]};
    else q[i] = {i, last[x], first[y], father};
  }
  len = sqrt(top);
  sort(q, q + m, cmp);
  for (int i = 0, l = 1, r = 0, res = 0; i < m; i ++ )
  {
    while (l < q[i].l) add(seq[l ++ ], res);
    while (l > q[i].l) add(seq[-- l ], res);
    while (r < q[i].r) add(seq[++ r ], res);
    while (r > q[i].r) add(seq[r -- ], res);
    if (q[i].p) add(q[i].p, res);
    ans[q[i].id] = res;
    if (q[i].p) add(q[i].p, res);
   }
  for (int i = 0; i < m; i ++ ) printf("%d
", ans[i]);
  return 0;
}

　　

相关推荐