poj 2352 Stars

클릭 하여 링크 열기 poj 2352
사고: 나무 모양 배열 분석: 1 문 제 는 각 점 의 왼쪽 아래 (왼쪽 + 바로 아래) 에 몇 개의 별 이 있 는 지 요구 하 는 것 이다. 그 점 이 바로 몇 층 이 고 마지막 으로 0 ~ n - 1 층 의 점 을 출력 하 는 것 이다.예 를 들 어 견본 번호 가 5 인 별 은 왼쪽 아래 에 3 개의 별 이 있 으 면 5 는 3 층 2 에 있 고 나무 모양 의 배열 을 이용 합 니 다. 우 리 는 나무 모양 의 배열 C 에서 C [i] 는 원래 의 배열 A 중의 한 부분 과 합 을 나타 내 는 것 을 알 고 있 습 니 다.문 제 는 입력 할 때 Y 값 이 커지 는 순서 (y 는 똑 같이 x 가 커진다) 라 고 명확 하 게 지적 했다. 그러면 우 리 는 무엇 을 원래 의 배열 A 로 해 야 하 는 지, 바로 X 축 이 고 A [2] 는 x = 2 를 나타 내 는 점 의 개수 이다.그러면 한 점 의 x 값 이 2 일 때 A [2] +, 이때 C [2], C [2 + lowbit (2) 를 업데이트 해 야 합 니 다.
3. 어떤 점 의 왼쪽 아래 에 몇 개의 별 이 있 는 지 어떻게 구 할 수 있 습 니까? 분명히 왼쪽 아래 에 있 는 점 의 x 수 치 는 현재 점 보다 작 을 것 입 니 다. 그러면 나무 모양 의 배열 과 비슷 합 니 다. 그러면 전체 문제 의 방향 은 4. 나무 모양 의 배열 을 업데이트 할 때 x < = MAXN 에 주의 하 세 요. 입력 한 n 이 아 닙 니 다.A [x] 가 변경 되 었 기 때문에 C [x], C [x + lowbit (x)] 를 업데이트 해 야 합 니 다.
5 문제 가 입력 한 x 의 좌 표 는 0 일 수 있 기 때문에 여기 서 우 리 는 모든 x + 1 을 피 할 수 있 습 니 다. 그러면 TLE 를 피 할 수 있 습 니 다.
코드:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 32010;

int n , ans[MAXN];
int treeNum[MAXN];

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

int getSum(int x){
    int sum = 0;
    while(x){
        sum += treeNum[x]; 
        x -= lowbit(x);
    }
    return sum;
}

void add(int x , int val){
    while(x < MAXN){
        treeNum[x] += val; 
        x += lowbit(x);
    }
}

int main(){
    int x , y;
    while(scanf("%d" , &n) != EOF){ 
        memset(treeNum , 0 , sizeof(treeNum));
        memset(ans , 0 , sizeof(ans));
        for(int i = 0 ; i < n ; i++){
            scanf("%d%d" , &x , &y); 
            x++;
            ans[getSum(x)]++; 
            add(x , 1);
        }
        for(int i = 0 ; i < n ; i++)
            printf("%d
" , ans[i]);
    }
    return 0;
}

사고방식: 라인 트 리 + 단점 업데이트 분석: 1 문제 가 입력 한 점 은 y 의 오름차 순 이 고 같은 y 는 x 의 오름차 순 이다.그러면 우 리 는 뒤에 입력 한 점 이 앞 점 의 왼쪽 아래 에 있 지 않다 는 것 을 알 수 있다. 그러면 우 리 는 고려 하기 만 하면 된다.이렇게 하면 1 차원 의 문제 가 되 어 선분 수 를 이용 하여 할 수 있다.2. 우 리 는 한 점 이 다른 점 의 왼쪽 아래 에 있다 는 것 을 알 고 있다. 그러면 이 점 의 x 수 치 는 틀림없이 다른 점 보다 작 을 것 이다.그러면 새로 가입 한 점 은 갱신 구간 [x, x] 과 같 습 니 다. 그리고 왼쪽 아래 에 몇 가지 점 을 요구 하 는 것 은 구간 [0, x] 의 합 입 니 다.3. 생각 을 알 게 되면 선분 수 를 이용 하여 구 할 수 있다.이 문 제 는 입력 데이터 가 질서 가 있 기 때문에 뒤의 것 은 앞의 것 에 영향 을 주지 않 습 니 다. 그러면 우 리 는 입력 한 후에 업데이트 하기 전에 이전의 level 을 구 할 수 있 습 니 다.이런 식 으로 모든 것 을 추구 하 다.4. x 값 이 0 일 수 있 으 므 로 루트 노드 구간 은 [0, MAXN] 입 니 다. 코드:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAXN 32010

struct Node{
  int left;
  int right;
  int sum;
};
Node node[4*MAXN];
int vis[MAXN];

/*       */
void buildTree(int left , int right , int pos){
   node[pos].left = left;
   node[pos].right = right;
   node[pos].sum = 0;
   if(left == right)
     return;
   int mid = (left+right)>>1;
   buildTree(left , mid , pos<<1);
   buildTree(mid+1 , right , (pos<<1)+1);
}

/*    */
void update(int index , int pos){
   if(node[pos].left == node[pos].right){
      node[pos].sum++;
      return;
   }
   int mid = (node[pos].left+node[pos].right)>>1;
   if(index <= mid)
     update(index , pos<<1);
   else
     update(index , (pos<<1)+1);
   node[pos].sum = node[pos<<1].sum + node[(pos<<1)+1].sum;
}

/*    */
int query(int left , int right , int pos){
   if(node[pos].left == left && node[pos].right == right)
     return node[pos].sum;
   int mid = (node[pos].left+node[pos].right)>>1;
   if(right <= mid)
     return query(left , right , pos<<1);
   else if(left > mid)
     return query(left , right , (pos<<1)+1);
   else
     return query(left , mid , pos<<1)+query(mid+1 , right , (pos<<1)+1);
}

int main(){
   int Case , n;
   int x , y;
   scanf("%d" , &Case);
   n = Case;
   buildTree(0 , MAXN , 1);
   memset(vis , 0 , sizeof(vis));
   while(Case--){
      scanf("%d%d" , &x , &y);
      vis[query(0 , x , 1)]++;
      update(x , 1);
   }
   for(int i = 0 ; i < n ; i++)
      printf("%d
" , vis[i]);
   return 0;
}