test/aoj2674_1.test.cpp

Back to top page

• category: test
• View this file on GitHub
  • Last commit date: 2020-03-01 12:39:31+09:00
• see: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2674

Depends on

• data_structure/segtree_range_freq.cpp
• memo/macro.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2674"
#include "../memo/macro.hpp"
#include "../data_structure/segtree_range_freq.cpp"

int main() {
    ll n;
    cin >> n;
    vector<vector<ll>> x(n);
    REP(i, n) x[i].resize(1), cin >> x[i][0];
    segTreeRangeFreq seg(x);

    ll q;
    cin >> q;
    vector<ll> ans(q);
    REP(i, q) {
        ll l, r, e;
        cin >> l >> r >> e;
        l--, r--;
        ll a = min(x[l][0], x[r][0]), b = max(x[l][0], x[r][0]);
        cout << r-l+1 - (seg.query(l, r+1, b+e) - seg.query(l, r+1, a-e-1)) << "\n";
    }
    cout << flush;
}

#line 1 "test/aoj2674_1.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2674"
#line 1 "memo/macro.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
const ll INF = 1LL<<60;
#line 1 "data_structure/segtree_range_freq.cpp"
// BEGIN CUT
struct segTreeRangeFreq {
    int n;
    vector<vector<ll>> dat;
    // 初期化 O(NlogN)
    segTreeRangeFreq() {}
    segTreeRangeFreq(vector<vector<ll>> v) {
        n = 1; while(n < (ll)v.size()) n *= 2;
        dat.resize(2*n-1);
        REP(i, v.size()) dat[i+n-1] = v[i];
        for(int i=n-2; i>=0; --i) {
            dat[i].resize(dat[i*2+1].size() + dat[i*2+2].size());
            merge(ALL(dat[i*2+1]), ALL(dat[i*2+2]), dat[i].begin());
        }
    }
    // [a, b) のx以下の個数を返す O(log^2N)
    int query(int a, int b, ll x, int k, int l, int r) {
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return upper_bound(ALL(dat[k]), x) - dat[k].begin();
        int vl = query(a, b, x, k*2+1, l, (l+r)/2);
        int vr = query(a, b, x, k*2+2, (l+r)/2, r);
        return vl + vr;
    }
    int query(int a, int b, ll x) { return query(a, b, x, 0, 0, n); }
};

// 2次元平面上の点集合 矩形中に何個点があるかのクエリに答えることが可能
// (x[i], y[i]) をxでソートしてyをセグ木に乗せるとrangefreqになる
// wavelet matrixじゃなくてセグ木でO(log^2N)でok
// END CUT
#line 4 "test/aoj2674_1.test.cpp"

int main() {
    ll n;
    cin >> n;
    vector<vector<ll>> x(n);
    REP(i, n) x[i].resize(1), cin >> x[i][0];
    segTreeRangeFreq seg(x);

    ll q;
    cin >> q;
    vector<ll> ans(q);
    REP(i, q) {
        ll l, r, e;
        cin >> l >> r >> e;
        l--, r--;
        ll a = min(x[l][0], x[r][0]), b = max(x[l][0], x[r][0]);
        cout << r-l+1 - (seg.query(l, r+1, b+e) - seg.query(l, r+1, a-e-1)) << "\n";
    }
    cout << flush;
}

Back to top page