也是写上了今年的第一篇题解

~~~~Aurelia~~~~

2026-08-21 13:07:48

发布于：浙江

2阅读

0回复

0点赞

看我们可以被把本题抽象一下

$有一个length为 n 的序列，序列一开始为均为 1,有q 次询问，2种操作\\ C : 改变 A ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ B 的value 为 C\\P : 查询 A ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ B 有几类value$

这恰恰和我们的线段树

不谋而合

（Tim经典语录）、

于是

建树函数

void Union (long long root,long long l,long long r) {
    tree [root].l = l;
    tree [root].r = r;
    tree [root].n = 1;
     if (l == r) {
        //如果不能再分就stop
        return;j
    }
    long long mid = (l + r) >> 1;
    Union (root * 2,l,mid);
    //遍历left端点
    Union (root * 2 + 1,mid + 1,r);
    //遍历right端点
}

改变colour 函数

void Push (long long root,long long l,long long r,long long a,long long b,long long c) {
    if (a <= l && r <= b) {
        // 如果当前节点被包含了 更新数值并stop
        tree [root].n = (1 << (c - 1));
        // 更新懒mark 等孩子需要时再给更新
        tree [root].lan = (1 << (c - 1));
		return;
    }
    lg (root);// 更新子节点的懒mark
    long long mid = (l + r) >> 1;
    if (a <= mid)
        Push (root * 2,l,mid,a,b,c);//如果包含答案遍历
    if (b > mid)
        Push (root * 2 + 1,mid + 1,r,a,b,c);//如果包含答案遍历
    tree[root].n = tree[root * 2].n | tree[root * 2 + 1].n;// 以子节点更新父节点
}

更新子节点懒mark 函数

void lg (long long x) {
	if (tree[x].lan) {
		tree[x * 2].n = tree[x].lan;
		tree[x * 2 + 1].n = tree[x].lan;
		tree[x * 2].lan = tree[x].lan;
		tree[x * 2 + 1].lan = tree[x].lan;	
		long long root = x;
		tree[x].lan = 0;
	}
}

区间查询函数

long long Find (long long root,long long l,long long r,long long a,long long b) {
	long long ans = 0;
    //用bit运算统计状态
    if (a <= l && r <= b) {
        return tree[root].n;
    }
    lg (root);// 更新子节点的懒mark
    long long mid = (l + r) >> 1;
    if (a <= mid)
        ans |= Find (root * 2,l,mid,a,b);//如果包含答案遍历
    //用bit运算统计状态
    if (b > mid)
        ans |= Find (root * 2 + 1,mid + 1,r,a,b);//如果包含答案遍历
    //用bit运算统计状态
    return ans;// return 答案
}

完整代码

#include <bits/stdc++.h>
using namespace std;
struct Node {
    long long l,r,n,lan;
}tree[4000005];
long long L,t,o;
void lg (long long x) {
	if (tree[x].lan) {
		tree[x * 2].n = tree[x].lan;
		tree[x * 2 + 1].n = tree[x].lan;
		tree[x * 2].lan = tree[x].lan;
		tree[x * 2 + 1].lan = tree[x].lan;	
		long long root = x;
		tree[x].lan = 0;
	}
}
void Union (long long root,long long l,long long r) {
    if (l == r) {
        tree [root].l = l;
        tree [root].r = r;
        tree [root].n = 1;
        return;
    }
    tree [root].l = l;
    tree [root].r = r;
    tree [root].n = 1;
    long long mid = (l + r) >> 1;
    Union (root * 2,l,mid);
    Union (root * 2 + 1,mid + 1,r);
}
void Push (long long root,long long l,long long r,long long a,long long b,long long c) {
    if (a <= l && r <= b) {
        tree [root].n = (1 << (c - 1));
        tree [root].lan = (1 << (c - 1));
		return;
    }
    lg (root);
    long long mid = (l + r) >> 1;
    if (a <= mid)
        Push (root * 2,l,mid,a,b,c);
    if (b > mid)
        Push (root * 2 + 1,mid + 1,r,a,b,c);
    tree[root].n = tree[root * 2].n | tree[root * 2 + 1].n;
}
long long Find (long long root,long long l,long long r,long long a,long long b) {
	long long ans = 0;
    if (a <= l && r <= b) {
        return tree[root].n;
    }
    lg (root);
    long long mid = (l + r) >> 1;
    if (a <= mid)
        ans |= Find (root * 2,l,mid,a,b);
    if (b > mid)
        ans |= Find (root * 2 + 1,mid + 1,r,a,b);
    return ans;
}
int main () {
    cin >> L >> t >> o;
    Union (1,1,L);
    while (o --) {
        char op;
        cin >> op;
        if (op == 'C') {
            long long a,b,c;
            cin >> a >> b >> c;
            if (a > b)swap (a,b);
            Push (1,1,L,a,b,c);
        }
        if (op == 'P') {
            long long a,b;
            cin >> a >> b;
            if (a > b)swap (a,b);
            cout << __builtin_popcount (Find (1,1,L,a,b)) << "\n";
        }
    } 
    return 0;
}