UOJ Logo lris的博客

博客

人世无常,学弟学妹加我啊

2020-09-20 16:15:06 By lris

转眼间就毕业了。

看了一眼,我大概不会做自己出的题了……

最近大学开学了,打算看看雅礼的题复健一下,结果发现居然有人在写,tql

有兴趣的话可以翻翻我以前的博客,好像是有雅礼的题解的(不过我的博客挂了,你可以试试这个看看能不能访问,如果不能就是我太懒了)

总之希望感兴趣的学弟学妹加我(qq2443064471)

有没有什么有趣的夏令营啊

2019-06-10 11:15:54 By lris

高二鶸省一选手(315pts),无其他奖项。

综合成绩以前100-(上次133,这次9),有什么适合的夏令营推荐么qwq

老咸鱼祝学习快乐~顺便宣传指针……

2019-02-12 16:48:07 By lris

这里是书名号《 》,退役老学长一枚,祝大家学习快乐~

以及别听老韩的,指针大法好! 给学妹看的指针简要介绍

为什么是学妹?我校自古有OIers女装的传统,学弟思考一下。

我都女装了qwq,你们不试试?

并查集的正确使用方式

2018-12-03 16:44:33 By lris
struct UFS
{
    int *f, *siz;
    UFS(int n): f(new int[n+1]), siz(new int[n+1]) {}
    void Find(int x)
      { return x==f[x]? x:f[x]=Find(f[x]); }
    void Union(int x, int y)
    {
        x=Find(x), y=Find(y);
        if(siz[x]>siz[y]) swap(x, y);
        f[x]=y, siz[y]+=(x==y);    
    }
}*s;

复杂度为反阿克曼函数,可以认为是O(1),这样Kruscal的复杂度才为O(n+mlogm)

一些简单的封装

2018-10-29 20:07:11 By lris

邻接表

struct Edge
{
    int v, w; Edge* nxt;
    Edge(int v, int w, Edge* nxt):
        v(v), w(w), nxt(nxt) {}
}*hd[N];
void AddEdge(int u, int v, int w)
  { hd[u]=new Edge(v, w, hd[u]); }

并查集

struct UFS
{
    int* f;
    UFS(int n): f(new int [n+1])
      { for(int i=1; i<=n; ++i) f[i]=i; }
    int Find(int x) 
      { return x==f[x]? x:f[f[x]]=Find(f[x]); }
    bool Merge(int a, int b)
    {
        a=Find(a), b=Find(b);
        return a==b? 0:f[a]=b;
    } 
}*s;

线段树(标记)

struct Tree
{
    Tree *lc, *rc;
    int l, r;
    ll dat, add, mul;
    Tree(int l, int r, Tree* lc, Tree* rc):
        l(l), r(r), lc(lc), rc(rc), dat((lc->dat+rc->dat)%p), add(0), mul(1) {}
    Tree(int l, int r):        //叶节点
        l(l), r(r), lc(NULL), rc(NULL), dat(a[l]), add(0), mul(1) {}
    static Tree* Build(int l, int r)
    {
        if(l>r) return NULL;
        if(l==r) return new Tree(l, r);
        int mid=l+(r-l)/2;
        return new Tree(l, r, Build(l, mid), Build(mid+1, r));
    }
    void Covermul(ll x)
      { dat=dat*x%p, mul=mul*x%p, add=add*x%p; }
    void Coveradd(ll x)
      { add=(add+x)%p, dat=(dat+x*(r-l+1))%p; }
    void Pushup()
      { dat=(lc->dat+rc->dat)%p; }
    void Pushdown()
    {
        lc->Covermul(mul); lc->Coveradd(add);
        rc->Covermul(mul); rc->Coveradd(add);
        mul=1, add=0;
    }
    void Multi(int l, int r, ll k)
    {
        if(l>this->r || r<this->l) return;
        if(l<=this->l && r>=this->r) Covermul(k);
        else
        {
            Pushdown();
            lc->Multi(l, r, k);
            rc->Multi(l, r, k);
            Pushup(); 
        }
    }
    void Addit(int l, int r, ll k)
    {
        if(l>this->r || r<this->l) return;
        if(l<=this->l && r>=this->r) Coveradd(k);
        else
        {
            Pushdown();
            lc->Addit(l, r, k);
            rc->Addit(l, r, k);
            Pushup(); 
        }
    }
    ll Ask(int l, int r)
    {
        if(l>this->r || r<this->l) return 0;
        if(l<=this->l && r>=this->r) return dat;
        Pushdown();
        return (lc->Ask(l, r)+rc->Ask(l, r))%p;
    }
};

内存池

struct Tree
{
    Tree *l, *r; int tot;
    Tree(Tree* l=NULL, Tree* r=NULL):
        l(l), r(r), tot(0) {}
}poorpool[PS], *root[N+3];
Tree* New()
{
    static int c_pool=0;
    if(c_pool==PS) return new Tree();
    return &poorpool[c_pool++];
}
lris Avatar