题目大意：D表示在区间x，y内所有的元素扩充一倍;Q表示查询在这个下表以内的数字最多的个数为多少。
如：1,2,3.D 1 3 之后就变成了 1 1 2 2 3 3.Q 1 4 输出 2.
解题思路：每个节点记录两个信息：最大值的个数以及这个点一共有多少个数字。
A simple simulation problem.
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 580 Accepted Submission(s): 227
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
#include
#include
#include
#include
#include
#define LL long long using namespace std; const int maxn = 101000; LL num[maxn<<2]; LL Max[maxn<<2]; void Bulid(int l, int r, int site) { Max[site] = 1LL; if(l == r) { num[site] = 1LL; return; } int mid = (l+r)>>1; Bulid(l, mid, site<<1); Bulid(mid+1, r, site<<1|1); num[site] = num[site<<1]+num[site<<1|1]; } void Push_Up(int site) { Max[site] = max(Max[site<<1], Max[site<<1|1]); num[site] = num[site<<1]+num[site<<1|1]; } void Update(int l, int r, LL ll, LL rr, int site) { if(l == r) { num[site] += (rr-ll+1); Max[site] = num[site]; return; } LL tmp = num[site<<1]; int mid = (l+r)>>1; if(rr <= tmp) Update(l, mid, ll, rr, site<<1); else if(ll > tmp) Update(mid+1, r, ll-tmp, rr-tmp, site<<1|1); else { Update(l, mid, ll, tmp, site<<1); Update(mid+1, r, 1, rr-tmp, site<<1|1); } Push_Up(site); } LL Query(int l, int r, LL ll, LL rr, int site) { if(num[site] == (rr-ll+1)) return Max[site]; if(l == r) return (rr-ll+1); LL tmp = num[site<<1]; int mid = (l+r)>>1; if(rr <= tmp) return Query(l, mid, ll, rr, site<<1); else if(ll > tmp) return Query(mid+1, r, ll-tmp, rr-tmp, site<<1|1); else return max(Query(l, mid, ll, tmp, site<<1), Query(mid+1, r, 1, rr-tmp, site<<1|1)); } int main() { int T; int Case = 1; cin >>T; char str[110]; while(T--) { printf("Case #%d:\n", Case++); int n, m; scanf("%d %d",&n, &m); Bulid(1, n, 1); LL x, y; while(m--) { scanf("%s",str); scanf("%I64d %I64d",&x, &y); if(str[0] == 'D') Update(1, n, x, y, 1); else printf("%I64d\n",Query(1, n, x, y, 1)); } } }