您的位置: 首页  >  IT文章  >  统计颜色~线段树

统计颜色~线段树

分类: IT文章 • 2024-03-05 07:37:21

链接：https://www.nowcoder.com/acm/contest/105/H
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

n个桶按顺序排列，我们用1~n给桶标号。有两种操作：
1 l r c 区间[l,r]中的每个桶中都放入一个颜色为c的球 (1≤l,r ≤n,l≤r,0≤c≤60)
2 l r   查询区间[l,r]的桶中有多少种不同颜色的球     (1≤l,r ≤n,l≤r)

输入描述:

有多组数据，对于每组数据：
第一行有两个整数n,m(1≤n,m≤100000)
接下来m行，代表m个操作，格式如题目所示。

输出描述:

对于每个2号操作，输出一个整数，表示查询的结果。
示例1

输入

10 10
1 1 2 0
1 3 4 1
2 1 4
1 5 6 2
2 1 6
1 7 8 1
2 3 8
1 8 10 3
2 1 10
2 3 8

输出

2
3
2
4
3

 这题是线段树裸题 ，用位运算处理很方便

  按位或运算符（|）

  参加运算的两个对象，按二进制位进行“或”运算。

  运算规则：0|0=0；  0|1=1；  1|0=1；   1|1=1；

  即 ：参加运算的两个对象只要有一个为1，其值为1。



#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 1e5 + 10;

typedef long long LL ;
LL add[maxn << 2], sum[maxn << 2];
void pushup(LL rt) {
    sum[rt] = sum[rt << 1] | sum[rt << 1 | 1];
}
void pushdown(LL rt) {
    if (add[rt]) {
        add[rt << 1] |= add[rt];
        add[rt << 1 | 1] |= add[rt];
        sum[rt << 1] |= add[rt];
        sum[rt << 1 | 1] |= add[rt];
        add[rt] = 0;
    }
}
void updata(LL x, LL y, LL z, LL l, LL r, LL rt) {
    if (r<x || l>y ) return ;
    if (x <= l && r <= y) {
        sum[rt] |= z;
        add[rt] |= z;
        return ;
    }
    pushdown(rt);
    LL m = (l + r) >> 1;
    updata(x, y, z, l, m, rt << 1);
    updata(x, y, z, m + 1, r, rt << 1 | 1);
    pushup(rt);
}
LL query(LL x, LL y, LL l, LL r, LL rt ) {
    if (x <= l && r <= y) return sum[rt];
    pushdown(rt);
    LL ans = 0;
    LL mid = (l + r) >> 1;
    if (y > mid) ans |= query(x, y, mid + 1, r, rt << 1 | 1);
    if (x <= mid) ans |= query(x, y, l, mid, rt << 1);
    return ans;
}
LL getx(LL x) {
    LL ans = 0;
    while(x) {
        ans += x % 2;
        x /= 2;
    }
    return ans;
}
int main() {
    LL n, m;
    //freopen("DATA.txt", "r", stdin);
    while(scanf("%lld%lld", &n, &m) != EOF) {
        memset(sum, 0, sizeof(sum));
        memset(add, 0, sizeof(add));
        while(m--) {
            LL l, r, x;
            scanf("%lld", &x);
            scanf("%lld%lld", &l, &r);
            if(x == 1) {
                LL a;
                scanf("%lld", &a);
                updata(l, r, (LL)1 << a, 1, n, 1 );
            } else {
                LL t = query(l, r, 1, n, 1);
                printf("%lld
", getx(t));
            }
        }
    }
    return 0;
}


相关推荐