【算法提高——第四讲】高级数据结构(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;
}
相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
25 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
1月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
32 4
|
1月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
20 0
数据结构与算法学习十四:常用排序算法总结和对比
|
1月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
29 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
1月前
|
机器学习/深度学习 存储 算法
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
|
2月前
|
机器学习/深度学习 算法 Java
[算法与数据结构] 谈谈线性查找法~
该文章详细介绍了线性查找法的基本概念与实现方法,通过Java代码示例解释了如何在一个数组中查找特定元素,并分析了该算法的时间复杂度。
|
1月前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
1月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
20 0
|
1月前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
16 0