洛谷P1558 色板游戏 题解

高考完后随机跳题的复建运动。

看到区间覆盖操作考虑线段树。

30种颜色？用位运算存储节省空间。因为在线段树上传合并时只需要考虑这一段是否存在该颜色，（即\(0\)或\(1\)）具体位置和长度都不用考虑。（以下简称为“颜料桶”）

\(pushup\)操作:直接暴力30种颜色对比两个儿子，记录下颜色存在状况以及当前颜色数量。

\(pushdown\)：已知，向下推的标记一定都是全区间覆盖为同一种颜色，因此全部刷新，颜料桶刷为仅一种颜色，数量当然也是\(1\)。

为了方便，这里使用了结构体上下传。
具体细节看代码吧。

/*
author: Blue_Bird
2022.9.3
*/

#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

int n, cnum, q; 

struct Ge{
	int col;  // 上传当前颜色
	int ans;  
	
	Ge operator + (const Ge& a) const{
		Ge temp = (Ge){0, 0};
		int num = 0; 
		temp.col |= col; temp.col |= a.col;
		for(int i = 1; i <= cnum; i++){  // 比较颜色位置 
			if((col & (1 << i)) || (a.col & (1 << i))){
				num++; 
				 
			}  // 存在这个颜色 
		}
		temp.ans = num;
		return temp; 	
	}
} ;

struct Segment_tree{
	struct node{
		ll top;   // 位运算装颜色
		int col;   // 纯色块 
		int w; 
		
		node(){
			this->col = 0;
			this->top = 0; 
			return ; 
		}
		
	} t[N << 2];
	
	#define lson o<<1
	#define rson o<<1|1
	
	int temp = 0;  
	
	inline void pushup(int o){    //   *************此处可以优化    两边为纯色块时不需要循环判断 
		this->temp = 0; 
		for(int i = 1; i <= cnum; i++){  // 比较颜色位置 
			if((t[lson].top & (1 << i)) || (t[rson].top & (1 << i)))  // 存在这个颜色 
				this->temp += 1; 
		}
		t[o].top = 0; // 清空之前的 
		t[o].top |= t[lson].top; t[o].top |= t[rson].top;   // 两边的颜色类型合并 
		t[o].w = this->temp; 
		return ;
	}
	
	inline void pushdown(int o, int l, int r){  // 下推标记 
		if(!t[o].col) return ; 		  // 无修改 
		t[lson].col = t[o].col; t[rson].col = t[o].col; // 向下刷色 
		
		t[lson].w = t[rson].w = 1; 
		
		t[lson].top = t[rson].top = 0;     // 刷成纯色 
		t[lson].top |= (1 << t[o].col); t[rson].top |= (1 << t[o].col);   
		
		
		t[o].col = 0;    // 清空 
		return ;  
	} 
	
	void build(int o, int l, int r){
		if(l == r){
			t[o].top |= (1 << 1);   // 一号颜色为真 
			t[o].col = 1;  // 纯色块颜色为 1
			t[o].w = 1; 
			return ;  
		}
		int mid = l + r >> 1;
		build(lson, l, mid); build(rson, mid + 1, r);  
		pushup(o); 
		return ; 
	}
	
	void update(int o, int l, int r, int in, int end, int k){  // k: 修改的颜色 
		if(l > end || r < in) return ;
		if(l >= in && r <= end){  // 在刷纯色区间内 
			t[o].col = k;
			t[o].top = 0; t[o].top |= (1 << k); 
			t[o].w = 1; 
			return ; 
		}
		pushdown(o, l, r); 
		int mid = l + r >> 1;
		update(lson, l, mid, in, end, k); 
		update(rson, mid + 1, r, in, end, k);
		pushup(o);
		return ; 
	}
	
	Ge query(int o, int l, int r, int in, int end){
		if(l > end || r < in) return (Ge){0, 0}; 
		if(l >= in && r <= end){
			return (Ge){t[o].top, t[o].w}; 
		}
		pushdown(o, l, r);
		int mid = l + r >> 1;
		Ge t1, t2; 
		Ge temp = query(lson, l, mid, in, end) + query(rson, mid + 1, r, in, end); 
		return temp;  
	}	
} tree;

int main(){
//	freopen("hh.txt", "r", stdin); 
	read(n), read(cnum), read(q);
	tree.build(1, 1, n); 
	
	while(q--){
		char opt; int x, y, z, ans; 
		cin >> opt;
		switch(opt){
			case ('C'):
				read(x), read(y), read(z);
				if(x > y) swap(x, y); 
				tree.update(1, 1, n, x, y, z); 
				break; 
			case ('P'):
				read(x), read(y);
				if(x > y) swap(x, y); 
				Ge ans = tree.query(1, 1, n, x, y) ;
				printf("%d\n", ans.ans); 
				break; 
		}
	}
	
	return 0;
}