hckim

문제링크

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

풀이

다항함수에서 f(c) 의 부호를 결정하는 요소는

• 최고차항의 계수 부호
• 최고차항의 지수
• c 보다 작은 근의 개수

가 있다. 위 세개를 고려해서 부호를 결정하면 되겠다 

c 보다 작은 근의 개수를 구하기 위해서 segment tree 를 사용할 수 있겠다

근의 범위가 크므로(+ 정수 값이 아니므로) 대소비교만 알 수 있도록 좌표압축을 해준다.

( PBDS 의 ordered set 을 쓰면 더 간결하게 코드 작성 가능)

1 a b 에서 a = 0 인 경우를 주의

코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ll long long
#define ld long double
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;
typedef vector<vector<int>> vvi;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tlll;
typedef vector<ll> vl;
typedef vector<pair<ll, ll>> vpl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #if !defined(ONLINE_JUDGE)
  freopen("../input.txt", "r", stdin);
  freopen("../output.txt", "w", stdout);
  #endif // ONLINE_JUDGE
 
  int q;
  cin >> q;
  vector<tuple<ll, ll, ll> > query(q);
  vector<tuple<ll, ll, ll> > queryOrg(q);
  vector<pair<ld, int> > v(q);
  for (int i = 0; i < q; ++i) {
    auto& [a, b, c] = query[i];
    cin >> a;
    if (a == 1) {
      cin >> b >> c;
      if (b == 0) {
        v[i] = {1.0L * 1e30, -1};
      } else {
        v[i] = {-1.0L * c / b,i};
      }
    } else {
      cin >> b;
      v[i] = {b, i};
    }
    queryOrg[i] = query[i];
  }
  sort(all(v));
 
  ld prev;
  int idx = 1;
  for (int i = 0; i < q; ++i) {
    if (v[i].second == -1) continue;
    auto& [a, b, c] = query[v[i].second];
 
    if (a == 1) {
      if (b > 0) b = 1;
      else if (b == 0) b = 0;
      else b = -1;
 
      if (i && abs(prev - v[i].first) > 1e-25) {
        c = ++idx;
      } else {
        c = idx;
      }
    } else {
      if (i && abs(prev - v[i].first) > 1e-25) {
        b = ++idx;
      } else {
        b = idx;
      }
    }
    prev = v[i].first;
  }
 
  vi t(2 * q);
  auto update = [&](int p, int v) {
    for (t[p += q] = v; p > 1; p >>= 1) t[p >> 1] = t[p] + t[p ^ 1];
  };
  auto sum = [&](int l, int r) {
    int ret = 0;
    for (l += q, r += q; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ret += t[l++];
      if (r & 1) ret += t[--r];
    }
    return ret;
  };
 
  int x = 0;
  int sign = 0;
  int allzero = false;
  for (int i = 0; i < q; ++i) {
    auto [a, b, c] = query[i];
    if (a == 1) {
 
      if (b == 0) {
        if (get<2>(queryOrg[i]) == 0) allzero = true;
        else {
          if (get<2>(queryOrg[i]) < 0) sign ^= 1;
        }
      } else {
        if (get<1>(queryOrg[i]) < 0) sign ^= 1;
        ++x;
        update(c, t[q + c] + 1);
      }
    } else {
 
      if (t[q + b] || allzero) cout << 0 << '\n';
      else cout << (((sign + x + sum(1, b + 1)) % 2 == 1) ? '-' : '+' )<< '\n';
    }
  }
}

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

풀이

• 기본적인 세그먼트 트리에서 노드의 값을 해당 노드 구간의 배열을 정렬된 상태로 가지는 머지 소트 트리를 이용

코드

• 시간복잡도: $O(NlogN + Mlog^2N)$

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N;
    cin >> N;
 
    vector<vector<long long> > t(2 * N);
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        t[N + i].push_back(num);
    }
 
    for (int i = N - 1; i >= 1; --i) {
        t[i].resize(t[i << 1 | 1].size() + t[i << 1].size());
        merge(all(t[i << 1 | 1]), all(t[i << 1]), t[i].begin());
    }
 
    auto query = [&](int l, int r, int k) {
        int ret = 0;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret += t[l].end() - upper_bound(all(t[l]), k), ++l;
            if (r & 1) --r, ret += t[r].end() - upper_bound(all(t[r]), k);
        }
        return ret;
    };
 
    int M;
    cin >> M;
    while (M--) {
        int i, j, k;
        cin >> i >> j >> k;
        cout << query(i - 1, j, k) << '\n';
    }
}