hdu 1556 Color the ball(선분 트 리 구간 업데이트)
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 12814 Accepted Submission(s): 6401
Problem Description
N 개의 풍선 이 한 줄 로 늘 어서 고 왼쪽 에서 오른쪽으로 순서대로 번호 가 1,2,3 이다.그런데 N 번 이후로 릴 은 I 번 째 풍선 이 몇 번 이나 발 랐 는 지 잊 어 버 렸 어 요.풍선 마다 몇 번 발 랐 는 지 계산 해 주 시 겠 어 요?
Input
각 테스트 실례 의 첫 번 째 행 위 는 정수 N,(N<=100000)입 니 다.다음 N 줄 은 정수 a b(1<=a<=b<=n)2 개 를 포함 합 니 다.
N=0 이면 입력 이 끝 납 니 다.
Output
모든 테스트 인 스 턴 스 는 N 개의 정 수 를 포함 하여 한 줄 을 출력 합 니 다.I 번 째 수 는 I 번 째 풍선 이 모두 색칠 되 는 횟수 를 대표 합 니 다.
Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
Author
8600
Source
HDU 2006-12 Programming Contest
Recommend
LL | We have carefully selected several similar problems for you: 1166 1542 1394 1698 1255
Statistic | Submit | Discuss | Note
라인 트 리 구간 업데이트 문제그냥 쓰 면 돼.
매번 업데이트 할 때마다 시간 을 절약 하기 위해 업데이트 가 필요 한 구간+1 만 있 으 면 됩 니 다.
#include <stdio.h>
#include <string.h>
struct node
{
int left,right,count;
}c[100005*3];
int sum[100005];
void build(int l,int r,int root)//
{
c[root].left=l;
c[root].right=r;
c[root].count=0;
if(l==r)
return ;
int mid=(l+r)/2;
build(l,mid,root*2);
build(mid+1,r,root*2+1);
}
void update(int l,int r,int root)//
{
if(c[root].left==l&&c[root].right==r)// +1 ， ，
{
c[root].count++;
return ;
}
int mid=(c[root].left+c[root].right)/2;
if(mid<l)
update(l,r,root*2+1);
else if(mid>=r)
update(l,r,root*2);
else
{
update(l,mid,root*2);
update(mid+1,r,root*2+1);
}
}
void tosum(int root)//
{
for(int i=c[root].left;i<=c[root].right;i++)
sum[i]+=c[root].count;
if(c[root].left==c[root].right)
return ;
tosum(root*2);
tosum(root*2+1);
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
memset(sum,0,sizeof(sum));
memset(&c,0,sizeof(&c));
build(1,n,1);
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d %d",&l,&r);
update(l,r,1);
}
tosum(1);
printf("%d",sum[1]);
for(int i=2;i<=n;i++)
printf(" %d",sum[i]);
printf("
");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
