时间戳

首页 > 技术文章 > POJ 2777 Count Color

POJ 2777 Count Color

luckyblock 2020-10-17 19:49 原文

知识点：线段树

原题面：poj

扯

练手题，区间修改不写懒标记，傻逼！

题意简述

给定一长度为 \(n\) 的序列 \(a\)，参数 \(T\)。
给定 \(m\) 次操作，每次操作是下面两种形式之一：

  1. 区间修改为给定值。
  2. 查询区间内权值种类数。

\(1\le n,m \le 10^5\)，\(1\le a_i\le T\le 30\)。

分析题意

考虑用线段树维护区间内权值的出现情况。

发现 \(a_i\le T\le 30\)，权值的种类很少。
对于一个区间，直接用一个 int 二进制状压一下，维护区间内某权值是否出现过。
两区间权值的出现情况，即为两变量的或。
区间内权值的种类数，即为二进制中 1 的个数。

对于区间修改操作，直接将指定区间覆盖即可。

由于需要查询二进制中 1 的个数，代码中使用了 bitset 进行实现。

爆零小技巧

区间修改不写懒标记，傻逼！

代码实现

//知识点：线段树 
/*
By:Luckyblock
*/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <cstring>
#define LL long long
const int kMaxn = 1e5 + 10;
const int kMaxT = 30 + 5;
//=============================================================
int n, m, T;
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
namespace Seg {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  std::bitset <kMaxT> col[kMaxn << 2];
  int tag[kMaxn << 2];
  void Pushup(int now_) {
    col[now_] = col[ls] | col[rs];
  }
  void Pushdown(int now_) {
    if (! tag[now_]) return ;
    col[ls].reset(); col[ls].set(tag[now_], true);
    col[rs].reset(); col[rs].set(tag[now_], true);
    tag[ls] = tag[rs] = tag[now_];
    tag[now_] = 0;
  }
  void Build(int now_, int L_, int R_) {
    col[now_].reset();
    col[now_].set(1, true);
    if (L_ == R_) return ;
    Build(ls, L_, mid), Build(rs, mid + 1, R_);
  }
  void Modify(int now_, int L_, int R_, int l_, int r_, int pos_) {
    if (l_ <= L_ && R_ <= r_) {
      col[now_].reset();
      col[now_].set(pos_, true);
      tag[now_] = pos_;
      return ;
    }
    Pushdown(now_);
    if (l_ <= mid) Modify(ls, L_, mid, l_, r_, pos_);
    if (r_ > mid) Modify(rs, mid + 1, R_, l_, r_, pos_);
    Pushup(now_);
  }
  std::bitset <kMaxT> Query(int now_, int L_, int R_, int l_, int r_) {
    if (l_ <= L_ && R_ <= r_) return col[now_];
    Pushdown(now_);
    if (r_ <= mid) return Query(ls, L_, mid, l_, r_);
    if (l_ > mid) return Query(rs, mid + 1, R_, l_, r_);
    return (Query(ls, L_, mid, l_, mid) | Query(rs, mid + 1, R_, mid + 1, r_));
  }
  #undef ls
  #undef rs
  #undef mid
}
//=============================================================
int main() {
  n = read(), T = read(), m = read();
  Seg::Build(1, 1, n);
  while (m --) {
    char opt[5] = "";
    scanf("%s", opt + 1);
    int l = read(), r = read();
    if (l > r) std::swap(l, r);
    if (opt[1] == 'C') {
      int pos = read();
      Seg::Modify(1, 1, n, l, r, pos);
    } else {
      std::bitset <kMaxT> ans = Seg::Query(1, 1, n, l, r);
      printf("%d\n", ans.count());
    }
  }
  return 0;
}

推荐阅读