A simple simulation problem.
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 330 Accepted Submission(s): 132
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?
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
题意：D：在区间内的所有点个数都变成2倍，总区间变长，Q：询问区间内的同一个数最多出现的次数。
#include<stdio.h>
#define N 50005
#define ll __int64
struct nn
{
ll sum,maxlen,mulit;//分别代表当前节点区间总个数，同一个数最多个数，子节点需更新的倍数
}tree[N*3];
void builde(ll l,ll r,int k)
{
tree[k].sum=r-l+1;
tree[k].maxlen=1; tree[k].mulit=1;
if(l==r)return ;
ll m=(l+r)/2;
builde(l,m,k*2); builde(m+1,r,k*2+1);
}
ll MAX(ll a,ll b){return a>b?a:b;}
void setchilde(int k)
{
tree[k*2].mulit*=tree[k].mulit;
tree[k*2].sum*=tree[k].mulit;
tree[k*2].maxlen*=tree[k].mulit;
tree[k*2+1].mulit*=tree[k].mulit;
tree[k*2+1].sum*=tree[k].mulit;
tree[k*2+1].maxlen*=tree[k].mulit;
tree[k].mulit=1;
}
void set(ll l,ll r,int k,ll L,ll R,ll suml)
{
ll m=(l+r)/2;
if(L<=suml+1&&suml+tree[k].sum<=R)
{
tree[k].maxlen*=2; tree[k].mulit*=2; tree[k].sum*=2;
return ;
}
else if(l==r)
{
if(tree[k].sum+suml>=R&&suml+1>=L)
tree[k].sum=tree[k].sum+suml-R+(R-suml)*2;
else if(tree[k].sum+suml>=R&&suml+1<=L)
tree[k].sum=tree[k].sum+suml-R+L-suml-1+(R-L+1)*2;
else if(tree[k].sum+suml<=R&&suml+1<=L)
tree[k].sum=(tree[k].sum+suml-L+1)*2+L-suml-1;
tree[k].maxlen=tree[k].sum;
return ;
}
if(tree[k].mulit>1)
setchilde(k);
ll sum=tree[k*2].sum;
if(suml+sum>=L)set(l,m,k*2,L,R,suml);
if(suml+sum+1<=R)set(m+1,r,k*2+1,L,R,suml+sum);
tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
tree[k].maxlen=MAX(tree[k*2].maxlen,tree[k*2+1].maxlen);
}
ll query(ll l,ll r,int k,ll L,ll R,ll suml)
{
ll m=(l+r)/2, maxlen;
if(suml+1>=L&&tree[k].sum+suml<=R)
{
return tree[k].maxlen;
}
else if(l==r)
{
if(tree[k].sum+suml>=R&&suml+1>=L)
maxlen=R-suml;
else if(tree[k].sum+suml>=R&&suml+1<=L)
maxlen=R-L+1;
else if(tree[k].sum+suml<=R&&suml+1<=L)
maxlen=tree[k].sum+suml-L+1;
return maxlen;
}
if(tree[k].mulit>1)
setchilde(k);
if(tree[k*2].sum+suml>=R)
maxlen=query(l,m,k*2,L,R,suml);
else if(tree[k*2].sum+1+suml<=L)maxlen=query(m+1,r,k*2+1,L,R,tree[k*2].sum+suml);
else maxlen= MAX(query(l,m,k*2,L,R,suml),query(m+1,r,k*2+1,L,R,tree[k*2].sum+suml));
return maxlen;
}
int main()
{
ll n,m,L,R,t,tt=0;
char s[5];
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d%I64d",&n,&m);
builde(1,n,1);
printf("Case #%I64d:\n",++tt);
while(m--)
{
scanf("%s%I64d%I64d",s,&L,&R);
if(s[0]=='D')set(1,n,1,L,R,0);
else printf("%I64d\n",query(1,n,1,L,R,0));
}
}
}