头像

lixiaoqian

diep.io




离线:16小时前


最近来访(403)
用户头像
xlz
用户头像
xuexi999
用户头像
王小强
用户头像
香香小马
用户头像
小朋友没有武德
用户头像
沅芷澧兰_9
用户头像
cow马
用户头像
从前有棵树
用户头像
Hygen
用户头像
shen2347
用户头像
染尘c
用户头像
武敬轩
用户头像
jimmy2021
用户头像
itdef
用户头像
2485165291@qq.com
用户头像
白洲アズサ
用户头像
222222
用户头像
忆の風
用户头像
一只可爱严
用户头像
HAMZZQ

活动打卡代码 AcWing 253. 普通平衡树

lixiaoqian
17小时前

AcWing 253. 普通平衡树

#include <bits/stdc++.h>
#define INF (1<<30)
using namespace std ;
const int N=100010 ;
struct node { int l,r,cnt,size,key,val ; } tr[N] ;
int root=1,idx ;
int n ;
int add(int k)
{
    tr[++idx].key=k ;
    tr[idx].val=rand() ;
    tr[idx].cnt=tr[idx].size=1 ;
    return idx ;
}
void pushup(int p)
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt ;
}
void zig(int &p)
{
    int q=tr[p].l ;
    tr[p].l=tr[q].r,tr[q].r=p,p=q ;
    pushup(p),pushup(tr[p].r) ;
}
void zag(int &p)
{
    int q=tr[p].r ;
    tr[p].r=tr[q].l,tr[q].l=p,p=q ;
    pushup(p),pushup(tr[p].l) ;
}
void build()
{
    srand(time(NULL)) ;
    add(-INF),add(INF) ;
    tr[1].r=2 ;
    pushup(root) ;
    if(tr[1].val<tr[2].val) zag(root) ;
}
void ins(int &p,int k)
{
    if(!p) p=add(k) ;
    else if(tr[p].key==k) tr[p].cnt++ ;
    else if(tr[p].key>k)
    {
        ins(tr[p].l,k) ;
        if(tr[tr[p].l].val>tr[p].val) zig(p) ;
    }
    else
    {
        ins(tr[p].r,k) ;
        if(tr[tr[p].r].val>tr[p].val) zag(p) ;
    }
    pushup(p) ;
}
void del(int &p,int k)
{
    if(!p) return ;
    if(tr[p].key==k)
    {
        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) ;
                del(tr[p].r,k) ;
            }
            else
            {
                zag(p) ;
                del(tr[p].l,k) ;
            }
        }
        else p=0 ;
    }
    else if(tr[p].key>k) del(tr[p].l,k) ;
    else del(tr[p].r,k) ;
    pushup(p) ;
}
int Rank(int p,int k)
{
    if(!p) return 0 ;
    else if(tr[p].key==k) return tr[tr[p].l].size+1 ;
    else if(tr[p].key>k) return Rank(tr[p].l,k) ;
    else return tr[tr[p].l].size+tr[p].cnt+Rank(tr[p].r,k) ;
}
int key(int p,int rk)
{
    if(!p) return INF ;
    else if(tr[tr[p].l].size>=rk) return key(tr[p].l,rk) ;
    else if(tr[tr[p].l].size+tr[p].cnt>=rk) return tr[p].key ;
    else return key(tr[p].r,rk-tr[tr[p].l].size-tr[p].cnt) ;
}
int pre(int p,int k)
{
    if(!p) return -INF ;
    else if(tr[p].key>=k) return pre(tr[p].l,k) ;
    else return max(tr[p].key,pre(tr[p].r,k)) ;
}
int nxt(int p,int k)
{
    if(!p) return INF ;
    else if(tr[p].key<=k) return nxt(tr[p].r,k) ;
    else return min(tr[p].key,nxt(tr[p].l,k)) ;
}
int main()
{
    scanf("%d",&n) ;
    build() ;
    while(n--)
    {
        int op,x ;
        scanf("%d%d",&op,&x) ;
        if(op==1) ins(root,x) ;
        else if(op==2) del(root,x) ;
        else if(op==3) printf("%d\n",Rank(root,x)-1) ;
        else if(op==4) printf("%d\n",key(root,x+1)) ;
        else if(op==5) printf("%d\n",pre(root,x)) ;
        else if(op==6) printf("%d\n",nxt(root,x)) ;
    }
    return 0 ;
}


新鲜事 原文

lixiaoqian
17小时前
我终于过了平衡树!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!



lixiaoqian
18小时前

宣传一下极简计划

#include <iostream>
int main(){
    int a,b;std::cin>>a>>b;
    std::cout<<"PROD = "<<a*b;
}



lixiaoqian
18小时前

宣传一下极简计划

#include <iostream> #include <cmath> //注意头文件是可以写在同一行的
int main(){
    double r;std::cin>>r; //再次压行
    printf("A=%.4lf",r*r*3.14159); //不用定义圆周率变量了,直接用就好
    return 0;
}



lixiaoqian
19小时前

宣传一下极简计划

#include <iostream>
int main(){
    for(int m,n,sum=0;std::cin>>m>>n&&m>0&&n>0;std::cout<<"Sum="<<sum<<'\n',sum=0)
        for(int i=(n<m?n:m);i<=(n>m?n:m);sum+=i++)cout<<i<<' ';
}
// 解释一下:
// n<m?n:m是min(n,m)
// n>m?n:m是max(n,m)
// 初始化直接在for循环内部定义所有需要的变量(for大法好)
// sum+=i++就是:
// sum+=i,i++



lixiaoqian
19小时前

受到彩笔聚聚的影响,把所有语法题的极简代码(也就是Saber代码)写出来

604
605
722



问题 呜呜呜

这段代码牺牲了一半的脑细胞

#include <bits/stdc++.h>
#define INF (1<<30)
using namespace std ;
const int N=100010 ;
struct node
{
    int l,r,cnt,size,key,val ;
    node(int k) { l=r=0,key=k,cnt=size=1,val=rand() ;}
    node() { l=r=key=0,cnt=size=1,val=rand() ; }
} tr[N] ;
int root=1,idx ;
void pushup(int p)
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt ;
}
void zig(int &p)
{
    int q=tr[p].l ;
    tr[p].l=tr[p].r,tr[p].r=p,p=q ;
    pushup(p),pushup(tr[p].l),pushup(tr[p].r) ;
}
void zag(int &p)
{
    int q=tr[p].r ;
    tr[p].r=tr[p].l,tr[p].l=p,p=q ;
    pushup(p),pushup(tr[p].l),pushup(tr[p].r) ;
}
void build()
{
    tr[++idx]=-INF,tr[++idx]=INF ;
    tr[1].r=2 ;
    pushup(root) ;
    if(tr[1].val<tr[2].val) zag(root) ;
}
void ins(int &p,int k)
{
    if(!p) tr[p=++idx]=k ;
    else if(tr[p].key==k) tr[p].cnt++ ;
    else if(tr[p].key<k)
    {
        ins(tr[p].r,k) ;
        if(tr[tr[p].r].val>tr[p].val) zag(p) ;
    }
    else
    {
        ins(tr[p].l,k) ;
        if(tr[tr[p].l].val>tr[p].val) zig(p) ;
    }
    pushup(p) ;
}
void del(int &p,int k)
{
    if(!p) return ;
    if(tr[p].key==k)
    {
        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) ;
                del(tr[p].l,k) ;
            }
            else
            {
                zag(p) ;
                del(tr[p].r,k) ;
            }
        }
        else p=0 ;
    }
}
int Rank(int p,int k)
{
    if(tr[p].key==k) return tr[tr[p].l].size+1 ;
    else if(tr[p].key>k) return Rank(tr[p].l,k) ;
    else return tr[tr[p].l].size+tr[p].cnt+Rank(tr[p].r,k) ;
}
int key(int p,int rk)
{
    if(tr[tr[p].l].size>=rk) return key(tr[p].l,rk) ;
    else if(tr[tr[p].l].size+tr[p].cnt>=rk) return tr[p].key ;
    else return key(tr[p].r,rk-tr[tr[p].l].size-tr[p].cnt) ;
}
int pre(int p,int k)
{
    if(!p) return -INF ;
    else if(tr[p].key>=k) return pre(tr[p].l,k) ;
    else return max(tr[p].key,pre(tr[p].r,k)) ;
}
int nxt(int p,int k)
{
    if(!p) return INF ;
    else if(tr[p].key>=k) return pre(tr[p].r,k) ;
    else return min(tr[p].key,pre(tr[p].l,k)) ;
}
int main()
{
    srand(time(NULL)) ;
    int n ;
    build() ;
    scanf("%d",&n) ;
    while(n--)
    {
        int op,x ;
        scanf("%d%d",&op,&x) ;
        if(op==1) ins(root,x) ;
        else if(op==2) del(root,x) ;
        else if(op==3) printf("%d\n",Rank(root,x)-1) ;
        else if(op==4) printf("%d\n",key(root,x+1)) ;
        else if(op==5) printf("%d\n",pre(root,x)) ;
        else if(op==6) printf("%d\n",nxt(root,x)) ;
    }
    return 0 ;
}

这次是薛定谔的treap,一会MLE,一会输出随机值,反正就没一次正常



问题 好离谱

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 1e8;

int n;
struct Node
{
    int l, r;
    int key, val;
    int cnt, size;
}tr[N];

int root, idx;

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

int get_node(int key)
{
    tr[ ++ idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 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 build()
{
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(root);

    if (tr[1].val < tr[2].val) zag(root);
}


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 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);
}

int get_rank_by_key(int p, int key)    // 通过数值找排名
{
    if (!p) return 0;   // 本题中不会发生此情况
    if (tr[p].key == key) return tr[tr[p].l].size + 1;
    if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank)   // 通过排名找数值
{
    if (!p) return INF;     // 本题中不会发生此情况
    if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int get_prev(int p, int key)   // 找到严格小于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)    // 找到严格大于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();

    scanf("%d", &n);
    while (n -- )
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(root, x);
        else if (opt == 2) remove(root, x);
        else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
        else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1));
        else if (opt == 5) printf("%d\n", get_prev(root, x));
        else printf("%d\n", get_next(root, x));
    }

    return 0;
}

//作者:yxc
//链接:https://www.acwing.com/activity/content/code/content/168876/
//来源:AcWing
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这里并没有srand(time(NULL)),为什么AC了?




排序算法,理论最快O(n),最慢O(nlogn)

#include <bits/stdc++.h>
using namespace std ;
const int N=100010 ;
typedef pair<int,int> pii ;
int nxt[N],e[N] ;
priority_queue<pii,vector<pii>,greater<pii>> heap ;
int main()
{
    int n ;
    scanf("%d",&n) ;
    for(int i=1,last=0;i<=n;i++)
    {
        int x ;
        scanf("%d",&x) ;
        if(!last) heap.push({x,i}) ;
        if(last>=x) heap.push({x,i}),nxt[i-1]=-1 ;
        else nxt[i-1]=i ;
        e[i]=last=x ;
    }
    nxt[n]=-1 ;
    while(heap.size()>1)
    {
        auto t=heap.top() ;
        heap.pop() ;
        printf("%d ",t.first) ;
        int ne=nxt[t.second] ;
        if(~ne) heap.push({e[ne],ne}) ;
    }
    for(int i=heap.top().second;~i;i=nxt[i]) printf("%d ",e[i]) ;
    return 0 ;
}

同样的测试数据,快排跑了100ms,我的排序跑了800ms,是因为STL太慢了吗?



新鲜事 原文

欢迎大家来水题(第二遍了) https://www.luogu.com.cn/problem/U102773