线段树题单

这篇具有很好参考价值的文章主要介绍了线段树题单。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 离散化+预处理+ min线段树

https://www.luogu.com.cn/problem/CF522D

题意:

给一个 n 个元素的数组 a ,m 次询问,每次询问区间 [ l , r ] 内 数值相等的两个数的最近距离,不存在则输出 -1

思路:

先用 set 和 map 对 a 数组离散化处理,对离散出来的每个点,记录 pos [ i ] 表示数字 i 上一次出现的位置,ans [ i ] 表示 第 i 个数字 离上一个相同位置的距离,nxt [ i ] 表示下一个和第 i 个数字相同的位置

这样就把询问转化为 查询区间 [ l , r ] 内满足 i - ans[ i ] >= l 的最小ans[i],即上一个相同位置也在区间内的最小ans,这里用 min线段树 实现区间最小值查询

然后离线下来每次询问,把所有询问按左端点排序,然后再遍历询问,保证了每次查询的左端点递增,这样 小于 当前询问 l 的数值一定不会在后面的区间里出现,用一个 l 指针维护再也不会查询到的点,每次将 经过的 l 的下一个相同数字处 ans [ nxt [ i ] ] 赋值 INF,表示上一个相同的点不会访问到,这样便可转换为单纯的区间查询,复杂度为(n+q)log(n)

代码:

#include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout<<#x<<" = "<<x<<endl
using namespace std;

#define int long long

typedef long long ll;
typedef pair<int,int> pii;

const int FINF=INT_MIN;
const int INF=INT_MAX;

const int N=5e5+5;

struct node{
    int mn;
    int l,r;
    #define mid ((l+r)>>1)
    #define ls (p<<1)
    #define rs ((p<<1)|1)
}seg[4*N];

int a[N],n,m,ans[N],pos[N],nxt[N];

void build(int p,int l,int r){
    seg[p].l=l,seg[p].r=r;
    if(l==r){
        seg[p].mn=ans[l];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    seg[p].mn=min(seg[ls].mn,seg[rs].mn);
}

void update(int p,int x,int y){
    if(x==0)return;
    int l=seg[p].l,r=seg[p].r;
    if(l==r){
        seg[p].mn=y;
        return;
    }
    if(x<=mid)update(ls,x,y);
    else update(rs,x,y);
    seg[p].mn=min(seg[ls].mn,seg[rs].mn);
}

int query(int p,int x,int y){
    int l=seg[p].l,r=seg[p].r;
    if(x<=l&&y>=r){
        int ans=seg[p].mn;
        return ans;
    }
    int ans=INT_MAX;
    if(x<=mid)ans=min(ans,query(ls,x,y));
    if(y>mid)ans=min(ans,query(rs,x,y));
    return ans;
}

struct Node{
    int x,y,id;
    bool operator <(const Node aa)const {
        return x<aa.x;
    }
}qq[N];

void solve(){

    cin>>n>>m;
    set<int>ss;
    map<int,int>mm;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ss.insert(a[i]);
    }
    int cnt=0;
    for(auto i:ss){
        mm[i]=++cnt;
    }
    for(int i=1;i<=n;i++)a[i]=mm[a[i]];


    for(int i=1;i<=n;i++){
        int val=a[i];
        if(!pos[val])ans[i]=INT_MAX;
        else ans[i]=i-pos[val],nxt[pos[val]]=i;
        pos[val]=i;
    }

    build(1,1,n);

    for(int i=1;i<=m;i++){
        cin>>qq[i].x>>qq[i].y;
        qq[i].id=i;
    }
    sort(qq+1,qq+m+1);

    int l=1;
    for(int i=1;i<=m;i++){
        int ll=qq[i].x,rr=qq[i].y;
        while(l<ll){
            if(nxt[l]==0){
                l++;
                continue;
            }
            update(1,nxt[l],INT_MAX);
            l++;
        }
        ans[qq[i].id]=query(1,ll,rr);
    }
    for(int i=1;i<=m;i++){
        if(ans[i]==INT_MAX)ans[i]=-1;
        cout<<ans[i]<<endl;
    }

    return;
}


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T=1;
   // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

2. 线段树维护 线段并

https://ac.nowcoder.com/acm/contest/26896/1005

题意:

有m次操作,每次插入或删除一个线段,或输出 当前所有线段并 的长度

思路:

用一个集合维护当前线段是否存在,线段树维护每个点(小线段)上覆盖的线段个数,每次查询区间 1-n 上被覆盖的点的个数即可

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;

const int N=1e5+5;
struct node{
    int l,r,flag;
    #define ls (p<<1)
    #define rs ((p<<1)|1)
    #define mid ((l+r)>>1)
}seg[4*N];
void build(int p,int l,int r){
    seg[p].l=l,seg[p].r=r;
    seg[p].flag=0;
    if(l==r)return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}

void add(int p,int x,int y,int k){
    int l=seg[p].l,r=seg[p].r;
    if(x<=l&&y>=r){
        seg[p].flag+=k;
        return;
    }
    if(x<=mid)add(ls,x,y,k);
    if(y>mid)add(rs,x,y,k);
}

int query(int p,int x,int y){
    int l=seg[p].l,r=seg[p].r;
    if(seg[p].flag){
        return r-l+1;
    }
    if(l==r)return 0;
    int ans=0;
    if(x<=mid)ans+=query(ls,x,y);
    if(y>mid)ans+=query(rs,x,y);
    return ans;
}

void solve(){
    int n,m;
    cin>>m>>n;
    build(1,1,n);
    map<pii,int>mp;
    while(m--){
        int u,v,op;
        cin>>op>>u>>v;
        if(op==1){
            if(mp.find(make_pair(u,v))!=mp.end()){
                if(mp[make_pair(u,v)]!=0)continue;
            }
            mp[make_pair(u,v)]=1;
            add(1,u,v,1);
        }
        else if(op==2){
            if(mp.find(make_pair(u,v))==mp.end())continue;
            if(mp[make_pair(u,v)]==0)continue;
            mp[make_pair(u,v)]=0;
            add(1,u,v,-1);
        }
        else cout<<query(1,1,n)<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

3. 线段树维护等差数列

https://ac.nowcoder.com/acm/contest/26896/1010

题意:

有一个数组 a[N] ,有两个操作,操作1 为 将区间 [ l , r ] 替换成 以 k 为首项,1为公差的等差数列,操作2 为输出区间和

思路:

线段树维护 区间和,打 lazy 标记,表示这一端被替换成了 k 为首项的等差数列

每次 pushdown 的时候,通过区间长度计算出 子区间的首项

update 的时候,通过 l 和 x 的差值 计算出当前被更改节点 的首项,通过等差数列求和公式直接替换 sum 即可文章来源地址https://www.toymoban.com/news/detail-605109.html

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;

const int N=2e5+5;
int a[N];
struct node{
    int l,r;
    int lazy,sum;
    #define ls (p<<1)
    #define rs ((p<<1)|1)
    #define mid ((l+r)>>1)
}seg[4*N];
void build(int p,int l,int r){
    seg[p].l=l,seg[p].r=r;
    seg[p].lazy=0;
    if(l==r){
        seg[p].sum=a[l];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    seg[p].sum=seg[ls].sum+seg[rs].sum;
}
void pd(int p){
    int l=seg[p].l,r=seg[p].r;
    int lazy=seg[p].lazy;
    if(lazy==0)return;
    if(l==r){
        seg[p].lazy=0;
        return;
    }
    int len1=mid-l+1,len2=r-(mid+1)+1;
    seg[ls].lazy=lazy;
    seg[rs].lazy=lazy+len1;
    seg[ls].sum=(lazy+lazy+len1-1)*len1/2;
    seg[rs].sum=(lazy+len1+lazy+len1+len2-1)*len2/2;
    seg[p].lazy=0;
}
void upd(int p,int x,int y,int k){
    int l=seg[p].l,r=seg[p].r;
    pd(p);
    int len=r-l+1;
    if(x<=l&&y>=r){
        seg[p].lazy=k+l-x;
        seg[p].sum=(k+l-x+k+l-x+len-1)*len/2;
        return;
    }
    if(x<=mid)upd(ls,x,y,k);
    if(y>mid)upd(rs,x,y,k);
    seg[p].sum=seg[ls].sum+seg[rs].sum;
}

int query(int p,int x,int y){
    int l=seg[p].l,r=seg[p].r;
    pd(p);
    if(x<=l&&y>=r){
        return seg[p].sum;
    }
    int ans=0;
    if(x<=mid)ans+=query(ls,x,y);
    if(y>mid)ans+=query(rs,x,y);
    return ans;
}

void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(m--){
        int op,x,y,k;
        cin>>op>>x>>y;
        if(op==1){
            cin>>k;
            upd(1,x,y,k);
        }
        else{
            cout<<query(1,x,y)<<endl;
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

到了这里,关于线段树题单的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 洛谷题单算法1-1模拟与高精度

    发文章只是为了督促自己做题,双非大二刚转科班的菜菜一枚,代码仅供参考,不足之处望理解。         这题太恶心了,看完题解发现三种情况没有考虑,后来给补上了,我的 if-else 思路可能写的不太好,但是能过         注意结构体在函数中的传参(下学期c语言II要好

    2024年02月19日
    浏览(44)
  • 洛谷题单--算法[2-1] 前缀和、差分与离散化

    目录 0.铺垫学习:p1115最大子段和--前缀和+贪心+DP 1.p1719最大加权矩形--前缀和+贪心+DP+矩阵压缩 原题链接: P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 原题: 题目描述 给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。 输入格式 第

    2024年02月22日
    浏览(37)
  • 【算法】单调栈题单(矩阵系列、字典序最小、贡献法)⭐

    https://leetcode.cn/problems/beautiful-towers-ii/solutions/2456562/qian-hou-zhui-fen-jie-dan-diao-zhan-pyth-1exe/ https://leetcode.cn/problems/next-greater-element-i/description/ 提示: 1 = nums1.length = nums2.length = 1000 0 = nums1[i], nums2[i] = 10^4 nums1和nums2中所有整数 互不相同 nums1 中的所有整数同样出现在 nums2 中 进阶: 你

    2024年02月03日
    浏览(42)
  • 【算法】树状数组和线段树

    O ( l o g n ) O(logn) O ( l o g n ) :单点修改、区间查询 与前缀和的区别: 前缀和是离线的,每次动态修改原数组某个元素,都需要重新求一遍前缀和,因此单点修改是 O ( n ) O(n) O ( n ) 的,区间查询则是 O ( 1 ) O(1) O ( 1 ) 树状数组是在线的,单点修改和区间查询都是 O ( l o g n ) O(

    2024年02月19日
    浏览(46)
  • Segment Tree 线段树算法(java)

    什么是线段树算法: 线段树(Segment Tree)是一种基于树结构的数据结构,用于解决区间查询问题,例如区间最大值、最小值、区间和等。线段树是一种高度平衡的二叉树,每个节点都代表了一个区间。下面我们来详细了解一下线段树算法。 线段树的构建 线段树的构建过程可

    2024年02月16日
    浏览(40)
  • 算法41:掉落的方块(力扣699题)----线段树

    题目: https://leetcode.cn/problems/falling-squares/description/ 在二维平面上的 x 轴上,放置着一些方块。 给你一个二维整数数组  positions  ,其中  positions[i] = [lefti, sideLengthi]  表示:第  i  个方块边长为  sideLengthi  ,其左侧边与 x 轴上坐标点  lefti  对齐。 每个方块都从一个比目

    2024年02月22日
    浏览(42)
  • 华为OD机试 - 最少数量线段覆盖| 机试题算法思路 【2023】

    华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 - 自动曝光(Python) | 机试题算法

    2023年04月25日
    浏览(41)
  • 【算法每日一练]-结构优化(保姆级教程 篇4 树状数组,线段树,分块模板篇)

    目录 分块 分块算法步骤: 树状数组 树状数组步骤: 线段树点更新 点更新步骤: 线段树区间更新 区间更新步骤: 不同于倍增和前缀和与差分序列。 前缀和处理不更新的区间和 差分处理离线的区间更新问题 倍增处理离线的区间最值问题 分块,树状数组,线段树: 分块处

    2024年02月04日
    浏览(43)
  • 【题单】一个动态更新的洛谷综合题单

    洛谷试炼场的题目确实很具有代表性,但是近几年以来,又有许多经典题目出现在 OI 界中,这个大题单就是作为洛谷试炼场的扩展和补充。 目录 新版本食用指南 更新日志 题单 Part 0 试机题 Part 1 入门阶段 Part 2 基础算法 Part 3 搜索 Part 4 动态规划 Part 4.1-4.4 动态规划 Part 4.5-

    2024年02月19日
    浏览(34)
  • 最近的题单 【C++】

    描述:给定两个只包含小写字母的字符串,计算两个字符串的最大公共子串的长度。 注:子串的定义指一个字符串删掉其部分前缀和后缀(也可以不删)后形成的字符串。 数据范围:字符串长度:1le sle 1501≤s≤150  进阶:时间复杂度:O(n^3)O(n3) ,空间复杂度:O(n)O(n) 

    2023年04月18日
    浏览(29)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包