nuo0930

1134

wiaxiamm
ohmygod
Little_Sealx

Tequila
nqR

InsaneFourier

wlyhuat
Albatross_3
Eason_AC

Takenzz
liang_xi_

shewaitspatiently
Barbed

nuo0930
5个月前

nuo0930
5个月前

nuo0930
5个月前

nuo0930
7个月前

nuo0930
7个月前

void quick_sort(int l, int r) {
if(l >= r)
return;
int pivot = a[rand() % (r - l + 1) + l], i = l, j = l, k = r + 1;
for(; i < k; ){
if(a[i] < pivot)
swap(a[i++], a[j++]);
else if(pivot < a[i])
swap(a[i], a[--k]);
else
++i;
}
quick_sort(l, j);
quick_sort(k, r);
}


#include <math.h>
#include <stdio.h>
#include <time.h>
const int maxn = 100010;
int a[ maxn ];
inline unsigned _rand( ) {
static unsigned seed = time( 0 );
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
return seed;
}
inline void swap( int &a, int &b ) {
int t = a;
a = b;
b = t;
}
void insert_sort( int l, int r ) {
for ( int i = l + 1; i <= r; ++i )
for ( int j = i; j > l && a[ j - 1 ] > a[ j ]; --j )
swap( a[ j - 1 ], a[ j ] );
}
int *heap;
int heap_size;
void heapify( int x ) {
for ( bool ch; ( x << 1 ) <= heap_size;
swap( heap[ x << 1 | ch ], heap[ x ] ), x = x << 1 | ch ) {
ch = ( x << 1 ) < heap_size
&& heap[ x << 1 ] <= heap[ x << 1 | 1 ];
if ( heap[ x << 1 | ch ] <= heap[ x ] )
return;
}
}
void heap_sort( int l, int r ) {
heap = a + l - 1;
heap_size = r - l + 1;
for ( int i = heap_size >> 1; i; )
heapify( i-- );
for ( ; heap_size; heapify( 1 ) )
swap( heap[ 1 ], heap[ heap_size-- ] );
}
void quick_sort( int l, int r, int cnt ) {
if ( r - l < 10 ) {
insert_sort( l, r );
return;
}
if ( !cnt ) {
heap_sort( l, r );
return;
}
int pivot = a[ _rand( ) % ( r - l + 1 ) + l ], i = l, j = l, k = r + 1;
for ( ; i < k; ) {
if ( a[ i ] < pivot )
swap( a[ i++ ], a[ j++ ] );
else if ( pivot < a[ i ] )
swap( a[ i ], a[ --k ] );
else
++i;
}
quick_sort( l, j, cnt - 1 );
quick_sort( k, r, cnt - 1 );
}
void sort( int n ) {
quick_sort( 1, n, log2( n ) );
}
int main( ) {
int n;
scanf( "%d", &n );
for ( int i = 1; i <= n; i++ )
scanf( "%d", &a[ i ] );
sort( n );
for ( int i = 1; i <= n; i++ )
printf( "%d ", a[ i ] );
return 0;
}


nuo0930
10个月前

#include <cstdio>
#include <cstdlib>
const int maxsize = 30001000;
int val[maxsize];
int key[maxsize];
int size[maxsize];
int lc[maxsize], rc[maxsize];
int nodecnt;
inline int newnode(int x) {
key[++nodecnt] = std::rand();
val[nodecnt] = x;
lc[nodecnt] = rc[nodecnt] = 0;
size[nodecnt] = 1;
return nodecnt;
}
inline int copynode(int x) {
key[++nodecnt] = key[x];
val[nodecnt] = val[x];
lc[nodecnt] = lc[x];
rc[nodecnt] = rc[x];
size[nodecnt] = size[x];
return nodecnt;
}
inline void pushup(int rt) {
size[rt] = size[lc[rt]] + size[rc[rt]] + 1;
}
void split(int rt, int x, int& a, int& b) {
if (!rt)
return (void)(a = b = 0);
int t = copynode(rt);
if (val[rt] <= x) {
a = t;
split(rc[a], x, rc[a], b);
} else {
b = t;
split(lc[a], x, a, lc[a]);
}
pushup(t);
}
void _split(int rt, int x, int& a, int& b) {
if (!rt)
return (void)(a = b = 0);
if (val[rt] <= x) {
a = rt;
_split(rc[rt], x, rc[rt], b);
} else {
b = rt;
_split(lc[rt], x, a, lc[rt]);
}
pushup(rt);
}
void join(int& rt, int a, int b) {
if (!a || !b)
return (void)(rt = a ^ b);
if (key[a] < key[b]) {
rt = b;
join(lc[rt], a, lc[b]);
} else {
rt = a;
join(rc[rt], rc[rt], b);
}
pushup(rt);
}
void ins(int rt, int x) {
int a, b;
split(rt, x, a, b);
join(a, a, newnode(x));
join(rt, a, b);
}
void del(int& rt, int x) {
int a, b, c;
split(rt, x, a, b);
split(a, x - 1, a, c);
join(c, lc[c], rc[c]);
join(a, a, c);
join(rt, a, b);
}
int value(int rt, int x) {
if (x <= size[lc[rt]])
return value(lc[rt], x);
if (x > size[lc[rt]] + 1)
return value(rt, x - size[lc[rt]] - 1);
return val[rt];
}
int rank(int rt, int x) {
int a, b;
_split(rt, x - 1, a, b);
int ans = size[a] + 1;
join(rt, a, b);
return ans;
}
int max(int rt) {
if (!rt)
return -2147483648;
if (rc[rt])
return max(rc[rt]);
return val[rt];
}
int pre(int& rt, int x) {
int a, b;
_split(rt, x - 1, a, b);
int ans = max(a);
join(rt, a, b);
return ans;
}
int min(int rt) {
if (!rt)
return 2147483647;
if (lc[rt])
return min(lc[rt]);
return val[rt];
}
int nxt(int& rt, int x) {
int a, b;
_split(rt, x, a, b);
int ans = min(b);
join(rt, a, b);
return ans;
}
const int maxn = 500001;
int root[maxn];
int main() {
int m;
std::scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int v, op, x;
std::scanf("%d%d%d", &v, &op, &x);
root[i] = v;
switch (op) {
case 1:
ins(root[i], x);
break;
case 2:
del(root[i], x);
break;
case 3:
std::printf("%d\n", rank(root[i], x));
break;
case 4:
std::printf("%d\n", value(root[i], x));
break;
case 5:
std::printf("%d\n", pre(root[i], x));
break;
case 6:
std::printf("%d\n", nxt(root[i], x));
break;
}
}
return 0;
}


nuo0930
10个月前

#include<cstdio>
#include<cstdlib>
struct tree_node{
short key;
int val;
int cnt;
int size;
int lc,rc;
tree_node() {
key=0;
val=0;
cnt=0;
size=0;
lc=rc=0;
}
tree_node(int a) {
key=std::rand();
val=a;
cnt=1;
size=1;
lc=rc=0;
}
}tree[100001];
int cnt;
inline int newnode(int a) {
tree[++cnt]=tree_node(a);
return cnt;
}
inline void pushup(int rt) {
tree[rt].size=tree[tree[rt].lc].size+tree[tree[rt].rc].size+tree[rt].cnt;
}
void value_split(int rt,int x,int &a,int &b) {
if(!rt) {
a=b=0;
return ;
}
if(tree[rt].val<=x) {
a=rt;
value_split(tree[rt].rc,x,tree[a].rc,b);
}
else {
b=rt;
value_split(tree[rt].lc,x,a,tree[b].lc);
}
pushup(rt);
}
void rank_split(int rt,int x,int &a,int &b) {
if(!rt) {
a=b=0;
return ;
}
int tmp=tree[tree[rt].lc].size+tree[rt].cnt;
if(tmp<=x) {
a=rt;
rank_split(tree[rt].rc,x-tmp,tree[a].rc,b);
}
else {
b=rt;
rank_split(tree[rt].lc,x,a,tree[b].lc);
}
pushup(rt);
}
void merge(int &rt,int a,int b) {
if(!a||!b) {
rt=a^b;
return ;
}
if(tree[a].key>=tree[b].key) {
rt=a;
merge(tree[a].rc,tree[a].rc,b);
}
else {
rt=b;
merge(tree[b].lc,a,tree[b].lc);
}
pushup(rt);
}
void ins(int& rt,int x) {
int a=0,b=0,c=0;
value_split(rt,x,a,b);
value_split(a,x-1,a,c);
if(c)
tree[c].cnt=tree[c].size=tree[c].cnt+1;
else
c=newnode(x);
merge(a,a,c);
merge(rt,a,b);
}
bool del(int& rt,int x) {
int a=0,b=0,c=0;
bool flag=true;
value_split(rt,x,a,b);
value_split(a,x-1,a,c);
if(!c)
flag=false;
else
if(!(tree[c].cnt=tree[c].size=tree[c].cnt-1))
c=0;
merge(a,a,c);
merge(rt,a,b);
return flag;
}
int the_min(int rt) {
for(;tree[rt].lc;rt=tree[rt].lc);
return tree[rt].val;
}
int the_max(int rt) {
for(;tree[rt].rc;rt=tree[rt].rc);
return tree[rt].val;
}
int rank(int &rt,int x) {
int a=0,b=0;
value_split(rt,x-1,a,b);
int ans=tree[a].size+1;
merge(rt,a,b);
return ans;
}
int value(int &rt,int x) {
int a=0,b=0;
rank_split(rt,x,a,b);
int ans=the_max(a);
merge(rt,a,b);
return ans;
}
int pre(int &rt,int x) {
int a=0,b=0;
value_split(rt,x-1,a,b);
int ans=the_max(a);
merge(rt,a,b);
return ans;
}
int nxt(int &rt,int x) {
int a=0,b=0;
value_split(rt,x,a,b);
int ans=the_min(b);
merge(rt,a,b);
return ans;
}
int main() {
srand(2333*114*514);
int m;
int op,x;
std::scanf("%d",&m);
int root=0;
while(m--) {
scanf("%d%d",&op,&x);
switch(op) {
case 1: {
ins(root,x);
break;
}
case 2: {
del(root,x);
break;
}
case 3: {
printf("%d\n",rank(root,x));
break;
}
case 4: {
printf("%d\n",value(root,x));
break;
}
case 5: {
printf("%d\n",pre(root,x));
break;
}
case 6: {
printf("%d\n",nxt(root,x));
break;
}
}
}
return 0;
}