首页 > 其他分享 >线段树

线段树

时间：2024-05-24 23:28:55浏览次数：19  
标签：tag1 tag2 int 线段 tr rc lc

P3372 【模板】线段树 1

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define lc p<<1         ////p*2
#define rc p<<1|1       ////p*2+1
const int N=100005;
typedef struct node{
    int l,r,sum,tag;
}node;
node tr[4*N];
int arr[N];
int n,q;
void build(int p,int l,int r){
    tr[p]={l,r,arr[l],0};
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void pushup(int p){         ////孩子区间向父区间更新
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int p){      ////父区间向孩子区间更新
    if(tr[p].tag){
        tr[lc].sum+=tr[p].tag*(tr[lc].r-tr[lc].l+1);
        tr[rc].sum+=tr[p].tag*(tr[rc].r-tr[rc].l+1);
        tr[lc].tag+=tr[p].tag;
        tr[rc].tag+=tr[p].tag;
        tr[p].tag=0;
    }
}
void update(int p,int l,int r,int x){
    if( l<=tr[p].l && r>=tr[p].r ){
        tr[p].sum+=x*(tr[p].r-tr[p].l+1);
        tr[p].tag+=x;
        return;
    }
    pushdown(p);  ////先下放懒标记
    int mid=(tr[p].l+tr[p].r)>>1;
    if(l<=mid) update(lc,l,r,x);
    if(r>mid) update(rc,l,r,x);
    pushup(p);   ////
}
int query(int p,int l,int r){
    if( l<=tr[p].l && r>=tr[p].r ) return tr[p].sum;
    pushdown(p);
    int res=0;
    int mid=(tr[p].r+tr[p].l)>>1;
    if(l<=mid) res+=query(lc,l,r);
    if(r>mid) res+=query(rc,l,r);
    return res;
}
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>arr[i];
    build(1,1,n);
    while(q--){
        int op; cin>>op;
        if(op==1){
            int x,y,k; cin>>x>>y>>k;
            update(1,x,y,k);
        }
        else{
            int x,y; cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    solve();
    return 0;
}

总结：区间加，维护区间和，最最最典的板子，没啥好说的。

P2003 [CRCI 2008] PLATFORME 平板

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc p<<1
#define rc p<<1|1
const int N=500;
typedef struct node{
    int l,r,h,tag;
}node;
typedef struct myarr{
    int h0,l0,r0;
}myarr;
bool cmp(myarr a,myarr b){
    return a.h0<b.h0;
}
node tr[40000];
myarr arr[N];

void build(int p,int l,int r){
    tr[p]={l,r,0,0};
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
}

void pushup(int p){
    tr[p].h=max(tr[lc].h,tr[rc].h);
}
void pushdown(int p){
    if(tr[p].tag) {
        tr[lc].h = max(tr[lc].h, tr[p].tag);
        tr[rc].h = max(tr[rc].h, tr[p].tag);
        tr[lc].tag = max(tr[lc].tag, tr[p].tag);
        tr[rc].tag = max(tr[rc].tag, tr[p].tag);
        tr[p].tag = 0;
    }
}

void update(int p,int x,int y,int k){
    if( x<=tr[p].l&&tr[p].r<=y ){
        tr[p].h=max(tr[p].h,k);
        tr[p].tag=max(tr[p].tag,k);
        return;
    }
    pushdown(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(x<=mid) update(lc,x,y,k);
    if(y>mid) update(rc,x,y,k);
    pushup(p);
}

int query(int p,int x,int y){
    if(x==tr[p].l&&y==tr[p].r) return tr[p].h;
    pushdown(p);
    int res=0;
    int mid=(tr[p].l+tr[p].r)>>1;
    if(x<=mid) res=max(res,query(lc,x,y));
    if(y>mid) res=max(res,query(rc,x,y));
    return res;
}

void solve(){
    int n;
    cin>>n;
    int maxn=0;
    for(int i=1;i<=n;i++){
        cin>>arr[i].h0>>arr[i].l0>>arr[i].r0;
        maxn=max(maxn,arr[i].r0);
    }
    build(1,1,maxn-1);              ////转换为格子!!!
    sort(arr+1,arr+n+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=arr[i].h0-query(1,arr[i].l0,arr[i].l0);
        ans+=arr[i].h0-query(1,arr[i].r0-1,arr[i].r0-1);
        update(1,arr[i].l0,arr[i].r0-1,arr[i].h0);
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    solve();
    return 0;
}

总结：承接第一个板子。最最简单的修改第一个模板。只需要改成维护区间最大值即可。然后这题最好转换为一个一个的格子来做..

P3373 【模板】线段树 2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define lc p<<1
#define rc p<<1|1
typedef struct node{
    int l,r,sum,tag1,tag2;              ////tag1为加法懒标记,tag2为乘法懒标记
}node;
const int N=100005;
node tr[4*N];
int n,q,mod;
int arr[N];

void build(int p,int l,int r){
    tr[p]={l,r,arr[l],0,1};   ////tag2初始化应该是1!!
    if(l==r) return;
    int mid=(l+r)>>1;
    if(l<=mid) build(lc,l,mid);
    if(r>mid) build(rc,mid+1,r);
    tr[p].sum=(tr[lc].sum+tr[rc].sum)%mod;
}

void pushup(int p){
    tr[p].sum=(tr[lc].sum+tr[rc].sum)%mod;
}

void pushdown(int p){
    int tag1=tr[p].tag1,tag2=tr[p].tag2;
    tr[lc].sum=(tr[lc].sum*tag2+tag1*(tr[lc].r-tr[lc].l+1))%mod;   ////先乘后加!!
    tr[rc].sum=(tr[rc].sum*tag2+tag1*(tr[rc].r-tr[rc].l+1))%mod;
    tr[lc].tag1=tr[lc].tag1*tag2+tag1,tr[lc].tag2*=tag2;          ////新的乘上的tag2会影响原本的tag1吗???---我觉得会
    tr[lc].tag1%=mod,tr[lc].tag2%=mod;
    tr[rc].tag1=(tr[rc].tag1*tag2)+tag1,tr[rc].tag2*=tag2;
    tr[rc].tag1%=mod,tr[rc].tag2%=mod;
    tr[p].tag1=0,tr[p].tag2=1;     ////tag2初始值为1.
}

void update(int p,int l,int r,int x,int typ){
    if( l<=tr[p].l && r>=tr[p].r ){
        if(typ==1){             ////区间乘
            tr[p].sum*=x,tr[p].sum%=mod;
            tr[p].tag2*=x,tr[p].tag2%=mod;
            tr[p].tag1*=x,tr[p].tag1%=mod;          ////tag2会影响之前的tag1
            ////tr[p].tag1=tr[p].tag1*(tr[p].r-tr[p].l+1)*x%mod;     ////处理tag2对tag1的影响
            ////不对..如果多次连续对tag2更新的话，tag1的值会多加了
            return;
        }
        else{                 ////区间加
            tr[p].sum+=x*(tr[p].r-tr[p].l+1),tr[p].sum%=mod;
            tr[p].tag1+=x;
            return;
        }
    }
    pushdown(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(l<=mid) update(lc,l,r,x,typ);
    if(r>mid) update(rc,l,r,x,typ);
    pushup(p);
}

int query(int p,int l,int r){
    if( l<=tr[p].l && r>=tr[p].r ){
        return tr[p].sum;
    }
    int res=0;
    pushdown(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(l<=mid) res+=query(lc,l,r),res%=mod;
    if(r>mid) res+=query(rc,l,r),res%=mod;
    return res%mod;
}
////本题关键在于tag1和tag2...后加上的tag2会影响前面的tag1...
////解决方案：先乘后加
////例如:
////①操作使:tr[1].tag1+=2;
////②再操作使:tr[1].tag2*=3;   ////实际上在这个时候，tag2是会影响tag1的,但是不会影响3操作加上的4.所以更新tag2的时候,可以同时更新tag1.
////③再操作使:tr[1].tag1+=4;
void solve(){
    cin>>n>>q>>mod;
    for(int i=1;i<=n;i++) cin>>arr[i];
    build(1,1,n);
    int op,x,y,k;
    while(q--){
        cin>>op;
        if(op==1){              ////区间乘
            cin>>x>>y>>k;
            update(1,x,y,k,1);
        }
        else if(op==2){        ////区间加
            cin>>x>>y>>k;
            update(1,x,y,k,2);
        }
        else if(op==3){       ////查询
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    solve();
    return 0;
}

总结：在模板1的基础上，增加了区间乘的操作。所以需要两个懒标记，tag1记录加法，tag2记录乘法。这里有个问题就是tag2标记会影响已有的tag1。所以需要稍稍变动一点。

update时，当增加tag2之后，需要更新当前tag1。剩下的问题在于pushdown，应该先下放tag2，再下放tag1，即"先乘后加"。而tag2对tag1的影响已经提前处理了。

to be continue...

 

标签：tag1,tag2,int,线段,tr,rc,lc
From： https://www.cnblogs.com/ouhq/p/18211829

相关文章

  • 判断点在形状里，点在线段上
    /************************************************************************函数名: OnSegment功能描述: 判断点q是否在p1和p2的线段上（调试用）输入参数: p1线段端点1；p2线段端点2；q要判断的点；输出参数: 无返回值: ture点在线段上；false点不在线段上******......
  • 线段（线性dp）
     题目链接：https://www.luogu.com.cn/problem/P3842思路：f[i][0]表示走完第i行且停在第i行的左端点最少用的步数f[i][1]同理，停在右端点的最少步数。那么转移就很简单了，走完当前行且停到左端点，那么一定是从右端点过来的，那么从上一行左端点转移的话就是f[i][0]=abs(上一行左端......
  • 线段树模板
    一、模板#definelc(p)p<<1//左孩子#definerc(p)p<<1|1//右孩子constintMAX=5e5+5;//数列元素最大个数lln,m,w[MAX];//n--数列元素个数;m--操作数;w[i]--第i个元素的值struct{intl,r;llsum,tag;}t......
  • 线段树扩展
    首先是动态树，以数列操作为例点击查看代码#include<bits/stdc++.h>#definelsontr[id].l#definersontr[id].rusingnamespacestd;constintN=1e6+20;inta[N];structnode{ intl,r,sum;}tr[N<<2];intn,m;intnum;intrt;voidupdate(int&id,intl,intr,i......
  • hdu4027（线段树区间操作）
    Problem-4027(hdu.edu.cn)许多邪恶的战舰在战斗前排成一排。我们的指挥官决定使用我们的秘密武器来消灭战列舰。每艘战列舰都可以标记为耐力值。对于我们秘密武器的每一次攻击，它都可能降低连续部分战列舰的续航能力，使它们的续航力达到其原始续航力值的平方根。在我们的秘密武......
  • halcon xld线段中点、端点和角度的计算
    一、xld线段中点area_center_points_xld(Line4,Area,Row,Column)二、xld线段端点*xld转regiongen_region_contour_xld(LineContours,RegionLines,'filled')*提取区域轮骨skeleton(RegionLines,Skeleton)*获取轮骨端点junctions_skeleton(RegionLines,EndPoints......
  • 可持久化线段树
    经典的数据结构。权值线段树：维护一个序列，然后记下每个\(a_i\)的出现次数，相当于线段树维护桶。然后这样就可以轻而易举的求出\(1-n\)之间的第\(k\)小数了。原理类似于平衡数求\(rank.\)动态·可持久化下面考虑动态的权值线段树。\(l-r\)查询可以理解为第\(r\)个......
  • 洛谷 P2824 [HEOI2016/TJOI2016] 排序（二分，线段树）
    传送门解题思路据说是经典思路：把多次排序转化成二分+01序列。首先二分所求位置的数字是啥，将大于mid的数字变成1，将小于等于mid的数字变成0。这样在排序的时候就相当于统计区间里的1的个数（区间和），然后区间全部变成0或者1。也就是区间修改，区间求和，线段树可以实现。AC代码#inclu......
  • 雨天的尾巴（P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并）
    1.题意简化N个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。2.思路首先这道题肯定要用先建树，然后我们可以在树上的每个节点建一个权值线段树，考虑到空间问题（每个点都有1个权值......
  • P4839 P 哥的桶 线段树+线性基
    P4839P哥的桶线段树+线性基题目链接题意：现在有\(n\)个桶，需要支持2种操作。\(1\)\(k\)\(x\):将一个价值为\(x\)的球放进\(k\)号桶。\(2\)\(l\)\(r\):求出在\(l\)号桶到\(r\)号桶之间拿球，价值异或和最大值。思路：单点修改，区间查询。可以想到用线段树维护......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99