/** * poj 2777(线段树) * 题意:1至L的染色板,初始化都是1号色,[1,T]种不同的颜色,可进行O次操作。 * 操作有两种: * C A B C 将染色板A到B所有的格子染成C号色 * P A B 询问染色板A到B中颜色的种数 */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; class Node { int left; int right; int color; } public class Main { // Scanner sc = new Scanner(System.in);//采用Scanner 读取数据会超时 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int L, T, O; Node[] node = new Node[300005]; boolean[] visit = new boolean[35]; void build(int left, int right, int i) { node[i] = new Node(); node[i].left = left; node[i].right = right; node[i].color = 1; if (left != right) { int mid = (left + right) / 2; build(left, mid, i * 2); build(mid + 1, right, i * 2 + 1); } } void update(int left, int right, int c, int i) { if (node[i].left == left && node[i].right == right) node[i].color = c; else { if (node[i].color != -1) { node[i * 2].color = node[i].color; node[i * 2 + 1].color = node[i].color; node[i].color = -1; // 表示此区间不止一种色调 } int mid = (node[i].left + node[i].right) / 2; if (right <= mid) update(left, right, c, 2 * i); else if (left >= mid + 1) update(left, right, c, 2 * i + 1); else { update(left, mid, c, 2 * i); update(mid + 1, right, c, 2 * i + 1); } } } void find(int left, int right, int i) { if (node[i].color != -1) visit[node[i].color] = true; else { int mid = (node[i].left + node[i].right) / 2; if (right <= mid) find(left, right, 2 * i); else if (left >= mid + 1) find(left, right, 2 * i + 1); else { find(left, mid, 2 * i); find(mid + 1, right, 2 * i + 1); } } } void init() throws IOException { String[] s = in.readLine().split(" "); L = Integer.parseInt(s[0]); T = Integer.parseInt(s[1]); O = Integer.parseInt(s[2]); build(1, L, 1); int a, b, c, temp; while (O-- > 0) { s = in.readLine().split(" "); if (s[0].equals("C")) { a = Integer.parseInt(s[1]); b = Integer.parseInt(s[2]); c = Integer.parseInt(s[3]); if (a > b) { temp = a; a = b; b = temp; } update(a, b, c, 1); } else { a = Integer.parseInt(s[1]); b = Integer.parseInt(s[2]); if (a > b) { temp = a; a = b; b = temp; } Arrays.fill(visit, false); find(a, b, 1); int sum = 0; for (int i = 0; i < 35; i++) if (visit[i]) sum++; System.out.println(sum); } } } public static void main(String[] args) throws Exception { new Main().init(); }