지속 가능 화 선분 트 리 (주석 트 리) 알고리즘 템 플 릿 과 도해
22517 단어 데이터 구조나무 위 에서 마구 잡 이 로 놀다
#include
#include
#include
#include
#include
#include
#include
#include
#define lowbit(a) ((a) & (-a))
#define OUT freopen("out.txt", "w", stdout)
#define mem(a, b) memset(a, b, sizeof(a))
#define DEBUG(a) cout << (a) << endl
#define IN freopen("in.txt", "r", stdin)
#define IO \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxn = 1e4 + 10;
struct node
{
int ls, rs;
int sum;
} tree[maxn * 20];
int tot, m;
int root[maxn];
int a[maxn], b[maxn];
string func[maxn];
void disc(int n)
{
int i;
sort(b + 1, b + n + 1);
m = unique(b + 1, b + n + 1) - (b + 1);
for (i = 1; i <= n; ++i)
a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
}
void _insert(int y, int &x, int l, int r, int p)
{
x = ++tot;
tree[x] = tree[y];
tree[x].sum++;
if (l == r)
return;
int mid = (l + r) >> 1;
if (p <= mid)
_insert(tree[y].ls, tree[x].ls, l, mid, p);
else
_insert(tree[y].rs, tree[x].rs, mid + 1, r, p);
}
int query(int x, int y, int l, int r, int k)
{
if (l == r)
return l;
int delta = tree[tree[y].ls].sum - tree[tree[x].ls].sum;
int mid = (l + r) >> 1;
if (k <= delta)
return query(tree[x].ls, tree[y].ls, l, mid, k);
else
return query(tree[x].rs, tree[y].rs, mid + 1, r, k - delta);
}
int main()
{
// IN;
IO;
int t;
int step = 0;
while (cin >> t)
{
for(int i=0;i<=tot;i++){
tree[i] = {0,0,0};
root[i] = 0;
}
tot = 0;
int tot = 1;
int buf;
for (int i = 0; i < t; i++)
{
cin >> func[i];
if (func[i] == "in")
{
cin >> buf;
a[tot] = buf;
b[tot] = a[tot];
tot++;
}
}
disc(tot);
int now = 0;
int num = 0;
int l = 0;
int r = 0;
cout <<"Case #" << ++step <<":" <<endl;
for (int i = 0; i < t; i++)
{
if (func[i] == "in")
{
now++;
_insert(root[now - 1], root[now], 1, m, a[now]);
num++;
}
else if (func[i] == "query")
DEBUG(b[query(root[l], root[now], 1, m, num / 2 + 1)]);
else
{
l++;
num--;
}
}
}
return 0;
}
먼저 구 덩이 를 파 서 코드 를 넣 고 그림 을 천천히 업데이트 합 니 다 ~ ~ ~ ~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.