01trie 트 리 템 플 릿 I - 구 또는 최 값
39713 단어 01trie 나무 정말 하늘하늘데이터 구조트 리 트 리
Face
제목
데이터 범위: 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
선행 기술
총 공간 복잡 도: 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;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Sparse Table을 아십니까? 나는 알고 있다.Sparse Table을 지금 배웠으므로, 메모를 겸해 씁니다. 불변의 수열의 임의의 구간에 대한 최소치/최대치를, 전처리 $O(N\log N)$, 쿼리 마다 $O(1)$ 로 구하는 데이터 구조입니다. 숫자 열의 값...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.