BOJ 25317 - functionx

BOJ 25317 - functionx

따져볼게 많은 문제이다.

0이 되는 조건

우선, $c=\dfrac {-b}a$ 라면, $0$이 쿼리의 정답이다.

따라서 $\dfrac {-b}a, ~~ (a ~\vert~ b)$ 쌍을 모아두고, 만약 $c$ 가 그 안에 있다면 정답은 0이다.

혹은, $a=0,\,b=0$ 인 조건이 하나라도 들어온 이후에는 항상 정답은 $0$ 이다. (항등식)

$ax+b < 0$ 이 되는 조건

부호의 결정에 있어서 중요한건 인수분해된 식에서 음수가 나오는 개수이므로,

$ax+b$ 를 추가하는 쿼리에 대해서 $ax+b<0$ 이 나오려면

$$ \begin{aligned} ax+b<0\\ \cdots\\ x< \dfrac {-b}a \end{aligned} $$

따라서 $c$의 값과 $\dfrac {-b}a$ 의 값이 관련이 있다.

단, 여기서 $a$ 는 항상 양수여야 저러한 조건이 나오므로 $a$ 를 양수가 되도록 적절히 부호 관리를 해주어야 한다.

구현

극심한 케이스 워크 문제이므로 따져볼건 더 많은데,, 대략적으로 세그먼트 트리에 $\dfrac {-b}a$ 를 저장해야 하고, $c$ 에 대해서 그 값보다 큰 값의 개수를 찾아와야 한다.

여기서 $\dfrac {-b}a$ 가 실수지만 $c$는 항상 실수이고 $c$보다 큰 것을 찾기만 하면 된다는 점에서 $\dfrac {-b}a$ 를 올림연산으로 정수로 처리하여 좌표압축 후 세그먼트 트리로 사용할 수 있다.

나머지 구현에 대한 설명은 생략한다.

template<class T>  
struct fenwick {  
   int n;  
   vector<T> tree;  
   fenwick(int n) : n(n) { tree.resize(n + 1); }  
   T sum(int i) {  
      T ret = 0;  
      for (; i; i -= i & -i) ret += tree[i];  
      return ret;  
   }  
   void update(int i, T x) { for (i++; i <= n; i += i & -i) tree[i] += x; }  
   T query(int l, int r) { return l > r ? 0 : sum(r + 1) - sum(l); }  
};  
// endregion  
  
int get_ceil(int x, int y) {  
   if (x < 0 != y < 0) return x / y;  
   return x / y + (x % y ? 1 : 0);  
}  
  
void solve() {  
   int q;  
   cin >> q;  
   vector<array<int, 4>> query;  
   vi values;  
  
   while (q--) {  
      int cmd;  
      cin >> cmd;  
      if (cmd == 1) {  
         int a, b;  
         cin >> a >> b;  
         if (a != 0) {  
            int v = get_ceil(-b, a);  
            values.pb(v);  
            query.pb({1, v, a, b});  
         } else {  
            query.pb({1, 0, a, b});  
         }  
      } else {  
         int c;  
         cin >> c;  
         values.pb(c);  
         query.pb({2, c, c, c});  
      }  
   }  
   uniq(values);  
   int V = sz(values);  
   fenwick<int> fenw(V);  
  
   // 항상 0이 되었으면  
   int always_zero = 0;  
   int b_negative = 0;  
   int b_zero = 0;  
   int global_negative = 0;  
   unordered_set<int> zero;  
  
   auto print = [&](char c) {  
      if (global_negative % 2) {  
         cout << (c == '+' ? '-' : '+');  
      } else {  
         cout << c;  
      }  
      cout << '\n';  
   };  
   for (auto[cmd, x, a, b]: query) {  
  
      if (cmd == 1) {  
         if (a != 0 && b % a == 0) zero.insert(-b / a);  
         if (a < 0 || a == 0 && b < 0) {  
            a *= -1;  
            b *= -1;  
            global_negative++;  
         }  
  
         if (a == 0 && b == 0) always_zero = 1;  
         if (b == 0) b_zero = 1;  
         if (b < 0) b_negative++;  
  
         if (a == 0) {  
            // 상수  
            if (b < 0) abort();  
  
         } else {  
            fenw.update(lbi(values, x), 1);  
         }  
      } else {  
         // a = 0 b = 0 인 경우가 나오면 항상 0이므로 그냥 0이다.  
         if (always_zero || hass(zero, x)) {  
            cout << 0 << endl;  
         } else if (x == 0) {  
            // 만약 c가 0이라면, b 중 0이 하나라도 있으면 0이다.  
            if (b_zero) {  
               cout << 0 << endl;  
            } else {  
               // 음수 b 개수가 홀수개면 음수다.  
               if (b_negative % 2) print('-');  
               else print('+');  
            }  
         } else {  
            int cnt = fenw.query(lbi(values, x) + 1, V - 1);  
            if (cnt % 2) {  
               print('-');  
            } else {  
               print('+');  
            }  
         }  
      }  
   }  
}