首页 > 代码库 > 2014多校10(1003)hdu4973(简单线段树区间操作)

2014多校10(1003)hdu4973(简单线段树区间操作)

A simple simulation problem.

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 679    Accepted Submission(s): 269


Problem Description
There are n types of cells in the lab, numbered from 1 to n. These cells are put in a queue, the i-th cell belongs to type i. Each time I can use mitogen to double the cells in the interval [l, r]. For instance, the original queue is {1 2 3 3 4 5}, after using a mitogen in the interval [2, 5] the queue will be {1 2 2 3 3 3 3 4 4 5}. After some operations this queue could become very long, and I can’t figure out maximum count of cells of same type. Could you help me?
 

Input
The first line contains a single integer t (1 <= t <= 20), the number of test cases.

For each case, the first line contains 2 integers (1 <= n,m<= 50000) indicating the number of cell types and the number of operations.

For the following m lines, each line represents an operation. There are only two kinds of operations: Q and D. And the format is:

“Q l r”, query the maximum number of cells of same type in the interval [l, r];
“D l r”, double the cells in the interval [l, r];

(0 <= r – l <= 10^8, 1 <= l, r <= the number of all the cells)
 

Output
For each case, output the case number as shown. Then for each query "Q l r", print the maximum number of cells of same type in the interval [l, r].

Take the sample output for more details.
 

Sample Input
1 5 5 D 5 5 Q 5 6 D 2 3 D 1 2 Q 1 7
 

Sample Output
Case #1: 2 3

题意:两种操作,D L R 将L到R区间的数的数量加倍,Q L R 查询区间内数量最多的数的个数

思路:由于初始给出的是1到n按顺序,那么无论怎么加倍,相同的数一定排在一起,这样可以用线段树维护整个序列,值为每个数的个数

            D L R 先将L点和R点的数的数量增加一定数量(不一定是加倍),然后将L+1到R-1的数的数量加倍
 
            Q L R 在L点,R点和[L+1,R-1]的选一个最大值

<script src="https://code.csdn.net/snippets/464113.js" type="text/javascript"></script>

2014多校10(1003)hdu4973(简单线段树区间操作)