UOJ Logo chtomede的博客

博客

来诈尸了捏

2022-06-03 02:56:01 By chtomede

学弟们好好努力捏 爱拼才会赢 大学也不能躺平捏 不说了 准备补考去了

身败名裂

2019-12-18 18:40:45 By chtomede

想着拿树状数组做个A+B给高一的教一下A+B的正确姿势,然而失败了(luogu上就A了,LFYZOJ的数据还是强,233)

Update:第二天cyx也失败了,比我还惨,233,update里没开ll

STL封装版 单调队列

2019-11-07 19:48:49 By chtomede
struct QueueNode{int pos,val;};
struct HD_Queue
{
    deque<QueueNode> Q1,Q2;int k;
    inline void init(int length){k=length;}
    inline void clear(){Q1.clear();Q2.clear();}
    inline void push_max(int pos,int val)
    {
        while(!Q1.empty()&&pos-Q1.front().pos>=k)    Q1.pop_front();
        while(!Q1.empty()&&val>=Q1.back().val) Q1.pop_back();
        Q1.push_back((QueuNode){pos,val}); 
    }
    inline void push_min(int pos,int val)
    {
        while(!Q2.empty()&&pos-Q2.front().pos>=k)    Q2.pop_front();
        while(!Q2.empty()&&val<=Q2.back().val) Q2.pop_back();
        Q2.push_back((QueueNode){pos,val}); 
    }
    inline ll the_max(int pos)
    {
        while(!Q1.empty()&&pos-Q1.front().pos>=k)    Q1.pop_front();
        if(!Q1.empty())    return Q1.front().val;
        else            return 0;
    }
    inline ll the_min(int pos)
    {
        while(!Q2.empty()&&pos-Q2.front().pos>=k)    Q2.pop_front();
        if(!Q2.empty())    return Q2.front().val;
        else            return (ll)1e20;
    }
}q[N];

Treap(数组实现)

2019-04-27 06:38:07 By chtomede
#include<iostream>
#include<cstdio>
#include<cstdlib>
const int MaxN=100500,INF=0x7fffffff;
using namespace std;
struct Node{int cnt,lc,rc,val,siz,key;}a[MaxN];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,tot,root;
inline void update(int pos){a[pos].siz=a[a[pos].lc].siz+a[a[pos].rc].siz+a[pos].cnt;}
inline void zig(int & pos){int x=a[pos].rc;a[pos].rc=a[x].lc;a[x].lc=pos;a[x].siz=a[pos].siz;update(pos);pos=x;}
inline void zag(int & pos){int x=a[pos].lc;a[pos].lc=a[x].rc;a[x].rc=pos;a[x].siz=a[pos].siz;update(pos);pos=x;}
inline void insert(int & pos,const int va)
{
    if(!pos)    pos=++tot,a[pos].val=va,a[pos].cnt=1,a[pos].key=-rand();
    else if(a[pos].val==va)    a[pos].cnt++;
    else if(a[pos].val<va)
    {
        insert(a[pos].rc,va);
        if(a[a[pos].rc].key<a[pos].key)    zig(pos);    
    }
    else if(a[pos].val>va)    
    {
        insert(a[pos].lc,va);
        if(a[a[pos].lc].key<a[pos].key)    zag(pos);
    }
    update(pos);
}
inline void Dlt(int & pos,int va)
{
    if(a[pos].val<va)    Dlt(a[pos].rc,va);
    else if(a[pos].val>va)    Dlt(a[pos].lc,va);
    else if(a[pos].val==va)
    {
        if(a[pos].cnt>1)    a[pos].cnt--;
        else if(!a[pos].lc&&!a[pos].rc)    pos=0;
        else if(!a[pos].lc&&a[pos].rc)    pos=a[pos].rc;
        else if(!a[pos].rc&&a[pos].lc)    pos=a[pos].lc;
        else
        {
            if(a[a[pos].lc].key>a[a[pos].rc].key)    zig(pos),Dlt(a[pos].lc,va);
            else    zag(pos),Dlt(a[pos].rc,va);
        }
    }
    update(pos);
}
inline int rank(int pos,const int va,int k)
{
    if(!pos)    return 0;
    if(a[pos].val==va)    return k+a[a[pos].lc].siz+1;
    if(a[pos].val<va)    {k+=a[a[pos].lc].siz+a[pos].cnt;return rank(a[pos].rc,va,k);}
    else    return rank(a[pos].lc,va,k);
}
inline int srank(int pos,const int rk,int k)
{
    if(!pos)    return 0;
    if(a[a[pos].lc].siz+1+k<=rk&&a[a[pos].lc].siz+a[pos].cnt+k>=rk)    return a[pos].val;
    if(a[a[pos].lc].siz+a[pos].cnt+k<rk){k+=a[a[pos].lc].siz+a[pos].cnt;return srank(a[pos].rc,rk,k);}
    else    return srank(a[pos].lc,rk,k);
}
inline int lst(int pos,const int va)
{
    int ans=-INF;
    while(pos)
    {
        if(a[pos].val<va&&a[pos].val>ans)    ans=a[pos].val;
        if(va<=a[pos].val)    pos=a[pos].lc;
        else                pos=a[pos].rc;
    }
    return ans;
}
inline int nxt(int pos,const int va)
{
    int ans=INF;
    while(pos)
    {
        if(a[pos].val>va&&a[pos].val<ans)    ans=a[pos].val;
        if(a[pos].val>va)    pos=a[pos].lc;
        else                pos=a[pos].rc;
    }
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
    {
        int op=read(),x=read();
        if(op==1)    insert(root,x);
        if(op==2)    Dlt(root,x);
        if(op==3)    printf("%d\n",rank(root,x,0));
        if(op==4)    printf("%d\n",srank(root,x,0));
        if(op==5)    printf("%d\n",lst(root,x));
        if(op==6)    printf("%d\n",nxt(root,x));
    }
    return 0;
}

BST

2019-04-26 17:05:31 By chtomede
#include<iostream>
#include<cstdio>
const int MaxN=100500,INF=0x7fffffff;
using namespace std;
struct Node{int cnt,lc,rc,val,siz;}a[MaxN];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,tot,root;
inline void update(int pos)
{
    a[pos].siz=a[a[pos].lc].siz+a[a[pos].rc].siz+a[pos].cnt;
}
inline void insert(int & pos,const int va)
{
    if(!pos)    pos=++tot,a[pos].val=va,a[pos].cnt=1;
    else if(a[pos].val==va)    a[pos].cnt++;
    else if(a[pos].val<va)    insert(a[pos].rc,va);
    else if(a[pos].val>va)    insert(a[pos].lc,va);
    update(pos);
}
inline Node DltMin(int & pos)
{
    if(a[pos].lc){Node y=DltMin(a[pos].lc);update(pos); return y;}
    Node x=a[pos]; pos=a[pos].rc; return x;
}
inline void Dlt(int & pos,const int va)
{
    if(a[pos].val<va)            Dlt(a[pos].rc,va);
    else if(a[pos].val>va)       Dlt(a[pos].lc,va);
    else if(a[pos].val==va)
    {
        if(a[pos].cnt>1)    a[pos].cnt--;
        else if(a[pos].lc&&a[pos].rc)    {Node x=DltMin(a[pos].rc);a[pos].cnt=x.cnt;a[pos].val=x.val;}
        else if(a[pos].lc&&!a[pos].rc)    pos=a[pos].lc;
        else if(a[pos].rc&&!a[pos].lc)    pos=a[pos].rc;
        else if(!a[pos].lc&&!a[pos].rc)    pos=0;
    }
    update(pos);
}
inline int rank(int pos,const int va,int k)
{
    if(a[pos].val==va)    return k+a[a[pos].lc].siz+1;
    if(a[pos].val<va)    {k+=a[a[pos].lc].siz+a[pos].cnt;return rank(a[pos].rc,va,k);}
    else    return rank(a[pos].lc,va,k);
}
inline int srank(int pos,const int rk,int k)
{
//    cout<<a[a[pos].lc].siz<<" "<<k<<" "<<rk<<endl;
    if(a[a[pos].lc].siz+1+k<=rk&&a[a[pos].lc].siz+a[pos].cnt+k>=rk)    return a[pos].val;
    if(a[a[pos].lc].siz+a[pos].cnt+k<rk){k+=a[a[pos].lc].siz+a[pos].cnt;return srank(a[pos].rc,rk,k);}
    else    return srank(a[pos].lc,rk,k);
}
inline int lst(int pos,const int va)
{
    int ans=-INF;
    while(pos)
    {
        if(a[pos].val<va&&a[pos].val>ans)    ans=a[pos].val;
        if(va<=a[pos].val)    pos=a[pos].lc;
        else                pos=a[pos].rc;
    }
    return ans;
}
inline int nxt(int pos,const int va)
{
    int ans=INF;
    while(pos)
    {
        if(a[pos].val>va&&a[pos].val<ans)    ans=a[pos].val;
        if(a[pos].val>va)    pos=a[pos].lc;
        else                pos=a[pos].rc;
    }
    return ans;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
    {
        int op=read(),x=read();
        if(op==1)    insert(root,x);
        if(op==2)    Dlt(root,x);
        if(op==3)    cout<<rank(root,x,0)<<endl;
        if(op==4)    cout<<srank(root,x,0)<<endl;
        if(op==5)    cout<<lst(root,x)<<endl;
        if(op==6)    cout<<nxt(root,x)<<endl;
    }
    return 0;
}
chtomede Avatar