【算法提高——第四讲】高级数据结构(2)

简介: 【算法提高——第四讲】高级数据结构(2)

4.3 线段树

4.3.1 1275. 最大数

image.pngimage.png

代码:


#include<bits/stdc++.h>
using namespace std;
const int N=200010,INF=0x3f3f3f3f;
int m,p;
int n;
struct Node
{
    int l,r;
    int v;  // 区间[l, r]中的最大值
    Node(){}
    Node(int _l,int _r,int _v)
    {
        l=_l,r=_r,v=_v;
    }
}tr[4*N];
void pushup(int u)  // 由子节点的信息,来计算父节点的信息 u表示父节点编号
{
    tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r)   //u表示父节点编号,从u开始建立[l,r]的线段树
{
    tr[u]=Node(l,r,0);
    if(l==r) return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v; // 树中节点,已经被完全包含在[l, r]中了
    int mid=tr[u].l+tr[u].r>>1;
    int v=-INF;
    if(l<=mid) v=query(u<<1,l,r);
    if(r>mid) v=max(v,query(u<<1|1,l,r));
    return v;
}
void modify(int u,int x,int v) //单点修改,将u父节点编号,x是要修改的点,v是要修改为多少
{
    if(tr[u].l==x&&tr[u].r==x) tr[u].v=v;
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else  modify(u<<1|1,x,v);
        pushup(u);
    }
}
int main()
{
    cin>>m>>p;
    int num=0;
    build(1,1,m);
    while(m--)
    {
        string op;
        int x;
        cin>>op>>x;
        if(op=="Q")
        {
            num=query(1,n-x+1,n);
            cout<<num<<endl;
        }
        else
        {
            n++;
            modify(1,n,(num+x)%p);
        }
    }
    return 0;
}

4.3.2 245. 你能回答这些问题吗

image.png


代码:


#include<bits/stdc++.h>
using namespace std;
const int N=500010,INF=0x3f3f3f3f;
int n,m;
int w[N];
struct Node
{
    int l,r;
    int sum,tmax,lmax,rmax;
    Node(){}
    Node(int _l,int _r,int _sum,int _tmax,int _lmax,int _rmax)
    {
        l=_l,r=_r,sum=_sum,tmax=_tmax,lmax=_lmax,rmax=_rmax;
    }
}tr[N*4];
void pushup(Node &u,Node &l,Node &r)
{
    u.sum=l.sum+r.sum;
    u.lmax=max(l.lmax,l.sum+r.lmax);
    u.rmax=max(r.rmax,r.sum+l.rmax);
    u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
    if(l==r) tr[u]=Node(l,r,w[r],w[r],w[r],w[r]);
    else
    {
        tr[u]=Node(l,r,0,0,0,0);
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int x,int v)
{
    if(tr[u].l==x&&tr[u].r==x) tr[u]=Node(x,x,v,v,v,v);
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }
}
Node query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else
    {
        Node left=query(u<<1,l,r);
        Node right=query(u<<1|1,l,r);
        Node res;
        pushup(res,left,right);
        return res;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    build(1,1,n);
    while(m--)
    {
        int k,x,y;
        cin>>k>>x>>y;
        if(k==1)
        {
            if(x>y) swap(x,y);
            cout<<query(1,x,y).tmax<<endl;
        }
        else modify(1,x,y);
    }
    return 0;
}

4.3.3 246. 区间最大公约数

image.png


代码:


#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;
int n,m;
LL w[N];
struct Node
{
    int l,r;
    LL sum,d;
    Node(){}
    Node(int _l,int _r,LL _sum,LL _d)
    {
        l=_l,r=_r,sum=_sum,d=_d;
    }
}tr[N*4];
LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}
void pushup(Node &u,Node &l,Node &r)
{
    u.sum=l.sum+r.sum;
    u.d=gcd(l.d,r.d);
}
void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        LL b=w[r]-w[r-1];
        tr[u]=Node(l,r,b,b);
    }
    else
    {
        tr[u].l=l,tr[u].r=r;
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int x,LL v)
{
    if(tr[u].l==x&&tr[u].r==x)
    {
        LL b=tr[u].sum+v;
        tr[u]=Node(x,x,b,b);
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }
}
Node query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
    //注意三种情况
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid) return query(u<<1,l,r);
    else if(l>mid) return query(u<<1|1,l,r);
    else
    {
        Node left=query(u<<1,l,r);
        Node right=query(u<<1|1,l,r);
        Node res;
        pushup(res,left,right);
        return res;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    string op;
    int l,r;
    LL d;
    while(m--)
    {
        cin>>op>>l>>r;
        if(op=="Q")
        {
            Node left=query(1,1,l);
            Node right=Node(0,0,0,0);
            if(l+1<=r) right=query(1,l+1,r);
            cout<<abs(gcd(left.sum,right.d))<<endl;
        }
        else
        {
            cin>>d;
            modify(1,l,d);
            if(r+1<=n) modify(1,r+1,-d);
        }
    }
    return 0;
}

4.3.4 243. 一个简单的整数问题2

image.png


代码:


#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;
int n,m;
int w[N];
struct Node
{
    int l,r;
    LL sum,add;
    Node(){}
    Node(int _l,int _r,LL _sum,LL _add)
    {
        l=_l,r=_r,sum=_sum,add=_add;
    }
}tr[N*4];
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)
{
    Node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(root.add)
    {
        left.add+=root.add,left.sum+=(LL)(left.r-left.l+1)*root.add;
        right.add+=root.add,right.sum+=(LL)(right.r-right.l+1)*root.add;
        root.add=0;
    }
}
void build(int u,int l,int r)
{
    if(l==r) tr[u]=Node(l,r,w[r],0);
    else
    {
        tr[u]=Node(l,r,0,0);
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int d)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;
    }
    else // 一定要分裂
    {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,d);
        if(r>mid) modify(u<<1|1,l,r,d);
        pushup(u);
    }
}
LL query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    LL sum=0;
    if(l<=mid) sum+=query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);
    return sum;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    string op;
    int l,r,d;
    while(m--)
    {
        cin>>op>>l>>r;
        if(op=="C")
        {
            cin>>d;
            modify(1,l,r,d);
        }
        else
            cout<<query(1,l,r)<<endl;
    }
    return 0;
}

4.3.5 247. 亚特兰蒂斯

image.pngimage.png

代码:


#include<bits/stdc++.h>
using namespace std;
const int N=10010;
typedef pair<double,double> PII;
int n;
struct Segment
{
    double x,y1,y2;
    int k;
    Segment(){}
    Segment(double _x,double _y1,double _y2,int _k)
    {
        x=_x,y1=_y1,y2=_y2,k=_k;
    }
    bool operator < (const Segment &t) const
    {
        return x<t.x;
    }
}seg[N*2];
struct Node
{
    int l,r;
    int cnt;
    double len;
    Node(){}
    Node(int _l,int _r,int _cnt,double _len)
    {
        l=_l,r=_r,cnt=_cnt,len=_len;
    }
}tr[N*2*4];
vector<double> ys;
int find_y(double y)
{
    return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
}
void pushup(int u)
{
    if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];
    else if(tr[u].l!=tr[u].r)
    {
        tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
    }
    else tr[u].len=0;
}
void build(int u,int l,int r)
{
    tr[u]=Node(l,r,0,0);
    if(l!=r)
    {
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    }
}
void modify(int u,int l,int r,int k)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        tr[u].cnt+=k;
        pushup(u);
    }
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,k);
        if(r>mid) modify(u<<1|1,l,r,k);
        pushup(u);
    }
}
int main()
{
    int T=1;
    while(true)
    {
        cin>>n;
        if(n==0) break;
        ys.clear();
        for(int i=0,j=0;i<n;i++)
        {
            double x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            seg[j++]=Segment(x1,y1,y2,1);
            seg[j++]=Segment(x2,y1,y2,-1);
            ys.push_back(y1),ys.push_back(y2);
        }
        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin(),ys.end()),ys.end());
        build(1,0,ys.size()-2);
        sort(seg,seg+n*2);
        double res=0;
        for(int i=0;i<n*2;i++)
        {
            if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);
            modify(1,find_y(seg[i].y1),find_y(seg[i].y2)-1,seg[i].k);
        }
        printf("Test case #%d\n",T++);
        printf("Total explored area: %.2f\n\n",res);
    }
    return 0;
}

4.3.6 1277. 维护序列

image.png

image.png

代码:


#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;
int n,p,m;
int w[N];
struct Node
{
    int l,r;
    int sum,add,mul;
    Node(){}
    Node(int _l,int _r,int _sum,int _add,int _mul)
    {
        l=_l,r=_r,sum=_sum,add=_add,mul=_mul;
    }
}tr[N*4];
void pushup(int u)
{
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
void eval(Node &t,int add,int mul)
{
    t.sum=((LL)t.sum*mul+(LL)(t.r-t.l+1)*add)%p;
    t.mul=(LL)t.mul*mul%p;
    t.add=((LL)t.add*mul+add)%p;
}
void pushdown(int u)
{
    eval(tr[u<<1],tr[u].add,tr[u].mul);
    eval(tr[u<<1|1],tr[u].add,tr[u].mul);
    tr[u].add=0,tr[u].mul=1;
}
void build(int u,int l,int r)
{
    if(l==r) tr[u]=Node(l,r,w[r],0,1);
    else
    {
        tr[u]=Node(l,r,0,0,1);
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int add,int mul)
{
    if(tr[u].l>=l&&tr[u].r<=r) eval(tr[u],add,mul);
    else
    {
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,add,mul);
        if(r>mid) modify(u<<1|1,l,r,add,mul);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=mid) sum=query(u<<1,l,r);
    if(r>mid) sum=(sum+query(u<<1|1,l,r))%p;
    return sum;
}
int main()
{
    cin>>n>>p;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    cin>>m;
    while(m--)
    {
        int t,l,r,d;
        cin>>t>>l>>r;
        if(t==1)
        {
            cin>>d;
            modify(1,l,r,0,d);
        }
        else if(t==2)
        {
            cin>>d;
            modify(1,l,r,d,1);
        }
        else
            cout<<query(1,l,r)<<endl;
    }
    return 0;
}

4.4 可持久化数据结构

4.4.1 256. 最大异或和

image.png


代码:


#include<bits/stdc++.h>
using namespace std;
const int N=600010,M=N*25;
int n,m;
int s[N];
int tr[M][2],max_id[M];
int root[N],idx;
void my_insert(int i,int k,int p,int q)
{
    if(k<0)
    {
        max_id[q]=i;
        return;
    }
    int v=s[i]>>k&1;
    if(p) tr[q][v^1]=tr[p][v^1];
    tr[q][v]=++idx;
    my_insert(i,k-1,tr[p][v],tr[q][v]);
    max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);
}
int query(int root,int C,int L)
{
    int p=root;
    for(int i=23;i>=0;i--)
    {
        int v=C>>i&1;
        if(max_id[tr[p][v^1]]>=L) p=tr[p][v^1];
        else p=tr[p][v];
    }
    return C^s[max_id[p]];
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    max_id[0]=-1;
    root[0]=++idx;
    my_insert(0,23,0,root[0]);
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        s[i]=s[i-1]^x;
        root[i]=++idx;
        my_insert(i,23,root[i-1],root[i]);
    }
    string op;
    int l,r,x;
    while(m--)
    {
        cin>>op;
        if(op=="A")
        {
            cin>>x;
            n++;
            s[n]=s[n-1]^x;
            root[n]=++idx;
            my_insert(n,23,root[n-1],root[n]);
        }
        else
        {
            cin>>l>>r>>x;
            cout<<query(root[r-1],s[n]^x,l-1)<<endl;
        }
    }
    return 0;
}

4.4.2 255. 第K小数

image.png


代码:


#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=10010;
int n,m;
int a[N];
vector<int> nums;
struct Node
{
    int l,r;
    int cnt;
}tr[N*4+N*17];
int root[N],idx;
int find_x(int x)
{
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
int build(int l,int r)
{
    int p=++idx;
    if(l==r) return p;
    int mid=l+r>>1;
    tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
    return p;
}
int my_insert(int p,int l,int r,int x)
{
    int q=++idx;
    tr[q]=tr[p];
    if(l==r)
    {
        tr[q].cnt++;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid) tr[q].l=my_insert(tr[p].l,l,mid,x);
    else tr[q].r=my_insert(tr[p].r,mid+1,r,x);
    tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;
    return q;
}
int query(int q,int p,int l,int r,int k)
{
    if(l==r) return r;
    int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;
    int mid=l+r>>1;
    if(k<=cnt) return query(tr[q].l,tr[p].l,l,mid,k);
    else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    root[0]=build(0,nums.size()-1);
    for(int i=1;i<=n;i++)
        root[i]=my_insert(root[i-1],0,nums.size()-1,find_x(a[i]));
    while(m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<nums[query(root[r],root[l-1],0,nums.size()-1,k)]<<endl;
    }
    return 0;
}
相关文章
|
3月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
196 6
|
4月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
126 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
16天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
79 29
|
16天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
|
16天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
|
2月前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
70 20
|
3月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
3月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
146 23
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1

热门文章

最新文章