【算法提高——第四讲】高级数据结构(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月前
|
机器学习/深度学习 人工智能 算法
【人工智能】线性回归模型:数据结构、算法详解与人工智能应用,附代码实现
线性回归是一种预测性建模技术,它研究的是因变量(目标)和自变量(特征)之间的关系。这种关系可以表示为一个线性方程,其中因变量是自变量的线性组合。
40 2
|
2月前
|
存储 算法 索引
算法与数据结构
算法与数据结构
37 8
|
2月前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
50 1
【数据结构】算法的复杂度
|
1月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
|
1月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
|
1月前
|
存储 缓存 算法
深入解析B树:数据结构、存储结构与算法优势
深入解析B树:数据结构、存储结构与算法优势
|
2月前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
26 1
|
2月前
|
存储 算法 调度
惊呆了!Python高级数据结构堆与优先队列,竟然能这样优化你的程序性能!
【7月更文挑战第10天】Python的heapq模块实现了堆和优先队列,提供heappush和heappop等函数,支持O(log n)时间复杂度的操作。优先队列常用于任务调度和图算法,优化性能。例如,Dijkstra算法利用最小堆加速路径查找。堆通过列表存储,内存效率高。示例展示了添加、弹出和自定义优先级元素。使用堆优化程序,提升效率。
45 2
|
2月前
|
存储 数据处理 开发者
告别繁琐查找!Python高级数据结构Trie树与Suffix Tree,让数据处理更轻松!
【7月更文挑战第19天】Python的Trie树优化字符串搜索,利用前缀减少无效操作,提升效率;Suffix Tree则高效处理后缀问题,尤其适用于文本搜索与生物信息学。虽构建复杂,但能加速后缀查询。掌握这两种数据结构,能有效应对大规模数据挑战,简化处理流程,提升开发效率。
70 0
|
2月前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
32 0