头像

皓首不倦




离线:1个月前


活动打卡代码 AcWing 2535. 二次离线莫队

皓首不倦
1个月前
/*
 *
 * 二次离线莫队算法
 *
 * 利用前缀和的思想来构造答案
 * S1(i) 表示a(1), a(2) ... a(i-1) 中和a(i)配对的数的数量
 * S2(k, i) 表示a(1), a(2) .... a(k) 中和a(i)配对的数的数量
 * a1, a2 .... an 序列里面 [L, R]区间中配对的数对个数
 * 等于sum(S1(i) - S2(L-1, i)), i = L, L+1, .... R
 *
 *
 * 首先S1是好求的,从左到右遍历一遍a序列,累加已经扫过的位置中所有数值产生的可能与其配对的数值的计数值,没到一个新
 * 位置时候,先读取前面所有数值产生了多少个当前数值的配对计数,该数值就是S1(i), 然后将统计该新加入的数值可能产生的
 * 和其配对的数值,将这些数值的计数全部加1,由于异或之后能够配对的数值是很有限的,所以每一个位置最多会有几千次更新
 * 计数的操作,复杂度还可接受
 *
 * 但是S2(L-1, i)单独在每次[L, R]的询问里面求,复杂度比较高,没法重复利用计算结果,但是如果询问量比较大,
 * 每个[L, R] 询问都会产生大量的S2(x, i)的询问,把所有S2询问全部离线收集起来,按照双关键字x排序,
 * 堆到一起算,利用莫队思想x参数从小到大右移,重复利用前面的计算结果,就可以暴力把时间复杂度压下去,所以整个
 * 是两层莫队,先构造出所有第一层莫队询问,把其中的S1询问全部算出来,然后把S2询问再用内层莫队算一次,最后组合
 * S1和S2的结果,生成最后答案
 *
 */

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


#define N 100005
int part_len;       // 分段长度

struct query_node {
    int l;
    int r;
    int idx;
    bool negative;
};

bool operator < (const query_node& n1, const query_node& n2) {
    int g1 = n1.l / part_len, g2 = n2.l / part_len;

    if (g1 != g2) {
        return g1 < g2;
    }
    return n1.r < n2.r;
}


int arr[N];
long long SS1[N];                   // S1序列的前缀和
long long cnt[(1 << 14) + 10];      // 配对数值的计数值
long long ret[N];                   // 询问的答案
vector<query_node> S2_query[N];     // 延后计算的询问
vector<query_node> tot_query;       // 外层莫队的询问
vector<int> mask;                   // 所有二进制位数中有k个1的数值

void build_s1(int n) {
    memset(cnt, 0, sizeof(cnt));

    for (int i = 1; i <= n; i++) {
        SS1[i] = SS1[i-1] + cnt[arr[i]];;
        for (auto mask_val : mask) {
            cnt[arr[i] ^ mask_val] += 1;
        }
    }
}

// 处理延后计算的询问
void process_s2_query(int n) {
    int l, r, idx;
    bool neg;

    memset(cnt, 0, sizeof(cnt));
    for (int ii = 1; ii <= n; ii++) {
        for (auto mask_val : mask) {
            cnt[arr[ii] ^ mask_val] += 1;
        }

        long long ans = 0;
        for (auto& q : S2_query[ii]) {
            l = q.l, r = q.r, idx = q.idx, neg = q.negative;

            ans = 0;
            for (int i = l; i <= r; i++) {
                ans += cnt[arr[i]];
            }

            if (neg) {
                ret[idx] -= ans;
            } else {
                ret[idx] += ans;
            }
        }
    }
}

int one_cnt(int val) {
    int ans = 0;
    while (val) {
        ans += 1;
        val &= (val - 1);
    }
    return ans;
}


int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

    int n, m, k, L, R;
    scanf("%d %d %d", &n, &m, &k);
    part_len = sqrt(n);

    for (int val = 0; val < (1 << 14); val++) {
        if (one_cnt(val) == k) {
            mask.push_back(val);
        }
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d", arr + i);
    }

    for (int idx = 0; idx < m; idx++) {
        scanf("%d %d", &L, &R);
        tot_query.push_back({L, R, idx});
    }


    build_s1(n);

    // 外层莫队
    int l, r, idx;
    sort(tot_query.begin(), tot_query.end());
    L = 1, R = 0;     // 当前处理的询问的左右边界

    for (auto&q : tot_query) {
        l = q.l, r = q.r, idx = q.idx;

        if (L < l) {
            S2_query[R].push_back({L, l-1, idx, true});
            ret[idx] += SS1[l-1] - SS1[L-1];
            if (k == 0) {
                // 处理自己匹配自己的情况
                ret[idx] += (l-1)-L+1;
            }

            L = l;
        } else if (L > l) {
            S2_query[R].push_back({l, L-1, idx, false});
            ret[idx] -= SS1[L-1] - SS1[l-1];
            if (k == 0) {
                // 处理自己匹配自己的情况
                ret[idx] -= (L-1)-l+1;
            }

            L = l;
        }

        if (R < r) {
            S2_query[L-1].push_back({R+1, r, idx, true});
            ret[idx] += SS1[r] - SS1[R];
            R = r;
        } else if (R > r) {
            S2_query[L-1].push_back({r+1, R, idx, false});
            ret[idx] -= SS1[R] - SS1[r];
            R = r;
        }
    }

    process_s2_query(n);

    // 把增量全部加和起来生成最终答案
    int idx1, idx2;
    for (int i = 1; i < m; i++) {
        idx1 = tot_query[i-1].idx;
        idx2 = tot_query[i].idx;
        ret[idx2] += ret[idx1];
    }


    for (int i = 0; i < m; i++) {
        printf("%lld\n", ret[i]);
    }

    return 0;
}





皓首不倦
1个月前

/*
 *
 * 二次离线莫队算法
 *
 * 利用前缀和的思想来构造答案
 * S1(i) 表示a(1), a(2) ... a(i-1) 中和a(i)配对的数的数量
 * S2(k, i) 表示a(1), a(2) .... a(k) 中和a(i)配对的数的数量
 * a1, a2 .... an 序列里面 [L, R]区间中配对的数对个数
 * 等于sum(S1(i) - S2(L-1, i)), i = L, L+1, .... R
 *
 *
 * 首先S1是好求的,从左到右遍历一遍a序列,累加已经扫过的位置中所有数值产生的可能与其配对的数值的计数值,没到一个新
 * 位置时候,先读取前面所有数值产生了多少个当前数值的配对计数,该数值就是S1(i), 然后将统计该新加入的数值可能产生的
 * 和其配对的数值,将这些数值的计数全部加1,由于异或之后能够配对的数值是很有限的,所以每一个位置最多会有几千次更新
 * 计数的操作,复杂度还可接受
 *
 * 但是S2(L-1, i)单独在每次[L, R]的询问里面求,复杂度比较高,没法重复利用计算结果,但是如果询问量比较大,
 * 每个[L, R] 询问都会产生大量的S2(x, i)的询问,把所有S2询问全部离线收集起来,按照双关键字x排序,
 * 堆到一起算,利用莫队思想x参数从小到大右移,重复利用前面的计算结果,就可以暴力把时间复杂度压下去,所以整个
 * 是两层莫队,先构造出所有第一层莫队询问,把其中的S1询问全部算出来,然后把S2询问再用内层莫队算一次,最后组合
 * S1和S2的结果,生成最后答案
 *
 */

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


#define N 100005
int part_len;       // 分段长度

struct query_node {
    int l;
    int r;
    int idx;
    bool negative;
};

bool operator < (const query_node& n1, const query_node& n2) {
    int g1 = n1.l / part_len, g2 = n2.l / part_len;

    if (g1 != g2) {
        return g1 < g2;
    }
    return n1.r < n2.r;
}


int arr[N];
long long SS1[N];                   // S1序列的前缀和
long long cnt[(1 << 14) + 10];      // 配对数值的计数值
long long ret[N];                   // 询问的答案
vector<query_node> S2_query[N];     // 延后计算的询问
vector<query_node> tot_query;       // 外层莫队的询问
vector<int> mask;                   // 所有二进制位数中有k个1的数值

void build_s1(int n) {
    memset(cnt, 0, sizeof(cnt));

    for (int i = 1; i <= n; i++) {
        SS1[i] = SS1[i-1] + cnt[arr[i]];;
        for (auto mask_val : mask) {
            cnt[arr[i] ^ mask_val] += 1;
        }
    }
}

// 处理延后计算的询问
void process_s2_query(int n) {
    int l, r, idx;
    bool neg;

    memset(cnt, 0, sizeof(cnt));
    for (int ii = 1; ii <= n; ii++) {
        for (auto mask_val : mask) {
            cnt[arr[ii] ^ mask_val] += 1;
        }

        long long ans = 0;
        for (auto& q : S2_query[ii]) {
            l = q.l, r = q.r, idx = q.idx, neg = q.negative;

            ans = 0;
            for (int i = l; i <= r; i++) {
                ans += cnt[arr[i]];
            }

            if (neg) {
                ret[idx] -= ans;
            } else {
                ret[idx] += ans;
            }
        }
    }
}

int one_cnt(int val) {
    int ans = 0;
    while (val) {
        ans += 1;
        val &= (val - 1);
    }
    return ans;
}


int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

    int n, m, k, L, R;
    scanf("%d %d %d", &n, &m, &k);
    part_len = sqrt(n);

    for (int val = 0; val < (1 << 14); val++) {
        if (one_cnt(val) == k) {
            mask.push_back(val);
        }
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d", arr + i);
    }

    for (int idx = 0; idx < m; idx++) {
        scanf("%d %d", &L, &R);
        tot_query.push_back({L, R, idx});
    }


    build_s1(n);

    // 外层莫队
    int l, r, idx;
    sort(tot_query.begin(), tot_query.end());
    L = 1, R = 0;     // 当前处理的询问的左右边界

    for (auto&q : tot_query) {
        l = q.l, r = q.r, idx = q.idx;

        if (L < l) {
            S2_query[R].push_back({L, l-1, idx, true});
            ret[idx] += SS1[l-1] - SS1[L-1];
            if (k == 0) {
                // 处理自己匹配自己的情况
                ret[idx] += (l-1)-L+1;
            }

            L = l;
        } else if (L > l) {
            S2_query[R].push_back({l, L-1, idx, false});
            ret[idx] -= SS1[L-1] - SS1[l-1];
            if (k == 0) {
                // 处理自己匹配自己的情况
                ret[idx] -= (L-1)-l+1;
            }

            L = l;
        }

        if (R < r) {
            S2_query[L-1].push_back({R+1, r, idx, true});
            ret[idx] += SS1[r] - SS1[R];
            R = r;
        } else if (R > r) {
            S2_query[L-1].push_back({r+1, R, idx, false});
            ret[idx] -= SS1[R] - SS1[r];
            R = r;
        }
    }

    process_s2_query(n);

    // 把增量全部加和起来生成最终答案
    int idx1, idx2;
    for (int i = 1; i < m; i++) {
        idx1 = tot_query[i-1].idx;
        idx2 = tot_query[i].idx;
        ret[idx2] += ret[idx1];
    }


    for (int i = 0; i < m; i++) {
        printf("%lld\n", ret[i]);
    }

    return 0;
}




活动打卡代码 AcWing 918. 软件包管理器

皓首不倦
1个月前

/*
 * 题目要求支持的操作有两种
 * 安装操作就是将某节点和0号节点之间的路径上的所有节点数值都变为1
 * 卸载操作就是将某节点为根的子树的所有节点数值变为0
 * 输出的是每种操作之后,状态发生变化的节点数量,其实也就是操作前1的总数和操作后1总数的差值的绝对值
 *
 * 通过LCT将树上操作转换为线性区间操作,上面两种操作就是标准的线段树操作,线段树上维护好
 * 懒标记和区间和即可
 *
 */

#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

#define      N      (100008)

// LCT 相关定义
vector<int> link[N];
int dfs_id[N];              // 节点的dfs序id
int head_id[N];             // 节点对应的链的开始节点id
int fa[N];                  // 父节点id
int sub_tree_start[N];      // 子树对应的dfs序区间开始位置
int sub_tree_end[N];        // 子树对应的dfs序区间结束为止
int dep[N];                 // 节点深度
int heavy_child[N];         // 节点的重儿子节点id
int is_heavy[N];            // 节点是否是重儿子节点

// 线段树相关定义
int L[N<<2];
int R[N<<2];
long long val[N << 2];
long long add_flag[N << 2]; // lazy标记

void push_up(int idx) {
    val[idx] = val[idx << 1] + val[(idx<<1) + 1];
}

void push_down(int idx) {
    if (add_flag[idx] == -1) {
        return;
    }

    int l = idx << 1, r = (idx << 1) + 1;
    add_flag[l] = add_flag[idx];
    val[l] = add_flag[idx] * (R[l] - L[l] + 1);
    add_flag[r] = add_flag[idx];
    val[r] = add_flag[idx] * (R[r] - L[r] + 1);

    add_flag[idx] = -1;
}

void build_seg_tree(int idx, int start, int end) {
    L[idx] = start, R[idx] = end, add_flag[idx] = 0;

    if (start == end) {
        val[idx] = 0;
        return;
    }

    int mid = start + ((end-start) >> 1);
    build_seg_tree(idx<<1, start, mid);
    build_seg_tree((idx<<1)+1, mid+1, end);
    push_up(idx);
}

// 区间值修改为k
void change_range(int idx, int start, int end, int k) {
    if (start == L[idx] and end == R[idx]) {
        add_flag[idx] = k;
        val[idx] = k * (R[idx] - L[idx] + 1);
        return;
    }

    push_down(idx);
    int mid = L[idx] + ((R[idx]-L[idx]) >> 1);
    if (end <= mid) {
        change_range(idx << 1, start, end, k);
    } else if (start >= mid+1) {
        change_range((idx<<1) + 1, start, end, k);
    } else {
        change_range(idx <<1 , start, mid, k);
        change_range((idx<<1) + 1, mid+1, end, k);
    }

    push_up(idx);
}


void add_edge(int a, int b) {
    link[a].push_back(b);
    link[b].push_back(a);
}

int dfs1(int cur, int prev, int d) {
    fa[cur] = prev;
    dep[cur] = d;

    int tot_size = 1;
    int max_s = -1, max_root = 0, s = 0;
    for (auto next : link[cur]) {
        if (next != prev) {
            s = dfs1(next, cur, d+1);
            if (s > max_s) {
                max_s = s;
                max_root = next;
            }

            tot_size += s;
        }
    }

    heavy_child[cur] = max_root;
    return tot_size;
}

void dfs2(int cur, int h, int prev, int& id) {
    head_id[cur] = h;
    dfs_id[cur] = id++;

    if (heavy_child[cur]) {
        dfs2(heavy_child[cur], h, cur, id);
    }

    for (auto next : link[cur]) {
        if (next != prev && next != heavy_child[cur]) {
            if (is_heavy[next]) {
                dfs2(next, h, cur, id);
            } else {
                dfs2(next, next, cur, id);
            }
        }
    }

    sub_tree_start[cur] = dfs_id[cur];
    sub_tree_end[cur] = id-1;
}

void build_lct() {
    dfs1(1, 0, 1);
    int id = 1;
    dfs2(1, 1, 0, id);
}

// 修改区段上每一个节点的数值为0或者1
long long change_lct_ranges(int a, int b, int k) {
    int ha, hb;
    long long sum1, sum2;

    long long t = val[1];
    while (1) {
        ha = head_id[a];
        hb = head_id[b];

        if (ha == hb) {
            a = dfs_id[a], b = dfs_id[b];
            if (a > b) {
                swap(a, b);
            }
            change_range(1, a, b, k);

            break;
        } else {
            if (dep[ha] < dep[hb]) {
                swap(a, b);
                swap(ha, hb);
            }

            change_range(1, dfs_id[ha], dfs_id[a], k);

            a = fa[ha];
        }
    }

    return abs(t - val[1]);
}

// 修改子树对应的区间上所有节点数值为0或者1
long long change_sub_tree_range(int node_id, int k) {
    int start = sub_tree_start[node_id];
    int end =  sub_tree_end[node_id];

    int t = val[1];
    change_range(1, start, end, k);

    return abs(t - val[1]);
}

int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

    int n, m, node;
    scanf("%d", &n);

    for (int i = 2; i <= n; i++) {
        scanf("%d", &node);
        node++;

        add_edge(i, node);
    }

    build_lct();
    build_seg_tree(1, 1, n);

    scanf("%d", &m);
    char cmd[20];
    while (m--) {
        scanf("%s %d", cmd, &node);
        node++;

        if (strcmp(cmd, "install") == 0) {
            printf("%lld\n", change_lct_ranges(1, node, 1));
        } else {
            printf("%lld\n", change_sub_tree_range(node, 0));
        }
    }

    return 0;
}





皓首不倦
1个月前

/*
 * 题目要求支持的操作有两种
 * 安装操作就是将某节点和0号节点之间的路径上的所有节点数值都变为1
 * 卸载操作就是将某节点为根的子树的所有节点数值变为0
 * 输出的是每种操作之后,状态发生变化的节点数量,其实也就是操作前1的总数和操作后1总数的差值的绝对值
 *
 * 通过LCT将树上操作转换为线性区间操作,上面两种操作就是标准的线段树操作,线段树上维护好
 * 懒标记和区间和即可
 *
 */

#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

#define      N      (100008)

// LCT 相关定义
vector<int> link[N];
int dfs_id[N];              // 节点的dfs序id
int head_id[N];             // 节点对应的链的开始节点id
int fa[N];                  // 父节点id
int sub_tree_start[N];      // 子树对应的dfs序区间开始位置
int sub_tree_end[N];        // 子树对应的dfs序区间结束为止
int dep[N];                 // 节点深度
int heavy_child[N];         // 节点的重儿子节点id
int is_heavy[N];            // 节点是否是重儿子节点

// 线段树相关定义
int L[N<<2];
int R[N<<2];
long long val[N << 2];
long long add_flag[N << 2]; // lazy标记

void push_up(int idx) {
    val[idx] = val[idx << 1] + val[(idx<<1) + 1];
}

void push_down(int idx) {
    if (add_flag[idx] == -1) {
        return;
    }

    int l = idx << 1, r = (idx << 1) + 1;
    add_flag[l] = add_flag[idx];
    val[l] = add_flag[idx] * (R[l] - L[l] + 1);
    add_flag[r] = add_flag[idx];
    val[r] = add_flag[idx] * (R[r] - L[r] + 1);

    add_flag[idx] = -1;
}

void build_seg_tree(int idx, int start, int end) {
    L[idx] = start, R[idx] = end, add_flag[idx] = 0;

    if (start == end) {
        val[idx] = 0;
        return;
    }

    int mid = start + ((end-start) >> 1);
    build_seg_tree(idx<<1, start, mid);
    build_seg_tree((idx<<1)+1, mid+1, end);
    push_up(idx);
}

// 区间值修改为k
void change_range(int idx, int start, int end, int k) {
    if (start == L[idx] and end == R[idx]) {
        add_flag[idx] = k;
        val[idx] = k * (R[idx] - L[idx] + 1);
        return;
    }

    push_down(idx);
    int mid = L[idx] + ((R[idx]-L[idx]) >> 1);
    if (end <= mid) {
        change_range(idx << 1, start, end, k);
    } else if (start >= mid+1) {
        change_range((idx<<1) + 1, start, end, k);
    } else {
        change_range(idx <<1 , start, mid, k);
        change_range((idx<<1) + 1, mid+1, end, k);
    }

    push_up(idx);
}


void add_edge(int a, int b) {
    link[a].push_back(b);
    link[b].push_back(a);
}

int dfs1(int cur, int prev, int d) {
    fa[cur] = prev;
    dep[cur] = d;

    int tot_size = 1;
    int max_s = -1, max_root = 0, s = 0;
    for (auto next : link[cur]) {
        if (next != prev) {
            s = dfs1(next, cur, d+1);
            if (s > max_s) {
                max_s = s;
                max_root = next;
            }

            tot_size += s;
        }
    }

    heavy_child[cur] = max_root;
    return tot_size;
}

void dfs2(int cur, int h, int prev, int& id) {
    head_id[cur] = h;
    dfs_id[cur] = id++;

    if (heavy_child[cur]) {
        dfs2(heavy_child[cur], h, cur, id);
    }

    for (auto next : link[cur]) {
        if (next != prev && next != heavy_child[cur]) {
            if (is_heavy[next]) {
                dfs2(next, h, cur, id);
            } else {
                dfs2(next, next, cur, id);
            }
        }
    }

    sub_tree_start[cur] = dfs_id[cur];
    sub_tree_end[cur] = id-1;
}

void build_lct() {
    dfs1(1, 0, 1);
    int id = 1;
    dfs2(1, 1, 0, id);
}

// 修改区段上每一个节点的数值为0或者1
long long change_lct_ranges(int a, int b, int k) {
    int ha, hb;
    long long sum1, sum2;

    long long t = val[1];
    while (1) {
        ha = head_id[a];
        hb = head_id[b];

        if (ha == hb) {
            a = dfs_id[a], b = dfs_id[b];
            if (a > b) {
                swap(a, b);
            }
            change_range(1, a, b, k);

            break;
        } else {
            if (dep[ha] < dep[hb]) {
                swap(a, b);
                swap(ha, hb);
            }

            change_range(1, dfs_id[ha], dfs_id[a], k);

            a = fa[ha];
        }
    }

    return abs(t - val[1]);
}

// 修改子树对应的区间上所有节点数值为0或者1
long long change_sub_tree_range(int node_id, int k) {
    int start = sub_tree_start[node_id];
    int end =  sub_tree_end[node_id];

    int t = val[1];
    change_range(1, start, end, k);

    return abs(t - val[1]);
}

int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

    int n, m, node;
    scanf("%d", &n);

    for (int i = 2; i <= n; i++) {
        scanf("%d", &node);
        node++;

        add_edge(i, node);
    }

    build_lct();
    build_seg_tree(1, 1, n);

    scanf("%d", &m);
    char cmd[20];
    while (m--) {
        scanf("%s %d", cmd, &node);
        node++;

        if (strcmp(cmd, "install") == 0) {
            printf("%lld\n", change_lct_ranges(1, node, 1));
        } else {
            printf("%lld\n", change_sub_tree_range(node, 0));
        }
    }

    return 0;
}




活动打卡代码 AcWing 2568. 树链剖分

皓首不倦
1个月前
/*
 * 树链剖分模板题,将树上路径相关的查询问题转化为
 * DFS序上的区间查询问题
 */

#include <vector>
#include <algorithm>
using namespace std;

#define      N      (100008)

// LCT 相关定义
vector<int> link[N];
int dfs_id[N];              // 节点的dfs序id
int head_id[N];             // 节点对应的链的开始节点id
int fa[N];                  // 父节点id
int sub_tree_start[N];      // 子树对应的dfs序区间开始位置
int sub_tree_end[N];        // 子树对应的dfs序区间结束为止
int dep[N];                 // 节点深度
int heavy_child[N];         // 节点的重儿子节点id
int is_heavy[N];            // 节点是否是重儿子节点

// 线段树相关定义
int L[N<<2];
int R[N<<2];
long long val[N << 2];
long long add_flag[N << 2]; // lazy标记

void push_up(int idx) {
    val[idx] = val[idx << 1] + val[(idx<<1) + 1];
}

void push_down(int idx) {
    if (add_flag[idx] == 0) {
        return;
    }

    int l = idx << 1, r = (idx << 1) + 1;
    add_flag[l] += add_flag[idx];
    val[l] += add_flag[idx] * (R[l] - L[l] + 1);
    add_flag[r] += add_flag[idx];
    val[r] += add_flag[idx] * (R[r] - L[r] + 1);

    add_flag[idx] = 0;
}

void build_seg_tree(int idx, int start, int end, int* data) {
    L[idx] = start, R[idx] = end, add_flag[idx] = 0;

    if (start == end) {
        val[idx] = data[start];
        return;
    }

    int mid = start + ((end-start) >> 1);
    build_seg_tree(idx<<1, start, mid, data);
    build_seg_tree((idx<<1)+1, mid+1, end, data);
    push_up(idx);
}

void add_range(int idx, int start, int end, int k) {
    if (start == L[idx] && end == R[idx]) {
        add_flag[idx] += k;
        val[idx] += k * (R[idx] - L[idx] + 1);
        return;
    }

    push_down(idx);
    int mid = L[idx] + ((R[idx]-L[idx]) >> 1);
    if (end <= mid) {
        add_range(idx << 1, start, end, k);
    } else if (start >= mid + 1) {
        add_range((idx<<1) + 1, start, end, k);
    } else {
        add_range(idx<<1, start, mid, k);
        add_range((idx<<1) + 1, mid+1, end, k);
    }
    push_up(idx);
}

long long get_range(int idx, int start, int end) {
    if (start == L[idx] && end == R[idx]) {
        return val[idx];
    }

    push_down(idx);
    long long ans = 0;
    int mid = L[idx] + ((R[idx]-L[idx]) >> 1);
    if (end <= mid) {
        ans = get_range(idx<<1, start, end);
    } else if (start >= mid + 1) {
        ans = get_range((idx<<1) + 1, start, end);
    } else {
        ans += get_range(idx<<1, start, mid);
        ans += get_range((idx<<1) + 1, mid+1, end);
    }

    return ans;
}


void add_edge(int a, int b) {
    link[a].push_back(b);
    link[b].push_back(a);
}

int dfs1(int cur, int prev, int d) {
    fa[cur] = prev;
    dep[cur] = d;

    int tot_size = 1;
    int max_s = -1, max_root = 0, s = 0;
    for (auto next : link[cur]) {
        if (next != prev) {
            s = dfs1(next, cur, d+1);
            if (s > max_s) {
                max_s = s;
                max_root = next;
            }

            tot_size += s;
        }
    }

    heavy_child[cur] = max_root;
    return tot_size;
}

void dfs2(int cur, int h, int prev, int& id) {
    head_id[cur] = h;
    dfs_id[cur] = id++;

    if (heavy_child[cur]) {
        dfs2(heavy_child[cur], h, cur, id);
    }

    for (auto next : link[cur]) {
        if (next != prev && next != heavy_child[cur]) {
            if (is_heavy[next]) {
                dfs2(next, h, cur, id);
            } else {
                dfs2(next, next, cur, id);
            }
        }
    }

    sub_tree_start[cur] = dfs_id[cur];
    sub_tree_end[cur] = id-1;
}

void build_lct() {
    dfs1(1, 0, 1);
    int id = 1;
    dfs2(1, 1, 0, id);
}

void add_lct_ranges(int a, int b, int k) {
    int ha, hb;
    while (1) {
        ha = head_id[a];
        hb = head_id[b];

        if (ha == hb) {
            a = dfs_id[a], b = dfs_id[b];
            if (a > b) {
                swap(a, b);
            }

            add_range(1, a, b, k);
            break;
        } else {
            if (dep[ha] < dep[hb]) {
                swap(a, b);
                swap(ha, hb);
            }

            add_range(1, dfs_id[ha], dfs_id[a], k);
            a = fa[ha];
        }
    }
}

long long get_lct_range(int a, int b) {
    int ha, hb;
    long long ans = 0;

    while (1) {
        ha = head_id[a];
        hb = head_id[b];

        if (ha == hb) {
            a = dfs_id[a], b = dfs_id[b];
            if (a > b) {
                swap(a, b);
            }

            ans += get_range(1, a, b);
            break;
        } else {
            if (dep[ha] < dep[hb]) {
                swap(a, b);
                swap(ha, hb);
            }

            ans += get_range(1, dfs_id[ha], dfs_id[a]);
            a = fa[ha];
        }
    }

    return ans;
}

void add_sub_tree_range(int node_id, int k) {
    add_range(1, sub_tree_start[node_id], sub_tree_end[node_id], k);
}

long long get_sub_tree_range(int node_id) {
    return get_range(1, sub_tree_start[node_id], sub_tree_end[node_id]);
}

int arr[N];
int new_arr[N];

int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

    int n, m, a, b, cmd, k;
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", arr + i);
    }

    for (int i = 0; i < n-1; i++) {
        scanf("%d %d", &a, &b);
        add_edge(a, b);
    }

    build_lct();

    for (int node = 1; node <= n; node++) {
        new_arr[dfs_id[node]] = arr[node];
    }

    build_seg_tree(1, 1, n, new_arr);

    scanf("%d", &m);
    while (m--) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d %d %d", &a, &b, &k);
            add_lct_ranges(a, b, k);
        } else if (cmd == 2) {
            scanf("%d %d", &a, &k);
            add_sub_tree_range(a, k);
        } else if (cmd == 3) {
            scanf("%d %d", &a, &b);
            printf("%lld\n", get_lct_range(a, b));
        } else {
            scanf("%d", &a);
            printf("%lld\n", get_sub_tree_range(a));
        }
    }

    return 0;
}



皓首不倦
1个月前

/*
 * 树链剖分模板题,将树上路径相关的查询问题转化为
 * DFS序上的区间查询问题
 */

#include <vector>
#include <algorithm>
using namespace std;

#define      N      (100008)

// LCT 相关定义
vector<int> link[N];
int dfs_id[N];              // 节点的dfs序id
int head_id[N];             // 节点对应的链的开始节点id
int fa[N];                  // 父节点id
int sub_tree_start[N];      // 子树对应的dfs序区间开始位置
int sub_tree_end[N];        // 子树对应的dfs序区间结束为止
int dep[N];                 // 节点深度
int heavy_child[N];         // 节点的重儿子节点id
int is_heavy[N];            // 节点是否是重儿子节点

// 线段树相关定义
int L[N<<2];
int R[N<<2];
long long val[N << 2];
long long add_flag[N << 2]; // lazy标记

void push_up(int idx) {
    val[idx] = val[idx << 1] + val[(idx<<1) + 1];
}

void push_down(int idx) {
    if (add_flag[idx] == 0) {
        return;
    }

    int l = idx << 1, r = (idx << 1) + 1;
    add_flag[l] += add_flag[idx];
    val[l] += add_flag[idx] * (R[l] - L[l] + 1);
    add_flag[r] += add_flag[idx];
    val[r] += add_flag[idx] * (R[r] - L[r] + 1);

    add_flag[idx] = 0;
}

void build_seg_tree(int idx, int start, int end, int* data) {
    L[idx] = start, R[idx] = end, add_flag[idx] = 0;

    if (start == end) {
        val[idx] = data[start];
        return;
    }

    int mid = start + ((end-start) >> 1);
    build_seg_tree(idx<<1, start, mid, data);
    build_seg_tree((idx<<1)+1, mid+1, end, data);
    push_up(idx);
}

void add_range(int idx, int start, int end, int k) {
    if (start == L[idx] && end == R[idx]) {
        add_flag[idx] += k;
        val[idx] += k * (R[idx] - L[idx] + 1);
        return;
    }

    push_down(idx);
    int mid = L[idx] + ((R[idx]-L[idx]) >> 1);
    if (end <= mid) {
        add_range(idx << 1, start, end, k);
    } else if (start >= mid + 1) {
        add_range((idx<<1) + 1, start, end, k);
    } else {
        add_range(idx<<1, start, mid, k);
        add_range((idx<<1) + 1, mid+1, end, k);
    }
    push_up(idx);
}

long long get_range(int idx, int start, int end) {
    if (start == L[idx] && end == R[idx]) {
        return val[idx];
    }

    push_down(idx);
    long long ans = 0;
    int mid = L[idx] + ((R[idx]-L[idx]) >> 1);
    if (end <= mid) {
        ans = get_range(idx<<1, start, end);
    } else if (start >= mid + 1) {
        ans = get_range((idx<<1) + 1, start, end);
    } else {
        ans += get_range(idx<<1, start, mid);
        ans += get_range((idx<<1) + 1, mid+1, end);
    }

    return ans;
}


void add_edge(int a, int b) {
    link[a].push_back(b);
    link[b].push_back(a);
}

int dfs1(int cur, int prev, int d) {
    fa[cur] = prev;
    dep[cur] = d;

    int tot_size = 1;
    int max_s = -1, max_root = 0, s = 0;
    for (auto next : link[cur]) {
        if (next != prev) {
            s = dfs1(next, cur, d+1);
            if (s > max_s) {
                max_s = s;
                max_root = next;
            }

            tot_size += s;
        }
    }

    heavy_child[cur] = max_root;
    return tot_size;
}

void dfs2(int cur, int h, int prev, int& id) {
    head_id[cur] = h;
    dfs_id[cur] = id++;

    if (heavy_child[cur]) {
        dfs2(heavy_child[cur], h, cur, id);
    }

    for (auto next : link[cur]) {
        if (next != prev && next != heavy_child[cur]) {
            if (is_heavy[next]) {
                dfs2(next, h, cur, id);
            } else {
                dfs2(next, next, cur, id);
            }
        }
    }

    sub_tree_start[cur] = dfs_id[cur];
    sub_tree_end[cur] = id-1;
}

void build_lct() {
    dfs1(1, 0, 1);
    int id = 1;
    dfs2(1, 1, 0, id);
}

void add_lct_ranges(int a, int b, int k) {
    int ha, hb;
    while (1) {
        ha = head_id[a];
        hb = head_id[b];

        if (ha == hb) {
            a = dfs_id[a], b = dfs_id[b];
            if (a > b) {
                swap(a, b);
            }

            add_range(1, a, b, k);
            break;
        } else {
            if (dep[ha] < dep[hb]) {
                swap(a, b);
                swap(ha, hb);
            }

            add_range(1, dfs_id[ha], dfs_id[a], k);
            a = fa[ha];
        }
    }
}

long long get_lct_range(int a, int b) {
    int ha, hb;
    long long ans = 0;

    while (1) {
        ha = head_id[a];
        hb = head_id[b];

        if (ha == hb) {
            a = dfs_id[a], b = dfs_id[b];
            if (a > b) {
                swap(a, b);
            }

            ans += get_range(1, a, b);
            break;
        } else {
            if (dep[ha] < dep[hb]) {
                swap(a, b);
                swap(ha, hb);
            }

            ans += get_range(1, dfs_id[ha], dfs_id[a]);
            a = fa[ha];
        }
    }

    return ans;
}

void add_sub_tree_range(int node_id, int k) {
    add_range(1, sub_tree_start[node_id], sub_tree_end[node_id], k);
}

long long get_sub_tree_range(int node_id) {
    return get_range(1, sub_tree_start[node_id], sub_tree_end[node_id]);
}

int arr[N];
int new_arr[N];

int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

    int n, m, a, b, cmd, k;
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", arr + i);
    }

    for (int i = 0; i < n-1; i++) {
        scanf("%d %d", &a, &b);
        add_edge(a, b);
    }

    build_lct();

    for (int node = 1; node <= n; node++) {
        new_arr[dfs_id[node]] = arr[node];
    }

    build_seg_tree(1, 1, n, new_arr);

    scanf("%d", &m);
    while (m--) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d %d %d", &a, &b, &k);
            add_lct_ranges(a, b, k);
        } else if (cmd == 2) {
            scanf("%d %d", &a, &k);
            add_sub_tree_range(a, k);
        } else if (cmd == 3) {
            scanf("%d %d", &a, &b);
            printf("%lld\n", get_lct_range(a, b));
        } else {
            scanf("%d", &a);
            printf("%lld\n", get_sub_tree_range(a));
        }
    }

    return 0;
}



活动打卡代码 AcWing 2534. 树上计数2

皓首不倦
1个月前
'''
思路
1. 首先将节点的数值进行离散化
2. 构造树的欧拉序列
3. 将两个树节点之间路径转换为欧拉序列上的一个区间,每一个询问都可以转换为一个欧拉序列上区间的询问
4. 莫队算法暴力求解区间询问
'''

import sys
import math
from collections import deque

sys.setrecursionlimit(9999999)

class LCA:
    # edges 为所有树中的无向边,max_node_num为节点数,节点编号为0, 1, 2, ...... (max_node_num-1)
    # 0号节点是整个树的根
    def __init__(self, edges, max_node_num):
        self.max_node_num = max_node_num
        link = [[] for i in range(max_node_num)]
        self.__max_dep = 0
        for a, b in edges:
            link[a].append(b)
            link[b].append(a)

        self.dep = [0] * self.max_node_num      # 每个节点的深度
        fa = [0] * self.max_node_num            # 每个节点的父节点

        # bfs一次把每个节点的父节点和深度求出
        def __bfs():
            que = deque()
            que.append(0)
            visit = [0] * self.max_node_num
            visit[0] = 1

            depth = 0
            while len(que) > 0:
                node_num = len(que)
                for _ in range(node_num):
                    cur = que.popleft()
                    self.dep[cur] = depth
                    self.__max_dep = max(self.__max_dep, depth)

                    for child in link[cur]:
                        if visit[child] == 0:
                            visit[child] = 1
                            fa[child] = cur
                            que.append(child)

                depth += 1

        __bfs()

        # f[i][j] 表示节点向上跳跃2^j步后的祖先节点标号
        self.max_j = int(math.log2(self.__max_dep)) + 1
        self.f = [[0] * (self.max_j + 1) for _ in range(self.max_node_num)]

        for i in range(self.max_node_num):
            self.f[i][0] = fa[i]

        for j in range(1, self.max_j+1):
            for i in range(self.max_node_num):
                self.f[i][j] = self.f[ self.f[i][j-1] ][j-1]

    # 获取a, b 两个节点的最近公共祖先编号
    def get_lca(self, a, b):
        if self.dep[a] > self.dep[b]:
            a, b = b, a

        sub_dep = self.dep[b] - self.dep[a]
        if sub_dep > 0:
            # b 移动到和 a 同一层
            j = 0
            while sub_dep:
                if sub_dep & 1 != 0:
                    b = self.f[b][j]

                sub_dep >>= 1
                j += 1

        # a, b两个点本来就是祖孙关系,直接返回
        if a == b:
            return a

        # 两个节点同时上移
        j = min(int(math.log2(self.dep[a])) + 1, self.max_j)
        while j >= 0:
            aa, bb = self.f[a][j], self.f[b][j]
            if aa != bb:
                a, b = aa, bb
            j -= 1

        return self.f[a][0]

n, m = map(int, input().split())
s = sys.stdin.readline()
arr = list(map(int, s.split()))

new_arr = arr[::]
new_arr.sort()
map_vec = []        # 离散化表

last_val = -0x7fffffff
for val in new_arr:
    if val != last_val:
        map_vec.append(val)
    last_val = val

def get_map_val(val):
    l, r = 0, len(map_vec)
    while l <= r:
        mid = (l + r) >> 1
        if map_vec[mid] == val:
            return mid
        elif map_vec[mid] < val:
            l = mid + 1
        else:
            r = mid - 1

    return None

# 离散化
arr = [get_map_val(val) for val in arr]

edges = []
for _ in range(n-1):
    s = sys.stdin.readline()
    a, b = map(int, s.split())
    edges.append((a-1, b-1))

# 获取树的欧拉序列
first, second = [0x7fffffff] * (n), [0x7fffffff] * (n)    # 每个点第一次和第二次出现的位置
def get_eulur_list(e):
    path = [0] * (2*n)
    link = [[] for _ in range(n)]

    for a, b in e:
        link[a].append(b)
        link[b].append(a)

    top = [0]
    def dfs(cur, prev):
        path[top[0]] = cur
        first[cur] = top[0]
        top[0] += 1

        for next in link[cur]:
            if next != prev:
                dfs(next, cur)

        path[top[0]] = cur
        second[cur] = top[0]
        top[0] += 1

    dfs(0, None)
    return path

eulur_arr = get_eulur_list(edges)

# 将原始询问转换为欧拉序列中的询问
lca = LCA(edges, max_node_num=n)
query = [None for _ in range(m)]
part_len = int(math.sqrt(2*n))
for idx in range(m):
    s = sys.stdin.readline()
    a, b = map(int, s.split())
    a, b = a-1, b-1

    if first[a] > first[b]:
        a, b = b, a

    lca_node = lca.get_lca(a, b)
    if lca_node == a:
        l, r, extra = first[a], first[b], None
    else:
        l, r, extra = second[a], first[b], lca_node # 序列中需要补一个最近公共祖先

    if (l // part_len) & 1:
        query[idx] = (l // part_len, r, r, l, extra, idx)
    else:
        query[idx] = (l // part_len, 0x7ffffff-r, r, l, extra, idx)

query.sort()

# 求取欧拉序列每一个区间[l, r]中出现一次的点对应的权值的不同个数
i, j = 0, 0
cnt = [0] * len(map_vec)        # 离散化后节点权值出现的次数计数
stat = [0] * (n)                # 节点id出现的奇偶性
ans = 0
ret = [0] * m

def add(node_id):
    global ans

    w_val = arr[node_id]

    stat[node_id] ^= 1
    if stat[node_id]:
        cnt[w_val] += 1
        if cnt[w_val] == 1:
            ans += 1
    else:
        cnt[w_val] -= 1
        if cnt[w_val] == 0:
            ans -= 1

add(eulur_arr[0])

for _, _, r, l, extra, idx in query:

    if i < l:
        while i != l:
            add(eulur_arr[i])
            i += 1

    elif i > l:
        while i != l:
            i -= 1
            add(eulur_arr[i])

    if j < r:
        while j != r:
            j += 1
            add(eulur_arr[j])

    elif j > r:
        while j != r:
            add(eulur_arr[j])
            j -= 1

    if extra is not None:
        add(extra)

    ret[idx] = ans

    if extra is not None:
        add(extra)


for val in ret:
    print(val)


活动打卡代码 AcWing 2523. 历史研究

皓首不倦
1个月前

'''
总体思想
带回滚机制的莫队,通过回滚机制保证增量计算时候,只有加法没有减法
规避减法难以维护的问题
'''

import sys
import math

n, m = map(int, input().split())

s = sys.stdin.readline()
arr = list(map(int, s.split()))

new_arr = arr[::]
new_arr.sort()
map_arr = []        # 离散化去重之后的表
last_val = -0x7fffffff
for val in new_arr:
    if val != last_val:
        map_arr.append(val)
    last_val = val

# 不同数值的个数
diff_val_num = len(map_arr)

# 根据数值获取离散化后的下标
def val2map_idx(val):
    l, r = 0, diff_val_num-1
    while l <= r:
        mid = (l + r) >> 1
        if map_arr[mid] == val:
            return mid
        elif map_arr[mid] < val:
            l = mid + 1
        else:
            r = mid - 1
    return None

arr = [val2map_idx(val) for val in arr]


q_arr = []
part_len = int(math.sqrt(n))

ss = sys.stdin.readlines()

for idx, s in enumerate(ss):
    l, r  = map(int, s.split())
    l, r = l-1, r-1

    q_arr.append((l // part_len, r, l, idx))

ret = [0] * m
q_arr.sort()

last_group = -1
ans = None
flag = False
for group, r, l, idx in q_arr:

    if group != last_group:
        # 刚刚进入一个新的组, 进行初始化
        c = [0] * diff_val_num        # 数值计数的Counter
        max_val = None  # 从j所在的组开始位置到j位置的区间中统计出来的最大值
        j = None        # 右端点位置
        flag = True

    if r // part_len == group:
        # 左右端点在同一个组里面, 直接暴力求解
        tmp_ans = 0
        for pos in range(l, r+1):
            val = arr[pos]
            c[val] += 1
            tmp_ans = max(tmp_ans, map_arr[val] * c[val])
        ret[idx] = tmp_ans

        for pos in range(l, r+1):
            c[arr[pos]] -= 1

    else:
        if flag:
            flag = False
            j = (group+1) * part_len    # 下一组刚开始的位置
            c[arr[j]] = 1
            max_val = map_arr[arr[j]]

        # j一定是向右移动的,这里只维护j的移动,左端点位置一定是在当前组里面,左端点多出来的部分暴力添加
        # 这样所有操作中就只有加没有减,这样才能顺利进行增量计算
        while j != r:
            j += 1
            c[arr[j]] += 1
            max_val = max(max_val, c[arr[j]]* map_arr[arr[j]])

        # 下面暴力把剩下的在本分组的部分区间加上
        i = (group+1) * part_len
        ans = max_val
        while i != l:
            i -= 1
            c[arr[i]] += 1
            ans = max(ans, c[arr[i]]* map_arr[arr[i]])

        ret[idx] = ans

        # 将暴力加的部分回滚回去,把c的计数值恢复
        for i in range(l, (group+1) * part_len):
            c[arr[i]] -= 1

    last_group = group

for pos in range(len(q_arr)):
    print(ret[pos])





皓首不倦
1个月前

'''
总体思想
带回滚机制的莫队,通过回滚机制保证增量计算时候,只有加法没有减法
规避减法难以维护的问题
'''

import sys
import math

n, m = map(int, input().split())

s = sys.stdin.readline()
arr = list(map(int, s.split()))

new_arr = arr[::]
new_arr.sort()
map_arr = []        # 离散化去重之后的表
last_val = -0x7fffffff
for val in new_arr:
    if val != last_val:
        map_arr.append(val)
    last_val = val

# 不同数值的个数
diff_val_num = len(map_arr)

# 根据数值获取离散化后的下标
def val2map_idx(val):
    l, r = 0, diff_val_num-1
    while l <= r:
        mid = (l + r) >> 1
        if map_arr[mid] == val:
            return mid
        elif map_arr[mid] < val:
            l = mid + 1
        else:
            r = mid - 1
    return None

arr = [val2map_idx(val) for val in arr]


q_arr = []
part_len = int(math.sqrt(n))

ss = sys.stdin.readlines()

for idx, s in enumerate(ss):
    l, r  = map(int, s.split())
    l, r = l-1, r-1

    q_arr.append((l // part_len, r, l, idx))

ret = [0] * m
q_arr.sort()

last_group = -1
ans = None
flag = False
for group, r, l, idx in q_arr:

    if group != last_group:
        # 刚刚进入一个新的组, 进行初始化
        c = [0] * diff_val_num        # 数值计数的Counter
        max_val = None  # 从j所在的组开始位置到j位置的区间中统计出来的最大值
        j = None        # 右端点位置
        flag = True

    if r // part_len == group:
        # 左右端点在同一个组里面, 直接暴力求解
        tmp_ans = 0
        for pos in range(l, r+1):
            val = arr[pos]
            c[val] += 1
            tmp_ans = max(tmp_ans, map_arr[val] * c[val])
        ret[idx] = tmp_ans

        for pos in range(l, r+1):
            c[arr[pos]] -= 1

    else:
        if flag:
            flag = False
            j = (group+1) * part_len    # 下一组刚开始的位置
            c[arr[j]] = 1
            max_val = map_arr[arr[j]]

        # j一定是向右移动的,这里只维护j的移动,左端点位置一定是在当前组里面,左端点多出来的部分暴力添加
        # 这样所有操作中就只有加没有减,这样才能顺利进行增量计算
        while j != r:
            j += 1
            c[arr[j]] += 1
            max_val = max(max_val, c[arr[j]]* map_arr[arr[j]])

        # 下面暴力把剩下的在本分组的部分区间加上
        i = (group+1) * part_len
        ans = max_val
        while i != l:
            i -= 1
            c[arr[i]] += 1
            ans = max(ans, c[arr[i]]* map_arr[arr[i]])

        ret[idx] = ans

        # 将暴力加的部分回滚回去,把c的计数值恢复
        for i in range(l, (group+1) * part_len):
            c[arr[i]] -= 1

    last_group = group

for pos in range(len(q_arr)):
    print(ret[pos])



活动打卡代码 AcWing 2521. 数颜色

皓首不倦
1个月前
'''
本质还是莫队算法,只不过除了区间左右位置以外,还需要
多维护一个时间维度,所以是三维的莫队
'''


import sys
import math

n, m = map(int, input().split())
s = sys.stdin.readline()
arr = list(map(int, s.split()))
new_arr = arr[::]

part_len = math.sqrt(n)
change_rec = [(0, 0, 0)]       # change_rec[i] = (pos, a, b)表示第i次时间戳对应的修改是将pos位置的数值从a修改为b

his = {}

# 返回pos位置在时间戳为t时刻的数值
def get_val(pos, t):
    if pos not in his or t < his[pos][0][0]:
        return arr[pos]
    else:
        l, r = 0, len(his[pos])-1
        ans = None
        while l <= r:
            mid = (l + r) >> 1
            if his[pos][mid][0] <= t:
                ans = his[pos][mid][1]
                l = mid + 1
            else:
                r = mid - 1
        return ans


flag = False
if n == 10000 and m == 10000:
    flag = True


q_arr = []
idx = 0
time_stamp = 0
for _ in range(m):
    s = sys.stdin.readline()
    if s[0] == 'Q':
        l, r  = map(int, s[2:].split())
        l, r = l-1, r-1

        q_arr.append((l // part_len, r, time_stamp, l, idx))
        idx += 1
    else:
        pos, new_val = map(int, s[2:].split())
        pos -= 1

        change_rec.append((pos, new_arr[pos], new_val))
        new_arr[pos] = new_val
        time_stamp += 1

        if pos not in his:
            his[pos] = []
        his[pos].append((time_stamp, new_val))


q_arr.sort()
i, j, k, ans = 0, 0, 0, 1
cnt = [0] * 1000005
cnt[arr[0]] = 1

ret = [0] * m

for _, r, t, l, query_idx in q_arr:

    if i < l:
        while i != l:
            val = get_val(i, k)
            cnt[val] -= 1
            if cnt[val] == 0:
                ans -= 1
            i += 1
    elif i > l:
        while i != l:
            i -= 1
            val = get_val(i, k)
            cnt[val] += 1
            if cnt[val] == 1:
                ans += 1

    if j < r:
        while j != r:
            j += 1
            val = get_val(j, k)
            cnt[val] += 1
            if cnt[val] == 1:
                ans += 1
    elif j > r:
        while j != r:
            val = get_val(j, k)
            cnt[val] -= 1
            if cnt[val] == 0:
                ans -= 1
            j -= 1

    if k < t:
        while k != t:
            k += 1
            pos, old_val, new_val = change_rec[k]
            if pos >= l and pos <= r:
                cnt[old_val] -= 1
                if cnt[old_val] == 0:
                    ans -= 1

                cnt[new_val] += 1
                if cnt[new_val] == 1:
                    ans += 1
    elif k > t:
        while k != t:
            pos, old_val, new_val = change_rec[k]
            if pos >= l and pos <= r:
                cnt[new_val] -= 1
                if cnt[new_val] == 0:
                    ans -= 1

                cnt[old_val] += 1
                if cnt[old_val] == 1:
                    ans += 1
            k -= 1

    ret[query_idx] = ans

for i in range(len(q_arr)):
    print(ret[i])