hdu (1166): 적군 포진 - 나무 모양 배열 의 응용

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1166
제목 은 트 리 배열 의 정의 가 거의 같다 는 뜻 이다.

값 은 이 문제 의 입력 량 이 비교적 많 고 처음으로 cin 을 입력 으로 사 용 했 습 니 다. TLE 는 scanf 로 바 꾸 면 시간 이 700 ms + 에 달 합 니 다.
트 리 배열 을 연습 하 는 문제 로 트 리 배열 에 익숙 하 다.물론 이 문 제 는 선분 트 리 로 도 풀 수 있 지만 코드 가 좀 길 어서 좋 지 않 습 니 다.

코드:

//freopen("C:\\Documents and Settings\\All Users\\×ÀÃæ\\in.txt","r",stdin);

#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

int C[50010];
int n;

int lowbit(int x){return x&-x;}

int sum(int x){
    int ret=0;
    while(x>0){ret+=C[x];x-=lowbit(x);}
    return ret;
}

void add(int x,int d){
    while(x<=n){C[x]+=d;x+=lowbit(x);}
}

int main(){
    //freopen("C:\\Documents and Settings\\All Users\\×ÀÃæ\\in.txt","r",stdin);
    int T;cin>>T;
    for(int cas=1;cas<=T;cas++)
    {
        printf("Case %d:
",cas);
        memset(C,0,sizeof(C));
        cin>>n;
        for(int i=1;i<=n;i++){
            int t;scanf("%d",&t);
            add(i,t);
        }
        char s[10];
        while(scanf("%s",s)){
            if(s[0]=='E') break;
            int l,r;
            cin>>l>>r;
            if(s[0]=='Q'){
                l=sum(l-1);r=sum(r);
                cout<

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 1556 - Color the ball (트 리 배열 - 구간 수정 단점 조회)

Color the ball Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu (1166): 적군 포진 - 나무 모양 배열 의 응용

좋은 웹페이지 즐겨찾기