wt20

$\href{https://www.acwing.com/blog/content/14829/}{个人主页}$但是我真的没被封号！别去问y总了！y总都快被你们烦死了……！！六年级同学

6.0万

workhard_
rd0

liyuanchen
pengpeng_fudan
DreamFather

learners
.yxc.

mmmmm

YikN
Sistina_yang

codefish7

2010
0918k

wt20
15天前

wt20
1个月前

wt20
1个月前

wt20
2个月前

wt20
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10, INF = 1e8;
int n;
struct Node{
int l, r;
int key, val;
int cnt, s;
}tr[N];

int root, idx;

void pushup(int p) {
tr[p].s = tr[tr[p].l].s + tr[tr[p].r].s + tr[p].cnt;
}

int get_node(int key) {
tr[ ++ idx].key = key;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].s = 1;
return idx;
}

void zig(int &p) {
int q = tr[p].l;
tr[p].l = tr[q].r, tr[q].r = p, p = q;
pushup(tr[p].r), pushup(p);
}

void zag(int &p) {
int q = tr[p].r;
tr[p].r = tr[q].l, tr[q].l = p, p = q;
pushup(tr[p].l), pushup(p);
}

void remove(int &p, int key) {
if (!p) return;
if (tr[p].key == key) {
if (tr[p].cnt > 1) tr[p].cnt --;
else if (tr[p].l || tr[p].r) {
if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
zig(p);
remove(tr[p].r, key);
}
else {
zag(p);
remove(tr[p].l, key);
}
}
else p = 0;
}
else if (tr[p].key > key) remove(tr[p].l, key);
else remove(tr[p].r, key);
pushup(p);
}

void insert(int &p, int key) {
if (!p) p = get_node(key);
else if (tr[p].key == key) tr[p].cnt ++;
else if (tr[p].key > key) {
insert(tr[p].l, key);
if (tr[tr[p].l].val > tr[p].val) zig(p);
}
else {
insert(tr[p].r, key);
if (tr[tr[p].r].val > tr[p].val) zag(p);
}
pushup(p);
}

void build() {
get_node(-INF), get_node(INF);
root = 1, tr[1].r = 2;
pushup(root);
}

int get_rk(int &p, int key) {
if (!p) return 0;
if (tr[p].key == key) return tr[tr[p].l].s + 1;
if (tr[p].key > key) return get_rk(tr[p].l, key);
else return tr[tr[p].l].s + tr[p].cnt + get_rk(tr[p].r, key);
}

int get_key(int &p, int rank) {
if (!p) return INF;
if (tr[tr[p].l].s >= rank) return get_key(tr[p].l, rank);
if (tr[p].cnt + tr[tr[p].l].s >= rank) return tr[p].key;
return get_key(tr[p].r, rank - tr[tr[p].l].s - tr[p].cnt);

}

int get_prev(int &p, int key) {
if (!p) return -INF;
if (tr[p].key >= key) return get_prev(tr[p].l, key);
return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int &p, int key) {
if (!p) return INF;
if (tr[p].key <= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}

int main() {
build();
cin >> n;
while (n -- ) {
int opt, x;
cin >> opt >> x;
if (opt == 1) insert(root, x);
else if (opt == 2) remove(root, x);
else if (opt == 3) cout << get_rk(root, x)  - 1 << endl;
else if (opt == 4) cout << get_key(root, x + 1) << endl;
else if (opt == 5) cout << get_prev(root, x) << endl;
else cout << get_next(root, x) << endl;
}
return 0;
}


wt20
2个月前

wt20
2个月前

wt20
2个月前
CF463C 这个题就是CFdiv2C题，你告诉我这洛谷评紫？？ 况且就是个统计

wt20
2个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
struct D{
int a, b, c, x;
int res;
bool operator< (const D& t) const {
if (a != t.a) return a < t.a;
if (b != t.b) return b < t.b;
return c < t.c;
}
bool operator== (const D& t) const {
return a == t.a && b == t.b && c == t.c;
}
}q[N], w[N];
int tr[M], ans[M];

int lowbit(int x)
{
return x & -x;
}

void add(int x, int v) {
for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}

int query(int x)  // 返回前x个数的和
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}

void merge_sort(int l, int r)  // 归并排序
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);

int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (q[i].b <= q[j].b)
add(q[i].c, q[i].x), w[k ++ ] = q[i ++ ];
else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
while (i <= mid) add(q[i].c, q[i].x), w[k ++ ] = q[i ++ ];
while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].x);
for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
q[i] = {a, b, c, 1};
}
sort(q, q + n);

int k = 1;
for (int i = 1; i < n; i ++ )
if (q[i] == q[k - 1]) q[k - 1].x ++;
else q[k ++ ] = q[i];

merge_sort(0, k - 1);
for (int i = 0; i < k; i ++ )
ans[q[i].res + q[i].x - 1] += q[i].x;

for (int i = 0; i < n; i ++ )
printf("%d\n", ans[i]);
return 0;
}


wt20
2个月前
https://www.luogu.com.cn/team/49116 虽说是"我带你"，但是是大家共同学习hh