01trie 트 리 템 플 릿 I - 구 또는 최 값

01 트 리 템 플 릿 I - 혹은 가장 가치 있 는 난동
Face
제목
  • 집합 중 v a l val 또는 최대 치
  • 를 구하 십시오.
    데이터 범위: 1 ≤ n, m ≤ 1 0 5, a [i] ≤ 2 3 2 1 \ \ \ leq n, m \ \ leq 10 ^ 5, a [i] \ \ leq 2 ^ 32 1 ≤ n, m ≤ 105, a [i] ≤ 232
    선행 기술
  • trie 수 ~ ~ (trie 나무 안 배 워 서 여기 왜 왔 어) ~
  • Tutorial:
  • 원리
  • 검색 복잡 도 삽입: O (l o g (v a l)) O (log (val) O (log (val))
    총 공간 복잡 도: O (n)× 40 ) O(n\times40) O(n×40)
    code:
    #include 
    
    using namespace std;
    
    #define local
    #ifdef local
    
    template<class T>
    void _E(T x) { cerr << x; }
    
    void _E(double x) { cerr << fixed << setprecision(6) << x; }
    
    void _E(string s) { cerr << "\"" << s << "\""; }
    
    template<class A, class B>
    void _E(pair<A, B> x) {
        cerr << '(';
        _E(x.first);
        cerr << ", ";
        _E(x.second);
        cerr << ")";
    }
    
    template<class T>
    void _E(vector<T> x) {
        cerr << "[";
        for (auto it = x.begin(); it != x.end(); ++it) {
            if (it != x.begin()) cerr << ", ";
            _E(*it);
        }
        cerr << "]";
    }
    
    void ERR() {}
    
    template<class A, class... B>
    void ERR(A x, B... y) {
        _E(x);
        cerr << (sizeof...(y) ? ", " : " ");
        ERR(y...);
    }
    
    #define debug(x...) do { cerr << "{ "#x" } -> { "; ERR(x); cerr << "}" << endl; } while(false)
    #else
    #define debug(...) 114514.1919810
    #endif
    #define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
    #define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
    #define _for(n, a, b) for (ll n = (a); n < (b); ++n)
    #define _rof(n, a, b) for (ll n = (a); n > (b); --n)
    #define oo 0x3f3f3f3f3f3f
    #define ll long long
    #define db long double
    #define eps 1e-3
    #define bin(x) cout << bitset<10>(x) << endl;
    #define what_is(x) cerr << #x << " is " << x << endl
    #define met(a, b) memset(a, b, sizeof(a))
    #define all(x) x.begin(), x.end()
    #define pii pair
    #define pdd pair
    #define endl "
    "
    #define ls ch[now][0] #define rs ch[now][1] const ll mod = 998244353; const ll maxn = 2e5 + 10; ll qpow(ll a, ll b) { ll ret = 1; for (; b; a = a * a % mod, b >>= 1) { if (b & 1) { ret = ret * a % mod; } } return ret; } vector<ll> f(maxn), invf(maxn); ll inv(ll a) { return qpow(a, mod - 2); } void prework() { f[0] = 1; _rep(i, 1, maxn - 1) { f[i] = f[i - 1] * i % mod; } invf[maxn - 1] = qpow(f[maxn - 1], mod - 2); for (ll i = maxn - 2; i >= 0; i--) { invf[i] = invf[i + 1] * (i + 1) % mod; } } ll C(ll n, ll m) { if (n > m || m < 0)return 0; if (n == 0 || m == n) return 1; ll res = (f[m] * invf[m - n] % mod * invf[n]) % mod; return res; } vector<pii > G[maxn]; vector<ll> a(maxn); struct Trie { ll son[2][3500005], tot; ll u[3500005];// void insert(ll a, ll th) {// ll now = 0, id; for (ll i = 30; i >= 0; i--) { id = (a >> i) & 1; if (!son[id][now])son[id][now] = ++tot; now = son[id][now]; } u[now] = th; } ll ask(ll val, ll cur = 0, ll deep = 30) {// val if (deep < 0) return u[cur]; ll op = (val >> deep) & 1; if (son[op ^ 1][cur]) return ask(val, son[op ^ 1][cur], deep - 1); else return ask(val, son[op][cur], deep - 1); } ll find(ll r1, ll r2, ll b) { if (b < 0) return 0; ll a1 = -1, a2 = -1; if (son[0][r1] && son[0][r2]) a1 = find(son[0][r1], son[0][r2], b - 1); if (son[1][r1] && son[1][r2]) a2 = find(son[1][r1], son[1][r2], b - 1); if (~a1 && ~a2) return min(a1, a2); if (~a1) return a1; if (~a2) return a2; if (son[1][r1] && son[0][r2]) a1 = find(son[1][r1], son[0][r2], b - 1) + (1 << b); if (son[0][r1] && son[1][r2]) a2 = find(son[0][r1], son[1][r2], b - 1) + (1 << b); if (~a1 && ~a2) return min(a1, a2); if (~a1) return a1; if (~a2) return a2; } void clear() { met(son, 0); met(u, 0); tot = 0; } } T; //long long ans; // //void dfs(ll a, ll b) { // if (b < 0) return; // if (T.son[0][a] && T.son[1][a]) ans += 1ll * T.find(T.son[0][a], T.son[1][a], b - 1) + (1ll << b); // if (T.son[0][a]) dfs(T.son[0][a], b - 1); // if (T.son[1][a]) dfs(T.son[1][a], b - 1); //} signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll _; cin >> _; _rep(cas, 1, _) { ll n, m; cin >> n >> m; vector<ll> a(n + 1); T.clear(); _rep(i, 1, n) { cin >> a[i]; T.insert(a[i], i); } cout << "Case #" << cas << ':' << endl; _rep(i, 1, m) { ll x; cin >> x; cout << a[T.ask(x)] << endl; } } }

    좋은 웹페이지 즐겨찾기