[2934번] LRH 식물

문제 출처 :

https://www.acmicpc.net/problem/2934

알고리즘 분석 :

문제 해결에 필요한 사항

1. 펜윅 트리 :: http://www.crocus.co.kr/666

쿼리에 대한 빠른 답을 구해야 하는 문제이다.

이 문제는 각 좌표마다 수평선이 몇개 존재하는지를 펜윅 트리로 접근 할 수 있다.

a, b의 입력을 한다면 a + 1 ~ b - 1까지 수평선이 생긴다.

예를 들어 1,4를 넣으면 2~3에 수평선이 생기고, 1과 4에 수평선이 몇개있는지 검사를 해주면 된다.

그리고 수평선에 대해 답을 구해주고 그 수평선을 펜윅트리에서 지워주면 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

#include <iostream> #include <cstdio> #include <vector>   #define MAX_LEN 100001   using namespace std;   int tree[MAX_LEN];   int sum(int i) {     int ans = 0;     while (i > 0)     {         ans += tree[i];         i -= (i&-i);     }       return ans; }   void update(int i, int diff) {     while (i < MAX_LEN)     {         tree[i] += diff;         i += (i&-i);     } }   int main() {     int n, a, b;     int getA, getB;       scanf("%d", &n);       for (int i = 0; i < n; i++)     {         scanf("%d %d", &a, &b);           getA = sum(a);         getB = sum(b);           // a부분은 모든 꽃이 피었으니 0이 되고,          // a + 1부분부터는 다시 복구해준다.         update(a, -getA); update(a + 1, getA);         update(b, -getB); update(b + 1, getB);           // 새로 들어온 식물로 인해 a + 1부분부터 꽃이 필 수 있는 곳이 생긴다.         // b부터는 꽃이 필 수 없으니 다시 -1로 빼준다.         // 1 4일경우 1,2,3,4중 2,3에만 꽃이 필 수 있다.         update(a + 1, 1);         update(b, -1);           printf("%d\n", getA + getB);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus