#P9627. 生日

    ID: 6243 传统题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1600普及+/提高-懒标记线段树位集求并位计数

生日

题目描述

今天是牛牛的生日,牛牛请了他的好朋友们一起过生日,生日必不可少的环节当然就是吃蛋糕啦。

由于有 n n 个人来参加牛牛的生日,牛牛需要给 n n 个人分蛋糕,

牛牛有 2 2 种操作:

C C l,r,x l,r,x 将 [l,r] [l,r] 的人的蛋糕数改成 x(1≤x≤k) x(1 \le x \le k) 。

P P l,r l,r 查询 [l,r] [l,r] 中有多少种不同的蛋糕数。

牛牛总共执行了 m m 次这样的操作,请输出所有的询问操作所对应的答案。

你可以认为初始时每个人有 11 块蛋糕。

输入格式

第一行三个数 n,m,k n,m,k 。

接下来 m m 行,每行一次操作,含义见题目描述。

输出格式

对于每个询问,输出一行表示答案。

样例

2 4 2
C 1 1 2
P 1 2
C 2 2 2
P 1 2
2
1

数据范围

对于 30% 30\% 的数据: n,m≤1000 n,m\le 1000 。

对于 50% 50\% 的数据: n,m≤5×104n,m\le 5\times 10^4 。

对于 100% 100\% 的数据: 1≤l≤r≤n≤105 1\le l \le r \le n \le 10^5 , 1≤m≤1051\le m \le 10^5 , 1≤k≤301\le k \le 30 。