洛谷官方题单--线段树-6ren

洛谷官方题单--线段树

转载作者：撒哈拉更新时间：2024-06-19 23:03:22

57

4

前言

发现线段树根本不会写，所以想要完成洛谷官方题单来稍微提升一下... 持续更新ing 。

[========] 。

P3870 [TJOI2009] 开关明确了写线段树要思考的几个点 1.如何update，即如何合并子节点的信息，这里就是直接将子节点的灯的数量相加即可 2.如何modify，即如何根据tag修改该节点的值，这里就是节点长度-灯的数量就行还有如何下传tag，这里直接^就行。

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<assert.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

const int N=1e5+10;
struct Node{
    int add;
    int x;
}seg[N*4];

Node operator+(const Node& a,const Node& b){
    Node c;
    c.x=a.x+b.x;
    return c;
}

void settag(int u,int l,int r,int add){
    if(add==1){
        int len=r-l+1;
        seg[u].x=len-seg[u].x;
        seg[u].add^=add;
    }
}

void pushdown(int u,int l,int r){
    int mid=l+r>>1;
    settag(u*2,l,mid,seg[u].add);
    settag(u*2+1,mid+1,r,seg[u].add);
    seg[u].add=0;
}

void update(int u){
    seg[u].x=seg[u*2].x+seg[u*2+1].x;
}

void modify(int u,int l,int r,int ql,int qr,int add){
    assert(l<=ql and qr<=r);
    if(l==ql and r==qr)settag(u,l,r,add);
    else{
        pushdown(u,l,r);
        int mid=l+r>>1;
        if(qr<=mid)modify(u*2,l,mid,ql,qr,add);
        else if(ql>=mid+1)modify(u*2+1,mid+1,r,ql,qr,add);
        else{
            modify(u*2,l,mid,ql,mid,add);
            modify(u*2+1,mid+1,r,mid+1,qr,add);
        }
        update(u);
    }
}

Node query(int u,int l,int r,int ql,int qr){
    assert(l<=ql and qr<=r);
    if(l==ql and r==qr)return seg[u];
    else{
        pushdown(u,l,r);
        int mid=l+r>>1;
        if(qr<=mid)return query(u*2,l,mid,ql,qr);
        else if(ql>=mid+1)return query(u*2+1,mid+1,r,ql,qr);
        else{
            auto L=query(u*2,l,mid,ql,mid);
            auto R=query(u*2+1,mid+1,r,mid+1,qr);
            Node res=L+R;
            return res;
        }
        update(u);
    }
}

void solve(){
    int n,m;
    cin>>n>>m;

    while(m--){
        int c,a,b;
        cin>>c>>a>>b;
        if(c==0){
            modify(1,1,n,a,b,1);
        }else{
            cout<<query(1,1,n,a,b).x<<endl;
        }
    }
}

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

[========] 。

P1438 无聊的数列区间加等差数列，单点求和直接转化为差分，区间加就行用树状数组也能做。

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<assert.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

const int N=1e5+10;
LL a[N],b[N];
struct Node{
    LL add;
    LL x;
}seg[N*4];

void update(int u){
    seg[u].x=seg[u*2].x+seg[u*2+1].x;
}

void build(int u,int l,int r){
    assert(l<=r);
    if(l==r)seg[u].x=b[l];
    else{
        int mid=l+r>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        update(u);
    }
}

void settag(int u,int l,int r,LL add){
    int len=r-l+1;
    seg[u].x+=len*add;
    seg[u].add+=add;    
}

void pushdown(int u,int l,int r){
    int mid=l+r>>1;
    settag(u*2,l,mid,seg[u].add);
    settag(u*2+1,mid+1,r,seg[u].add);
    seg[u].add=0;
}

void modify(int u,int l,int r,int ql,int qr,LL add){
    assert(l<=ql and qr<=r);
    if(l==ql and r==qr)settag(u,l,r,add);
    else{
        pushdown(u,l,r);
        int mid=l+r>>1;
        if(qr<=mid)modify(u*2,l,mid,ql,qr,add);
        else if(ql>=mid+1)modify(u*2+1,mid+1,r,ql,qr,add);
        else{
            modify(u*2,l,mid,ql,mid,add);
            modify(u*2+1,mid+1,r,mid+1,qr,add);
        }
        update(u);
    }
}

Node query(int u,int l,int r,int ql,int qr){
    assert(l<=ql and qr<=r);
    if(l==ql and r==qr)return seg[u];
    else{
        pushdown(u,l,r);
        int mid=l+r>>1;
        if(qr<=mid)return query(u*2,l,mid,ql,qr);
        else if(ql>=mid+1)return query(u*2+1,mid+1,r,ql,qr);
        else{
            Node res;
            auto L=query(u*2,l,mid,ql,mid);
            auto R=query(u*2+1,mid+1,r,mid+1,qr);
            res.x=L.x+R.x;
            return res;
        }
        update(u);
    }
}

void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    build(1,1,n);

    while(m--){
        int op;cin>>op;
        if(op==1){
            LL l,r,k,d;
            cin>>l>>r>>k>>d;
            modify(1,1,n,l,l,k);
            if(l+1<=r)modify(1,1,n,l+1,r,d);
            if(r+1<=n)modify(1,1,n,r+1,r+1,-(k+(r-l)*d));
        }else{
            int p;cin>>p;
            cout<<query(1,1,n,1,p).x<<endl;
        }
    }  
}

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

最后此篇关于洛谷官方题单--线段树的文章就讲到这里了,如果你想了解更多关于洛谷官方题单--线段树的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

57

4

0

文章推荐： CSS属性计算

文章推荐： PhantomReference和WeakReference究竟有何不同

文章推荐：将强化学习重新引入RLHF

文章推荐： javadatetime数据类型去掉时分秒

树结构之MongoDb 使用的到底是 B 树，还是 B+ 树？
关于 B 树与 B+ 树，网上有一个比较经典的问题：为什么 MongoDb 使用 B 树，而 MySQL 索引使用 B+ 树? 但实际上 MongoDb 真的用的是 B 树吗?
c# - 持久(基于磁盘)R 树(或 R* 树)
如何将 R* Tree 实现为持久(基于磁盘)树？保存 R* 树索引或保存叶值的文件的体系结构是什么？注意:此外，如何在这种持久性 R* 树中执行插入、更新和删除操作？注意事项二:我已经实现了一个
java - 给定另一个 AST 树，在 Java 中创建一个 AST 树
目前，我正在努力用 Java 表示我用 SML 编写的 AST 树，这样我就可以随时用 Java 遍历它。我想知道是否应该在 Java 中创建一个 Node 类，其中包含我想要表示的数据，以及一个数
c++ - C++ 中任何好的范围查询库(使用 K-D 树、四叉树或 R 树)
我之前用过这个库http://www.cs.umd.edu/~mount/ANN/ .但是，它们不提供范围查询实现。我猜是否有一个 C++ 范围查询实现(圆形或矩形)，用于查询二维数据。谢谢。最佳
为什么MySQL数据库索引选择使用B+树?
在进一步分析为什么MySQL数据库索引选择使用B+树之前，我相信很多小伙伴对数据结构中的树还是有些许模糊的，因此我们由浅入深一步步探讨树的演进过程，在一步步引出B树以及为什么MySQL数据库索引选择
操作系统的那棵“树”---06
操作系统的那棵“树” 今天从一颗开始，我们看看如何从小树苗长成一颗苍天大树。运转CPU CPU运转起来很简单，就是不断的从内存取值执行。 CPU没有好好运转 IO是个耗费时间的活，如果CPU在取值
r - 从物种列表制作简单的系统发育树状图(树)
我想为海洋生物学类(class)制作一个简单的系统发育树作为教育示例。我有一个具有分类等级的物种列表: Group <- c("Benthos","Benthos","Benthos","Be
c++ - 树，无法正确删除节点
我从这段代码中删除节点时遇到问题，如果我插入数字 12 并尝试删除它，它不会删除它，我尝试调试，似乎当它尝试删除时，它出错了树的。但是，如果我尝试删除它已经插入主节点的节点，它将删除它，或者我插入数字
haskell - 如何在Haskell中实现B+树？
B+ 树的叶节点链接在一起。将 B+ 树的指针结构视为有向图，它不是循环的。但是忽略指针的方向并将其视为链接在一起的无向叶节点会在图中创建循环。在 Haskell 中，如何将叶子构造为父内部节点的子
GWT 树，开幕事件
我在 GWT 中使用树控件。我有一个自定义小部件，我将其添加为 TreeItem: Tree testTree = new Tree(); testTree.addItem(myWidget); 我想
c - 树/链表结构的遍历
它有点像混合树/链表结构。这是我定义结构的方式 struct node { nodeP sibling; nodeP child; nodeP parent; char
c - 树:使用队列进行层序遍历
我编写了使用队列遍历树的代码，但是下面的出队函数生成错误，head = p->next 是否有问题？我不明白为什么这部分是错误的。 void Levelorder(void) { node *tmp,
javascript - 将平面数组解析为嵌套结构(树)
例如，我想解析以下数组: var array1 = ["a.b.c.d", "a.e.f.g", "a.h", "a.i.j", "a.b.k"] 进入: var json1 = { "nod
java - 树-路径总和
问题 -> 给定一棵二叉树和一个和，确定该树是否具有从根到叶的路径，使得沿路径的所有值相加等于给定的和。我的解决方案 -> public class Solution { public bo
带有列的 Java 树
我有一个创建 java 树的任务，它包含三列:运动名称、运动类别中的运动计数和上次更新。类似的东西显示在下面的图像上: 如您所见，有 4 种运动:水上运动、球类运动、跳伞运动和舞蹈运动。当我展开 sk
mysql - H2数据库中的B+树
我想在 H2 数据库中实现 B+ Tree，但我想知道，B+ Tree 功能在 H2 数据库中可用吗？最佳答案 H2 已经使用了 B+ 树(PageBtree 类)。关于mysql - H2数据库
java - 字符串数组(树)
假设我们有 5 个字符串数组: String[] array1 = {"hello", "i", "cat"}; String[] array2 = {"hello", "i", "am"}; Str
每个节点具有恒定时间的 C++ 树
我正在处理树。每个节点都有带有 Tree * 值的对象。我读取的数据如下所示: 1 2 2 ... 这意味着，将 1 作为 0 的子节点，将 2 作为 1 的子节点，将 3 作为 o 2 的子节点。在
JavaScript 树/树网格库
我正在寻找一个好的 JavaScript 树/树网格包。现在——在你回答之前: 它需要能够在大量节点上正常运行。可能有 1,000 个兄弟节点。它需要能够在 2 或 3 秒内绘制到 1,000 个节点
c++ - 这个代码块到底是如何工作的[树]？
下面的代码块究竟是如何工作的？更具体地说，程序如何知道返回哪个选项？ return ancestor (node1->left(), node2) || ancestor

首页

博学

6Ren·AI

商城

洛谷官方题单--线段树

前言