코뚫린 앙드로이드

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

문제 풀이만 읽으면 그냥 세그먼트트리 구성하고

(쿼리, update)함수를 쓸줄아냐 모르냐 정도를 묻는 문제인데

정답률이 많이 낮았는데 역시 그럴만한 이유가 있었다.

x > y 인경우는 함수에 들어가자마 리턴이 되기 때문에 함수가 돌지 못한다.

#include <iostream>
using namespace std;
#define SWAP(a,b) {int t; t=a; a=b; b=t;}
#define MAX_N 100001

typedef long long ll;
ll tree[MAX_N * 4];

ll update_tree(int now, int target, int start, int end, int value) {
     if (target > end || target < start) return tree[now];
     if (start == end) {
          return tree[now] = value;
     }
     int mid = (start + end) / 2;
     return tree[now] = update_tree(now * 2, target, start, mid, value) + update_tree(now * 2 + 1, target, mid + 1, end, value);
}

ll query(int now, int left, int right, int start, int end) {
     if (left > end || right < start) return 0;
     if (left <= start && end <= right) return tree[now];
     int mid = (start + end) / 2;
     return query(now * 2, left, right, start, mid) + query(now * 2 + 1, left, right, mid + 1, end);
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, Q;
     cin >> N >> Q;
     for (int i = 0; i < N; i++) {
          int data; cin >> data;
          update_tree(1, i, 0, N - 1, data);
     }
     for (int i = 0; i < Q; i++) {
          int x, y, a, b;
          cin >> x >> y >> a >> b;
          if (y < x) SWAP(x, y);
          cout << query(1, x - 1, y - 1, 0, N - 1) << "\n";
          update_tree(1, a - 1, 0, N - 1, b);
     }
}

세그먼트 트리를 사용해서 해결 했습니다.

트리의 리프노드의 갯수를 n + m 개로 셋팅한뒤에

현재 k번째 리프노드가 제일위의 책의 위치라면

다음 위로올라가는 책은 k + 1 번째의 리프노드에 업데이트 해주었습니다.

최대 tree의 배열크기를 (10만 + 10만) * 4 + 1 로 해주어야 20만개의 리프노드를 처리가능합니다.

tree의 0번째 노드 : 제일밑에있는 책의 인덱스

tree의 n-1번째 노드 : 제일 위에있는 책의 인덱스

query로 자신보다 오른쪽에 있는 값을 리턴하고

자기 자신이 있던 노드를 0으로 업데이트해준뒤

유효한 리프노드 + 1 번째( 올라가게되는 위치 ) 를 1로 업데이트 해줍니다.

#include <iostream>
using namespace std;

#define MAX_N 100001
#define MAX_M 100001
int tree[MAX_N * 8]; 
int ans[MAX_M], arr[MAX_N];

int update_tree(int now, int target, int start, int end, int value) {
     if (target > end || target < start) return tree[now];
     if (start == end) {
          tree[now] = value;
          return tree[now];
     }
     int mid = (start + end) / 2;
     tree[now] = update_tree(now * 2, target, start, mid, value) + update_tree(now*2+1,target,mid+1,end, value);
     return tree[now];
}

int query(int now, int left, int right, int start, int end) {
     if (left > end || right < start) return 0;
     if (left <= start && end <= right)  return tree[now];
     int mid = (start + end) / 2;
     return query(now * 2, left, right, start, mid) + query(now * 2 + 1, left, right, mid + 1, end);
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int T; cin >> T;
     while (T--) {
          int n, m;
          cin >> n >> m;
          int size = n + m - 1;
          for (int i = 0; i < n+m; i++) {
               if (i < n)
                    update_tree(1, i, 0, size, 1);
               else
                    update_tree(1, i, 0, size, 0);
               
          }
          for (int i = n; i >= 1; i--) {
               arr[i] = (n - i);
          }
       
          for (int i = 0; i < m; i++) {
               int data; cin >> data;
               int target = arr[data];
               ans[i] = query(1, target+1, size, 0, size);
               update_tree(1, target, 0, size, 0);
               update_tree(1, n, 0, size, 1);
               arr[data] = ++n;
          }
          for (int i = 0; i < m; i++) {
               cout << ans[i] << " ";
          }
          cout << "\n";
     }
}

세그먼트 트리를 사용해서 풀었습니다.

세그먼트 분류 에서 단지 암기한 코드를 쓰기 바빴는데

이문제가 어떻게 세그먼트 트리 알고리즘이 적용될지 고민을 한참 했습니다 ㅜㅜ.

리프노드의 K번째를 지정해서 update 할 수 있다는 세그먼트 트리의 특징을 사용했습니다 !

주의점으로 답이 int 범위에 담기지 않습니다.

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

#include <iostream>
using namespace std;

#define MAX_N 500000
int map[1000001];
int tree[MAX_N * 4];

int update_tree(int now, int target,int start, int end) {
     if (target > end || target < start) return tree[now];
     if (start == end) return ++tree[now];
     int mid = (start + end) / 2;
     return tree[now] = update_tree(now * 2, target, start, mid) + update_tree(now * 2 + 1, target, mid + 1, end);
}

int query(int now, int left, int right, int start, int end) {
     if (left > end || right < start) return 0;
     if (left <= start && end <= right) return tree[now];
     int mid = (start + end) / 2;
     return query(now * 2, left, right, start, mid) + query(now * 2 + 1, left, right, mid + 1, end);
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N; cin >> N;
     for (int i = 0; i < N; i++) {
          int data; cin >> data;
          map[data] = i;
     }
     long long ans = 0;
     for (int i = 0; i < N; ++i) {
          int data; cin >> data;
          int target = map[data];
          ans += query(1, target, N - 1, 0, N - 1);
          update_tree(1, target, 0, N - 1);
     }
     cout << ans << "\n";
}