[백준] 25317. functionx

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

문제요약

• n차 함수에서 어떤 x값에서 양/음/0인지 판단
• 두 가지 쿼리를 처리 : 함수의 변화, x값 판단

접근법

• f()가 x축과 만나는 점은 알 수 있는데, 분수임. 10^18 값 범위를 갖는 분수
• x축에 만나는 점들이 쭉 늘어서있고, 판단하는 값이 어느 위치인지 알고, 양인지 음인지를 판단하고... 위치 판단하기도 어렵고 여러모로 쉽지 않음
• f() 함수가 올록볼록 형태일것이고 x축과 만나는 점을 지나면서 양/음/양/음을 반복할 것임
• 좌표압축 -> 구간트리 + x축과 만나는 점 map을 이용한 방문 처리 -> 함수 처리 -> 쿼리 처리
• 좌표 압축
  • 나오는 모든 수를 크기로 정수 변환
  • 곱을 이용한 분수 비교가 어려워서 큰 수 곱하기 구현
  • 0으로 나누기는 별도 처리 => 함수가 0으로 변함
  • 중복점도 별도로 번호 부여 : 쿼리처리에서 설명
• 구간트리
  • 새로 부여한 번호로 합 구간트리 구현. +1씩 처리
  • x축과 만나는 점은 map을 이용해 방문 처리
• 함수 처리
  • 차수가 얼마인지
  • 최고차항의 계수가 양인지 음인지
  • 함수가 변경될때마다
    • 변경하는 값이 0인지 : 0처리
    • 상수인지
      • 기존 함수가 상수이면 상수 부호가 바뀌는지
      • 기존 함수가 다항식이면 최고차항 부호가 바뀌는지
    • 1차식인지
      • x축과 만나는 점 방문 처리
      • 구간트리 업데이트
      • 최고차항 부호가 바뀌는지
• 쿼리 처리
  • 함수가 0인지
  • 함수의 차수가 0인지 = 상수 함수
    • 양, 음
  • 구하고자 하는 점이 map에 있으면 -> x축 만나는 점 -> 0
  • 합을 계산함
    • 합이 짝수면 : 처음 시작(무한대의 음수쪽 끝점)과 부호가 같음
    • 합이 홀수면 : 처음 시작과 부호가 다름
    • 중복점에 별도로 번호를 부여해도 효과는 같음 : ${x^2, x^3}$을 생각해보면됨

후기

• 다항함수의 올록볼록을 구간트리로 처리하면 되는 아이디어는 단순하지만 조건체크를 꼼꼼히 해야하는 문제이고, 구현량도 많음
• 큰자리수 곱셈
• 상수함수 처리
• 최고차항의 부호가 바뀌는 조건 체크