HFUUOJ1024 动态开点线段树+标记永久化

概述题意 分析 动态加点线段树，标记永久化好写常数小 Code #include<bits/stdc++.h>#define fi first#define se second#define lson l,mid,p<<1#define rson mid+1,r,p<<1|1#define pb push_back#define ll long longusing namespace s 题意

分析

动态加点线段树，标记永久化好写常数小

Code

#include<bits/stdc++.h>#define fi first#define se second#define lson l,mID,p<<1#define rson mID+1,r,p<<1|1#define pb push_back#define ll long longusing namespace std;const ll inf=1e18;const int mod=1e9+7;const int maxn=1e7+10;int n,m;ll tr[maxn];int ls[maxn],rs[maxn],tag[maxn],tot;int rt;voID up(ll x,ll y,ll l,ll r,int &p,ll k){    tr[++tot]=(tr[p]+(y-x+1)%mod*k%mod)%mod;    ls[tot]=ls[p],rs[tot]=rs[p],tag[tot]=tag[p],p=tot;    if(x==l&&y==r){        tag[p]=(tag[p]+k)%mod;        return;    }ll mID=l+r>>1;    if(y<=mID) up(x,y,l,ls[p],k);    else if(x>mID) up(x,mID+1,rs[p],k);    else up(x,k),up(mID+1,k);}ll qy(ll x,int p,ll k){    if(x==l&&y==r){        return (tr[p]+(y-x+1)%mod*k%mod)%mod;    }ll mID=l+r>>1;    if(y<=mID) return qy(x,(k+tag[p])%mod);    else if(x>mID) return qy(x,(k+tag[p])%mod);    else return (qy(x,(k+tag[p])%mod)+qy(mID+1,(k+tag[p])%mod))%mod;}int main(){    //ios::sync_with_stdio(false);    //freopen("in","r",stdin);    cin>>m;    for(int i=1,op;i<=m;i++){        ll x,r;scanf("%d%lld%lld",&op,&l,&r);        if(op==1){            scanf("%lld",&x);            x%=mod;            up(l,1,inf,rt,x);        }else{            printf("%lld\n",qy(l,0));        }    }    return 0;}

总结

以上是内存溢出为你收集整理的HFUUOJ1024 动态开点线段树+标记永久化全部内容，希望文章能够帮你解决HFUUOJ1024 动态开点线段树+标记永久化所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。