HDU 4973

只需要使用线段树进行一些基本的区间操作就可以了。很简单的题。

A simple simulation problem.

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

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

Source

2014 Multi-University Training Contest 10

代码：

/* ***
Author :kuangbin
Created Time :2014/8/21 13:16:18
File Name :20140821\1003.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 50010;
struct Node{
int l,r;
long long Max;
long long sum;
long long lazy;
}segTree[MAXN<<2];
void push_up(int i){
if(segTree[i].l == segTree[i].r)return;
segTree[i].sum = segTree[i<<1].sum + segTree[(i<<1)|1].sum;
segTree[i].Max = max(segTree[i<<1].Max,segTree[(i<<1)|1].Max);
}
void push_down(int i){
if(segTree[i].l == segTree[i].r)return;
if(segTree[i].lazy != 1){
segTree[i<<1].sum = segTree[i<<1].sumsegTree[i].lazy;
segTree[i<<1].Max = segTree[i<<1].MaxsegTree[i].lazy;
segTree[(i<<1)|1].sum = segTree[(i<<1)|1].sumsegTree[i].lazy;
segTree[(i<<1)|1].Max = segTree[(i<<1)|1].MaxsegTree[i].lazy;
segTree[i<<1].lazy = segTree[i].lazy;
segTree[(i<<1)|1].lazy = segTree[i].lazy;
segTree[i].lazy = 1;
}
}
void build(int i,int l,int r){
segTree[i].l = l;
segTree[i].r = r;
segTree[i].lazy = 1;
if(l == r){
segTree[i].sum = segTree[i].Max = 1;
return;
}
int mid = (l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
push_up(i);
}
void DOU(int i,int l,int r){
if(l > r)return;
if(segTree[i].l == l && segTree[i].r == r){
segTree[i].sum = 2;
segTree[i].Max = 2;
segTree[i].lazy *= 2;
return;
}
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/2;
if(r <= mid)DOU(i<<1,l,r);
else if(l > mid)DOU((i<<1)|1,l,r);
else {
DOU(i<<1,l,mid);
DOU((i<<1)|1,mid+1,r);
}
push_up(i);
}
long long query_Max(int i,int l,int r){
if(l > r)return 0;
if(segTree[i].l == l && segTree[i].r == r)
return segTree[i].Max;
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/2;
if(r <= mid)return query_Max(i<<1,l,r);
else if(l > mid)return query_Max((i<<1)|1,l,r);
else return max(query_Max(i<<1,l,mid),query_Max((i<<1)|1,mid+1,r));
}
long long query_Sum(int i,int l,int r){
if(l > r)return 0;
if(segTree[i].l == l && segTree[i].r == r)
return segTree[i].sum;
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/2;
if(r <= mid)return query_Sum(i<<1,l,r);
else if(l > mid)return query_Sum((i<<1)|1,l,r);
else return query_Sum(i<<1,l,mid)+query_Sum((i<<1)|1,mid+1,r);
}
int get_id(long long k){
int i = 1;
while(segTree[i].l != segTree[i].r){
push_down(i);
if(segTree[i<<1].sum >= k)i = i<<1;
else {
k -= segTree[i<<1].sum;
i = (i<<1)|1;
}
}
return segTree[i].l;
}
void ADD(int i,int id,long long val){
if(segTree[i].l == id && segTree[i].r == id){
segTree[i].sum += val;
segTree[i].Max += val;
return;
}
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/2;
if(id <= mid)ADD(i<<1,id,val);
else ADD((i<<1)|1,id,val);
push_up(i);
}
int n;
void gao1(long long l,long long r){
int id1 = get_id(l);
int id2 = get_id(r);
if(id1 == id2){
ADD(1,id1,r-l+1);
return;
}
ADD(1,id2,r-query_Sum(1,1,id2-1));
DOU(1,id1+1,id2-1);
ADD(1,id1,query_Sum(1,1,id1)-l+1);
}
long long gao2(long long l,long long r){
int id1 = get_id(l);
int id2 = get_id(r);
if(id1 == id2){
return r-l+1;
}
long long ans = query_Max(1,id1+1,id2-1);
ans = max(ans,query_Sum(1,1,id1)-l+1);
ans = max(ans,r-query_Sum(1,1,id2-1));
return ans;
}

int main()
{
//freopen(“1003.in”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int iCase = 0;
int m;
scanf(“%d”,&T);
while(T–){
iCase++;
printf(“Case #%d:\n”,iCase);
scanf(“%d%d”,&n,&m);
build(1,1,n);
char op[10];
long long l,r;
while(m–){
scanf(“%s%I64d%I64d”,op,&l,&r);
if(op[0] == ‘D’)gao1(l,r);
else printf(“%d\n”,(int)gao2(l,r));
}
}
return 0;
}