首页 > 代码库 > HDU-4973-A simple simulation problem.(二分+树状数组)
HDU-4973-A simple simulation problem.(二分+树状数组)
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)
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.
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
思路:找位置的时候直接二分查找。两个数组分别保存区间和、单点计数。
#include <stdio.h> #define max(A,B)(A>B?A:B) long long node[50005],cnt[50005]; int n,m; long long sum(int x) { long long res=0; while(x>=1) { res+=node[x]; x-=x&-x; } return res; } void add(int x,long long val) { while(x<=n) { node[x]+=val; x+=x&-x; } } int getpos(long long val) { int l=1,r=n,mid,res; while(l<=r) { mid=(l+r)>>1; if(sum(mid)>=val) { res=mid; r=mid-1; } else l=mid+1; } return res; } int main() { int T,i,l,r,cases=1; long long a,b,tempa,tempb,ans; char s[5]; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); printf("Case #%d:\n",cases++); for(i=1;i<=n;i++) node[i]=0,cnt[i]=1; for(i=1;i<=n;i++) add(i,1); while(m--) { scanf("%s%I64d%I64d",s,&a,&b); if(s[0]=='D') { l=getpos(a); r=getpos(b); if(l==r) { cnt[l]+=b-a+1; add(l,b-a+1); } else { tempa=sum(l)-a+1; tempb=b-sum(r-1); cnt[l]+=tempa; add(l,tempa); cnt[r]+=tempb; add(r,tempb); for(i=l+1;i<=r-1;i++) { add(i,cnt[i]); cnt[i]+=cnt[i]; } } } else { l=getpos(a); r=getpos(b); if(l==r) printf("%I64d\n",b-a+1); else { ans=max(sum(l)-a+1,b-sum(r-1)); for(i=l+1;i<=r-1;i++) ans=max(ans,cnt[i]); printf("%I64d\n",ans); } } } } }
HDU-4973-A simple simulation problem.(二分+树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。