板子

CAICAIA · 2023-11-23 18:21:54 · 个人记录

线段树

#include <bits/stdc++.h>
using namespace std;
const  long long MX=1e5+10;
long long n,m,cnt=0;
long long input[MX]={0};
struct Node{
    long long lazy,sum;
    long long lc,rc;
}tree[MX<<1];
inline void addnode(long long &now,long long l,long long r,long long val){
    if(now==0)  now=++cnt;
    tree[now].sum+=(r-l+1)*val;tree[now].lazy+=val;return ;
}

inline void pushup(long long now){
    tree[now].sum=tree[tree[now].lc].sum+tree[tree[now].rc].sum;return ;
}
inline void pushdown(long long now,long long l,long long r){
    if(l>=r)  return;
    long long mid=(l+r-1)>>1;
    addnode(tree[now].lc,l,mid,tree[now].lazy);
    addnode(tree[now].rc,mid+1,r,tree[now].lazy);
    tree[now].lazy=0;
    return ;
}
void update(long long now,long long lt,long long rt,long long l,long long r,long long val){
    if(r<lt||l>rt){
        return ;
    }
    if(l<=lt&&rt<=r){
        addnode(now,lt,rt,val);
        return ;
    }
    pushdown(now,lt,rt);
    long long mid=(lt+rt-1)/2;
    update(tree[now].lc,lt,mid,l,r,val);update(tree[now].rc,mid+1,rt,l,r,val);
    pushup(now);
    return ;
}
long long query(long long now,long long lt,long long rt,long long l,long long r){
    if(r<lt||l>rt){
        return 0;
    }
    if(l<=lt&&rt<=r){
        return tree[now].sum;
    }
    pushdown(now,lt,rt);
    long long mid=(lt+rt-1)/2;
    return query(tree[now].lc,lt,mid,l,r)+query(tree[now].rc,mid+1,rt,l,r);
}
//======================================
int main()
{
    scanf("%lld%lld",&n,&m);
    long long root = 1; //根结点编号
    cnt = 1; //总结点数量 
    for(long long i = 1; i <= n; i++)
    {
        long long x;
        scanf("%lld",&x);
        update(root, 1, n, i, i, x);
    }

    for(long long i = 1; i <= m; i++)
    {
        long long op, x, y, val;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op == 1)
        {
            scanf("%lld",&val);
            update(root, 1, n, x, y, val); 
        }
        else{
            printf("%lld\n",query(root,1,n,x,y));
        }
    }
    return 0;
}

平衡树

FHQ

const int MX=1e5+10;
struct Node{
    int l,r;
    int val,key;
    int size;
}fhq[MX];
int cnt,root;
inline int newnode(int val){
    fhq[++cnt].val=val;
    fhq[cnt].key=rand();
    fhq[cnt].size=1;
    return cnt;
}
inline void update(int now){
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void split(int now,int val,int &x,int &y){
    if(!now) x=y=0;
    else{
        if(fhq[now].val<=val){
            x=now;
            split(fhq[now].r,val,fhq[now].r,y);
        }
        else{
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);    //此处update位置不能写在下面，会合并根节点
    }
}

int merge(int x,int y){
    if(!x||!y)  return x+y;
    else{
        if(fhq[x].key<=fhq[y].key){
            fhq[x].r=merge(fhq[x].r,y);
            update(x);
            return x;
        }
        else{
            fhq[y].l=merge(x,fhq[y].l);
            update(y);
            return y;
        }
    }
}
int x,y,z;
inline void ins(int val){         //插入x数
    split(root,val,x,y);
    root=merge(merge(x,newnode(val)),y);
}
inline void del(int val){         //删除x数(若有多个相同的数,应只删除一个)
    split(root,val,x,z);
    split(x,val-1,x,y);
    y=merge(fhq[y].l,fhq[y].r);
    root=merge(merge(x,y),z);
}
inline int getrank(int val){      //查询x数的排名(排名定义为比当前数小的数的个数+1)
    split(root,val-1,x,y);
    int re=fhq[x].size+1;
    root=merge(x,y);
    return re;
}
inline int getnum(int rank){      //查询排名为x的数
    int now=root;
    while(now){
        if(fhq[fhq[now].l].size+1==rank)  break;
        else if(fhq[fhq[now].l].size>=rank){
            now=fhq[now].l;
        }
        else{
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    return fhq[now].val;
}
inline int pre(int val){          //求x的前驱(前驱定义为小于x,且最大的数)
    split(root,val-1,x,y);
    int now=x;
    while(fhq[now].r)  now=fhq[now].r;
    int re=fhq[now].val;
    root=merge(x,y);
    return re;
}
inline int nxt(int val){          //求x的后继(后继定义为大于x,且最小的数)
    split(root,val,x,y);
    int now=y;
    while(fhq[now].l)  now=fhq[now].l;
    int re=fhq[now].val;
    root=merge(x,y);
    return re;
}

二逼平衡树

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10, MAXM = 1e7;
const int INF = 0x7fffffff;

int input[MAXN] = {0};
int n, m;
struct Node
{
    int l, r;
    int key, val;
    int size;
} fhq[MAXM];
int cnt;
struct FHQ_Treap
{
    int root = 0;
    inline int newnode(int val)
    {
        fhq[++cnt].val = val;
        fhq[cnt].size = 1;
        fhq[cnt].key = (rand() << 10) + rand();
        return cnt;
    }
    inline void update(int now)
    {
        fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1;
    }
    void split(int now, int val, int &x, int &y)
    {
        if (!now)
            x = y = 0;
        else
        {
            if (fhq[now].val <= val)
            {
                x = now;
                split(fhq[now].r, val, fhq[now].r, y);
            }
            else
            {
                y = now;
                split(fhq[now].l, val, x, fhq[now].l);
            }
            update(now);
        }
    }
    int merge(int x, int y)
    {
        if (!x || !y)
            return x + y;
        else
        {
            if (fhq[x].key <= fhq[y].key)
            {
                fhq[x].r = merge(fhq[x].r, y);
                update(x);
                return x;
            }
            else
            {
                fhq[y].l = merge(x, fhq[y].l);
                update(y);
                return y;
            }
        }
    }
    int x, y, z;
    inline void Insert(int val)
    {
        split(root, val, x, y);
        root = merge(merge(x, newnode(val)), y);
    }
    inline void Delete(int val)
    {
        split(root, val, x, z);
        split(x, val - 1, x, y);
        y = merge(fhq[y].l, fhq[y].r);
        root = merge(merge(x, y), z);
    }
    inline void Build(int l, int r)
    {
        for (int i = l; i <= r; i++)
            Insert(input[i]);
    }
    inline int FindRank(int val)
    { // 查询x数的排名(排名定义为比当前数小的数的个数+1)
        split(root, val - 1, x, y);
        int re = fhq[x].size + 1;
        root = merge(x, y);
        return re;
    }
    inline int getnum(int rank)
    { // 查询排名为x的数
        int now = root;
        while (now)
        {
            if (fhq[fhq[now].l].size + 1 == rank)
                break;
            else if (fhq[fhq[now].l].size >= rank)
            {
                now = fhq[now].l;
            }
            else
            {
                rank -= fhq[fhq[now].l].size + 1;
                now = fhq[now].r;
            }
        }
        return fhq[now].val;
    }
    inline int Lower(int val)
    { // 求x的前驱(前驱定义为小于x,且最大的数)
        split(root, val - 1, x, y);
        int ans;
        if (fhq[x].size)
        {
            int now = x;
            while (fhq[now].r)
            {
                now = fhq[now].r;
            }
            ans = fhq[now].val;
        }
        else
            ans = -INF;
        root = merge(x, y);
        return ans;
    }
    inline int Upper(int val)
    { // 求x的后继(后继定义为大于x,且最小的数)
        split(root, val, x, y);
        int ans;
        if (fhq[y].size)
        {
            int now = y;
            while (fhq[now].l)
            {
                now = fhq[now].l;
            }
            ans = fhq[now].val;
        }
        else
            ans = INF;
        root = merge(x, y);
        return ans;
    }
} FT[MAXN << 2];
#define mid ((x + y) >> 1)
#define lson (pst << 1)
#define rson (pst << 1 | 1)

struct SegmentTree
{
    int root[MAXN << 2];

    inline void Build(int x, int y, int pst)
    {
        FT[pst].Build(x, y);
        if (x != y)
            Build(x, mid, lson), Build(mid + 1, y, rson);

        return;
    }

    inline int QueryRank(int x, int y, int pst, int l, int r, int key)
    {
        if (y < l || x > r)
            return 0;
        if (l <= x && y <= r)
            return FT[pst].FindRank(key) - 1;

        return QueryRank(x, mid, lson, l, r, key) + QueryRank(mid + 1, y, rson, l, r, key);
    }

    inline int QueryKey(int l, int r, int rak)
    {
        int x = 0, y = 1e8, ans = -1;
        while (x <= y)
        {
            if (QueryRank(1, n, 1, l, r, mid) + 1 <= rak)
                ans = mid, x = mid + 1;
            else
                y = mid - 1;
        }

        return ans;
    }

    inline void Update(int x, int y, int pst, int p, int k)
    {
        FT[pst].Delete(input[p]);
        FT[pst].Insert(k);

        if (x != y)
        {
            if (p <= mid)
                Update(x, mid, lson, p, k);
            else
                Update(mid + 1, y, rson, p, k);
        }

        return;
    }

    inline int Lower(int x, int y, int pst, int l, int r, int k)
    {
        if (y < l || x > r)
            return -INF;
        if (l <= x && y <= r)
            return FT[pst].Lower(k);
        return max(Lower(x, mid, lson, l, r, k), Lower(mid + 1, y, rson, l, r, k));
    }

    inline int Upper(int x, int y, int pst, int l, int r, int k)
    {
        if (y < l || x > r)
            return INF;
        if (l <= x && y <= r)
            return FT[pst].Upper(k);
        return min(Upper(x, mid, lson, l, r, k), Upper(mid + 1, y, rson, l, r, k));
    }

} ST;

signed main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", input + i);

    ST.Build(1, n, 1);

    for (int i = 1, opt, l, r, p, k; i <= m; i++)
    {
        scanf("%d", &opt);

        if (opt == 1)
        {
            scanf("%d %d %d", &l, &r, &k);
            printf("%d\n", ST.QueryRank(1, n, 1, l, r, k) + 1);
        }

        if (opt == 2)
        {
            scanf("%d %d %d", &l, &r, &k);
            printf("%d\n", ST.QueryKey(l, r, k));
        }

        if (opt == 3)
        {
            scanf("%d %d", &p, &k);
            ST.Update(1, n, 1, p, k);
            input[p] = k;
        }

        if (opt == 4)
        {
            scanf("%d %d %d", &l, &r, &k);
            printf("%d\n", ST.Lower(1, n, 1, l, r, k));
        }

        if (opt == 5)
        {
            scanf("%d %d %d", &l, &r, &k);
            printf("%d\n", ST.Upper(1, n, 1, l, r, k));
        }
    }
    return 0;
}

重链剖分/树链剖分

#include<bits/stdc++.h>
using namespace std;const int MX=1e5+10;
int n,m,r,p;int input[MX]={0};int siz[MX]={0};int fath[MX]={0};int top[MX]={0};int dfn[MX]={0};int son[MX]={0};int high[MX]={0};int w[MX]={0};
//线段树好闪，拜谢线段树
struct node{
    long long sum;
    long long lc,rc;
    long long lazy;
}tree[MX<<1];
long long cnt=1,root=1;
inline void update(long long now){
    tree[now].sum=tree[tree[now].lc].sum+tree[tree[now].rc].sum;
}
inline void addnode(long long &now,long long l,long long r,long long val){
    if(now==0)  now=++cnt;
    tree[now].sum+=((r-l+1)*val)%p;tree[now].sum%=p;
    tree[now].lazy+=val%p;tree[now].lazy%=p;
}
inline void pushdown(long long now,long long l,long long r){
    if(l>=r)  return;
    long long mid=(r+l-1)>>1;
    addnode(tree[now].lc,l,mid,tree[now].lazy);
    addnode(tree[now].rc,mid+1,r,tree[now].lazy);
    tree[now].lazy=0;
}
void add(long long now,long long lt,long long rt,long long l,long long r,long long val){
    if(lt>r||l>rt)  return;
    if(l<=lt&&rt<=r){
        addnode(now,lt,rt,val);
        return ;
    }
    long long mid=(rt+lt-1)>>1;pushdown(now,lt,rt);
    add(tree[now].lc,lt,mid,l,r,val);add(tree[now].rc,mid+1,rt,l,r,val);
    update(now);
    return ;
}
long long cy(long long now,long long lt,long long rt,long long l,long long r){
    if(lt>r||l>rt)  return 0;
    if(l<=lt&&rt<=r){
        return tree[now].sum;
    }
    long long mid=(rt+lt-1)>>1;pushdown(now,lt,rt);
    return (cy(tree[now].lc,lt,mid,l,r)+cy(tree[now].rc,mid+1,rt,l,r))%p;
}
void build_t(){
    for(int i=1;i<=n;i++){
        add(root,1,n,i,i,w[i]);
    }
}
/*
int siz[MX]={0};    大小
int fa[MX]={0};     父亲
int top[MX]={0};    重链开始的地方
int dfn[MX]={0};    DFS序
int son[MX]={0};   重儿子
int high[MX]={0};  高度
int w[MX]={0};     时间戳权值
*/
vector<int> vec[MX];
void dfs1(int now,int fa){//确定  大小，父亲，高度，重儿子
    siz[now]=1;fath[now]=fa;high[now]=high[fa]+1;
    int maxn=-0x3f3f3f3f;
    for(auto to:vec[now]){
        if(to==fa)  continue;
        dfs1(to,now);
        siz[now]+=siz[to];
        if(maxn<siz[to]){
            maxn=siz[to];
            son[now]=to;
        }
    }
}
int tim=0;
void dfs2(int now,int fa){//确定重链开头，时间戳，dfs序
    dfn[now]=++tim;
    top[now]=fa;
    w[tim]=input[now];
    if(!son[now])  return ;
    dfs2(son[now],fa);
    for(auto to:vec[now]){
        if(to==fath[now]||to==son[now])  continue;
        dfs2(to,to);
    }
}

int main(){
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(int i=1;i<=n;i++){
        scanf("%d",&input[i]);
    }
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        vec[x].push_back(y);vec[y].push_back(x);
    }
    dfs1(r,r);
    dfs2(r,r);
    build_t();
    for(int i=1;i<=m;i++){
        int op;scanf("%d",&op);
        if(op==1){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            z%=p;
            while(top[x]!=top[y]){
                if(high[top[x]]<high[top[y]]){
                    swap(x,y);
                }
                add(root,1,n,dfn[top[x]],dfn[x],z);
                x=fath[top[x]];
            }
            if(high[x]>high[y])  swap(x,y);
            add(root,1,n,dfn[x],dfn[y],z);
        }
        else if(op==2){
            int x,y;
            scanf("%d%d",&x,&y);
            int sum=0;
            while(top[x]!=top[y]){
                if(high[top[x]]<high[top[y]])  swap(x,y);
                sum=(sum+cy(root,1,n,dfn[top[x]],dfn[x]))%p;
                x=fath[top[x]];
            }
            if(high[x]>high[y])  swap(x,y);
            sum=(sum+cy(root,1,n,dfn[x],dfn[y]))%p;
            printf("%d\n",sum%p);
        }
        else if(op==3){
            int x,z;
            scanf("%d%d",&x,&z);
            add(root,1,n,dfn[x],dfn[x]+siz[x]-1,z);
        }
        else{
            int x;
            scanf("%d",&x);
            printf("%d\n",cy(root,1,n,dfn[x],dfn[x]+siz[x]-1));
        }
    }

    return 0;
}