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

1576 단어 트 리 배열
제목 링크: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<

 
 
Nginx 설정 은 전단 루트 와 백 엔 드 루트 의 분 리 를 실현 합 니 다
자바 데이터 분리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage