数颜色

本该是暑假集训的高级数据结构的练习题,按照出题大佬的本意要用树套树做的,然而那玩意太麻烦了不会写于是学了学传闻中能解决一切区间问题的莫队算法。具体的使用在我题目中写的注释很详细网上也有很多莫队算法的教程我就不展开说明了。

学习笔记:

  • 不带修改的分块每块大小:sqrt(n),理论时间复杂度O(n*sqrt(n))
  • 带单点修改的分块大小:n2/3,理论时间复杂度O(n5/3)
  • 单点修改的修改过程记录修改前和修改后的值而不是初始值和修改后的值
  • 排序关键字:左区间所在块号,右区间所在块号,修改的时间(如果存在修改)
  • 主要结构

    • 状态转移函数

      • 区间转移(步长为1)
      • 时间转移(步长为1)
    • 数据读入
    • 询问(修改)排序
    • 对询问循环

      • 对时间进行状态转移
      • 对区间进行转移
      • 记录当前询问的答案
    • 输出答案

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2120

题解

高档题。题意大概是单点修改和区间查询,区间查询要求得到某一区间内的颜色数。
套可持久化的莫队算法。

代码

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;

const int N = 10005;
const int COLORNUM = 1000005;

struct Query {
    int l, r, time, id;
}q[N];//询问情况
struct Change {
    int pos, New, Old; 
}c[N];//改变情况
int n, m;
int s[N], color[COLORNUM], now[N],ans[N];//s初始输入 now记录某次变量转移后的情况 color记录某种颜色的数量情况 ans记录询问的答案情况
int t, Time, unit, Ans, l(1), r, T;//t记录询问次数 Time记录更改次数 unit记录单元大小 Ans记录当前区间与修改时间的答案 l,r记录当前区间左右端点 T记录当前修改到具体某一次

inline int whichUnit(int a) {//判断当前位置处于哪一个unit
    return a / unit + 1;
}

inline bool cmp(Query a, Query b)//以区间左,右端点,询问时间排序,其中左,右端点分别以unit来划分;
{
    return whichUnit(a.l) == whichUnit(b.l) ? (whichUnit(a.r) == whichUnit(b.r) ? a.time<b.time : a.r<b.r) : a.l<b.l;
}

inline void revise(int x, int d) {//转移状态,以某次区间修改转移
    color[x] += d; 
    if (d>0)Ans += color[x] == 1;
    if (d<0)Ans -= color[x] == 0;
}

inline void going(int x, int d) {//转移状态,以某次颜色修改转移
    if (l <= x && x <= r) {
        revise(d, 1);
        revise(s[x], -1);
    }
    s[x] = d;
}

int main() {
    scanf("%d%d", &n, &m);
    unit = pow(n, (double)2 / 3);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        now[i] = s[i];
    }
    for (int i = 1; i <= m; i++) {
        char type; 
        int x, y; 
        scanf(" %c %d%d", &type, &x, &y);
        if (type == 'Q')q[++t] = Query{ x, y, Time, t };
        if (type == 'R')c[++Time] = Change{ x, y, now[x] }, now[x] = y;
    }
    sort(q + 1, q + t + 1, cmp);

    for (int i = 1; i <= t; i++)
    {
        while (T<q[i].time)going(c[T + 1].pos, c[T + 1].New), T++;
        while (T>q[i].time)going(c[T].pos, c[T].Old), T--;

        while (l<q[i].l)revise(s[l], -1), l++;
        while (l>q[i].l)revise(s[l - 1], 1), l--;
        while (r<q[i].r)revise(s[r + 1], 1), r++;
        while (r>q[i].r)revise(s[r], -1), r--;

        ans[q[i].id] = Ans;
    }
    for (int i = 1; i <= t; i++)
        printf("%d\n", ans[i]);
}

标签: 莫队算法

添加新评论