ca88亚洲城网站距离求和,唯有节点内的值备受震慑

题意:
给一个行列,最先全为0,然后有4种操作:

http://blog.csdn.net/liuledidai/article/details/9964697

在此地,所谓“可持久化”的数据结构并非指将数据存在非易失的存储器上,而是指保存了数据修改的野史音信。比如说对可持久化线段树举办修改操作,操作完成后我们得以在线段树原有的时光复杂度内查询到希望查询的版本的音信,比如“第二次修改后区间L和R之间的和”。

1.
给区间[L,R]所有值+c

( 1 )线段树效用: 单点替换 区间最值
I Hate
It

常常遇到的线条树都是构建之后结构不扭转的,所以在改动重点值时,唯有节点内的值备受震慑,而树本身的布局不暴发变化(比如左右子节点所代表的距离)。这为线段树举办可持久化提供了便民。大家每回修改的时候不直接改动原来节点的值,而是创造一多元新的节点。即便整棵树复制的话不仅分外耗费时间,而且占用空间太大。在线段树的单次修改中,实际上受到震慑的节点是零星的,原来的节点可以收获重新利用。

2.给区间[L,R]装有值乘c

#include <cstdio>
#include <algorithm>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 222222;
int MAX[maxn<<2];
void PushUP(int rt) {
MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l,int r,int rt) {  //rt当前节点编号
    if (l == r)//l==r,说明rt节点是叶子节点
    {           //由于先build左子树,再build右子树,所以最终会先写完左边的叶子节点,再写完右边的叶子节点
        scanf("%d",&MAX[rt]);
        return ;
    }
    int m = (l + r) >> 1;
    build(l , m , rt << 1);//rt*2
    build(m + 1 , r , rt << 1 | 1);//rt*2+1( rt*2 是偶数,rt<<1|1=rt*2+1)
    PushUP(rt);
}
void update(int p,int sc,int l,int r,int rt)
{
    if (l == r) {
        MAX[rt] = sc;
        return ;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p , sc , l , m , rt << 1);
    else update(p , sc , m + 1 , r , rt << 1 | 1);
    //PushUP(rt);
     MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
int query(int L,int R,int l,int r,int rt)//l r为线段树的完美区间,l mid为左子树区间, mid+1,r为右子树区间
{                                        //L , R是当前查询区间,它可能不是完美的,有可能包含左子树区间的一部分或者右子树的一部分
    if(L==l&&R==r) return MAX[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if(m>=R) return query(L,R,l,m,rt<<1);
    else if(m+1<=L) return query(L,R,m+1,r,rt<<1|1);
    else return max(query(L,m,l,m,rt<<1),query(m+1,R,m+1,r,rt<<1|1));
}
int main() {
    int n , m;
    while (~scanf("%d%d",&n,&m)) {
        build(1 , n , 1);
        while (m --) {
            char op[2];
            int a , b;
            scanf("%s%d%d",op,&a,&b);
            if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));
            else update(a , b , 1 , n , 1);
        }
    }
    return 0;
}

修改的进程

可持久化线段树每一遍修改都会自上而下地新建一些节点。每一次修改后的本子都有一个根节点与之相应。

只考虑单点修改,大家将递归过程中持有的节点创制一个“影子节点”,所谓“影子节点”保存的是当前涂改完毕后的面临更改的值。当u是v的黑影节点时,我们称v时u的原节点。

ca88亚洲城网站 1

对一棵线段树举行的一回可能暴发的改动操作,注意到每个根节点都对应了一次修改,不同的修改操功能了不同的颜料举办区分

在线段树的修改操作中,子节点修改形成后只影响到父节点(pushup操作),而不会影响到兄弟节点。所以大家发现,当修改影响到非叶子结点u时,(在单点修改中)他必然只有一个子节点会境遇修改的熏陶,比如右子节点受到震慑,此时u的黑影节点v的左子节点指向u的左子节点,而v的右子节点对应的是遭到震慑的新右子节点w,w是u的右子节点的阴影节点,以此类推。

3.安装区间[L,R]所有值为c

( 2)线段树效用:update:单点增减 query:区间求和
敌兵布阵

Lazy标签

对此区间修改,需要保障一个lazy标签来延缓更新操作,在pushdown操作时,创设了u的原节点的子节点的影子节点,在实质上贯彻中,通过爱慕一个节点的origin节点指针就足以成功这或多或少。

ca88亚洲城网站 2

革命是一个标志了lazy的操作,操作结束后并没有及时生成子节点的阴影节点。而在pushdown操作时(粉红色),新的黑影节点的值从原节点修改而来

4.查询[L,R]的p次方和(1<=p<=3)

#include <cstdio>
#include <algorithm>
#include<cstring>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN=50010;
int sum[MAXN<<2];
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&sum[rt]);
        return;
    }
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int pos,int val,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]+=val;
        return;
    }
    if(pos<=mid) update(pos,val,l,mid,rt<<1);
    else update(pos,val,mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int query(int L,int R,int l,int r,int rt)
{
    if(L==l&&R==r) return sum[rt];
    if(R<=mid) return query(L,R,l,mid,rt<<1);
    else if(mid+1<=L) return query(L,R,mid+1,r,rt<<1|1);
    else return query(L,mid,l,mid,rt<<1)+query(mid+1,R,mid+1,r,rt<<1|1);
}
int main()
{
    int t,n,L,R,val,pos;
    char order[10];
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d",&n);
        build(1,n,1);
        printf("Case %d:\n",cas);
        while(true)
        {
            scanf("%s",order);
            if(strcmp(order,"End")==0) break;
            else if(strcmp(order,"Query")==0)
            {
                scanf("%d%d",&L,&R);
                printf("%d\n",query(L,R,1,n,1));
            }
            else if(strcmp(order,"Add")==0)
            {
                scanf("%d%d",&pos,&val);
                update(pos,val,1,n,1);
            }
            else
            {
                scanf("%d%d",&pos,&val);
                update(pos,-val,1,n,1);
            }
        }
    }
    return 0;
}

实现

出于可持久化线段树在改动过程中需要不断新建影子节点,所以一般的下标标记子节点的法子不再有效。节点需要维护的不不过线段树的重大值x,还有左右子节点指针lch、rch,lazy标记和原节点指针origin。

在改动线段树时,沿着最新版本的线条树自上而下地遍历、创立影子节点并修改即可。

下边的程序实现了一个保障区间和的可持久化线段树,扶助区间修改。而且这些程序包含了一个demo。首先输入一个n,随后输入n个整数,表示a[1]~a[n]的最先值。随后开端询问和改动操作,输入q查询,m修改。查询接受一个版本号(从0最先),输出序列所有的值。修改接受u、v和w,表示将间隔[u,v]各种元素加上w。

#include <bits/stdc++.h>
using namespace std;
// 可持久化线段树
const int N = 100010;
struct Node {
    int sum, lch, rch, lazy, origin;
    Node():sum(0),lch(-1),rch(-1),lazy(0),origin(-1) {}
}tree[(N<<2)*4];
int tot, a[N], rt[N], curver;

void init() { tot=0; curver=0; }
int createIndentity(int p) {    // 创建影子节点
    int cp=tot++;
    tree[cp]=Node();
    tree[cp].origin=p;tree[cp].sum=tree[p].sum;tree[cp].lazy=tree[p].lazy;
    return cp;
}
void pushup(int p) { tree[p].sum=tree[tree[p].lch].sum+tree[tree[p].rch].sum; }
void pushdown(int p,int l,int r,int m) {
    int lch=tree[p].lch, rch=tree[p].rch;
    if (lch==-1||rch==-1) {
        int o=tree[p].origin;
        lch=tree[p].lch=createIndentity(tree[o].lch);
        rch=tree[p].rch=createIndentity(tree[o].rch);
    }
    tree[lch].lazy+=tree[p].lazy; tree[rch].lazy+=tree[p].lazy;
    tree[lch].sum+=tree[p].lazy*(m-l+1); tree[rch].sum+=tree[p].lazy*(r-m);
    tree[p].lazy=0;
}
int build(int l, int r) {
    int p=tot++;
    tree[p]=Node();
    tree[p].sum=a[l];
    if (l==r) return p;
    int mid=l+r>>1;
    tree[p].lch=build(l,mid);
    tree[p].rch=build(mid+1,r);
    pushup(p);
    return p;
}
int add(int p, int l, int r, int x, int y, int z) {
    int cp=tot++;       // create shadow node
    tree[cp]=Node();
    tree[cp].origin=p;  // origin node number, prepared for pushdown operation
    if (x<=l&&r<=y){
        tree[cp].lazy=tree[p].lazy+z;
        tree[cp].sum=tree[p].sum+z*(r-l+1);
        return cp;
    }
    int mid=l+r>>1;
    if (tree[p].lazy) pushdown(p,l,r,mid);
    if (x<=mid)
        tree[cp].lch=add(tree[p].lch,l,mid,x,y,z);
    else tree[cp].lch=tree[p].lch;
    if (mid<y)
        tree[cp].rch=add(tree[p].rch,mid+1,r,x,y,z);
    else tree[cp].rch=tree[p].rch;
    pushup(cp);
    return cp;
}
int query(int p, int l, int r, int x, int y) {
    if (x<=l&&r<=y) return tree[p].sum;
    int mid=l+r>>1, ret=0;
    if (tree[p].lazy) pushdown(p,l,r,mid);
    if (x<=mid) ret+=query(tree[p].lch,l,mid,x,y);
    if (mid<y) ret+=query(tree[p].rch,mid+1,r,x,y);
    return ret;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;++i) scanf("%d", a+i);
    // 
    init();
    rt[curver]=build(1,n);
    for (;;){
        int u,v,w;
        char q[3];
        printf("q/m:");
        scanf("%s", q);
        if (q[0]=='m') {
            printf("Please input u, v, w and we will add w to [u,v]: ");
            scanf("%d%d%d", &u, &v, &w);
            rt[curver+1]=add(rt[curver],1,n,u,v,w);
            ++curver;
            for (int i=1;i<=n;++i) {
                printf("%d ", query(rt[curver],1,n,i,i));
            }
            puts("");
        }else {
            printf("Please input ver: ");
            scanf("%d", &w);
            for (int i=1;i<=n;++i) {`
                printf("%d ", query(rt[w],1,n,i,i));
            }
            puts("");
        }
    }
    return 0;
}

Have fun!

解法:
线段树,维护五个记号,addmark,mulmark,setmark分别代表3种更新,然后p[1],p[2],p[3]个别代表该节点的1,2,3次方和。标记传递顺序setmark一定是第一个,因为setmark可以使mulmark,addmark都失效还原,mulmark和addmark的相继倒是无所谓。

ca88亚洲城网站,求逆序数+离散化
( 3 )线段树效率:update:单点增减 query:区间求和
参考文档
Ultra-QuickSort
题意:
求解一个队列的逆序数

这题写了半个竞技时间,写的很迷,依然没写出来,
后来看了外人写的,才了解自己许多地点都没更新好依然没更新。这题算是一道线段树的综合题了,混合了三种常见的翻新,对线段树的共同体把握很有帮扶。

#include <cstdio>
#include<cstdlib>
#include<string.h>
#include <algorithm>
#define maxn  500010
using namespace std;
int segTree[maxn<<2],aa[maxn];
struct Node
{
    int val,id;
}arr[maxn];
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return segTree[rt];
    int mid=(l+r)>>1;
    int ret=0;
    if(L<=mid) ret+=query(L,R,l,mid,rt<<1);
    if(R>=mid+1) ret+=query(L,R,mid+1,r,(rt<<1)|1);
    return ret;
}
void update(int index,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]++;
        return;

    }
    int mid=(l+r)>>1;
    if(index<=mid) update(index,l,mid,rt<<1);
    else update(index,mid+1,r,(rt<<1)|1);
    segTree[rt]=segTree[rt<<1]+segTree[(rt<<1)|1];
}
int cmp(const void *a,const void * b)
{
    return (*(Node *)a).val-(*(Node *)b).val;
}
int main() {
    int n,i;
    while(scanf("%d",&n)!=EOF,n)
    {
        memset(segTree,0,sizeof(segTree));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&arr[i].val);
            arr[i].id=i;
        }
        qsort(arr+1,n,sizeof(Node),cmp);
        for(int i=1;i<=n;i++)
            aa[arr[i].id]=i;
        long long  sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=query(aa[i],n,1,n,1);
            update(aa[i],1,n,1);
        }
        printf("%lld\n",sum);
    }

}

比如:

Minimum Inversion
Number

1.尽管setmark有值,那么addmark,mulmark全体要东山再起。

#include <cstdio>
#include<cstdlib>
#include<string.h>
#include <algorithm>
#define maxn  5005
using namespace std;
int segTree[maxn<<2],arr[maxn];
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return segTree[rt];
    int mid=(l+r)>>1;
    int ret=0;
    if(L<=mid) ret+=query(L,R,l,mid,rt<<1);
    if(R>=mid+1) ret+=query(L,R,mid+1,r,(rt<<1)|1);
    return ret;
}
void update(int index,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]++;
        return;

    }
    int mid=(l+r)>>1;
    if(index<=mid) update(index,l,mid,rt<<1);
    else update(index,mid+1,r,(rt<<1)|1);
    segTree[rt]=segTree[rt<<1]+segTree[(rt<<1)|1];
}
int main() {
    int n,i;
    while(scanf("%d",&n)!=EOF)
    {
        memset(segTree,0,sizeof(segTree));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&arr[i]);
        }
        int  sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=query(arr[i],n-1,0,n-1,1);
            update(arr[i],0,n-1,1);
        }
        int ret=sum;
        for(int i=1;i<=n;i++)
        {
            sum+=n-arr[i]-arr[i]-1;
            ret=min(sum,ret);
        }
        printf("%lld\n",ret);
    }
}

2.只要mulmark有值,那么addmark也要革新,更新为addmark*mulmark

( 4 )
题意:h*w的木板,放进一些1*L的物品,求每一遍放空间能兼容且最上边的位子
思路:每一遍找到最大值的座席,然后减去L
线段树功用:query:区间求最大值的席位(直接把update的操作在query里做了)

就是这两点平素没考虑到,WA了许久。

把每行看成线段树的叶子记录每片叶子的盈余空间,而根节点中保存的是纸牌节点最大的剩下空间,每便判断给定的宽窄从根节点能否插入,若左子数可以插则先行插入左子树,这样就足以确保每回插入都插在最上边。

在addmark下传过程中更新p[1],p[2],p[3]的艺术如下:

Billboard

比如 a^3
-> (a+c)^3 的过程:  (a+c)^3 = a^3 + c^3 + 3a*c^2 + 3*a^2*c,
a是变量,
所以提取出c,那么p[3]可以由p[1],p[2]推出,p[2]可以由p[1]推出。

#include <cstdio>
#include<cstdlib>
#include<string.h>
#include <algorithm>
#define maxn  900010
using namespace std;
int segTree[maxn],w,h,n;
void build(int l,int r,int rt)
{
    segTree[rt]=w;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
int query(int need,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]-=need;
        return l;
    }
    int ans,mid=(l+r)>>1;
    if(segTree[rt<<1]>=need) ans=query(need,l,mid,rt<<1);
    else ans=query(need,mid+1,r,rt<<1|1);
    segTree[rt]=max(segTree[rt<<1],segTree[rt<<1|1]);
    return ans;
}
int main() {
    int i,need;
    while(scanf("%d%d%d",&h,&w,&n)!=EOF)
    {
        h=min(h,n);
        build(1,h,1);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&need);
            if(segTree[1]<need) printf("-1\n");
            else printf("%d\n",query(need,1,h,1));
        }
    }
}

即 p[3]
= p[3] + c^3 + 3*c^2*p[1] + 3*c*p[2] . 

https://scut.online/problem.php?id=77
( 5 ) 题意:有两个操作:
1、将区间[ L,R ]里的所有数变为原来的一半。
2、询问区间 [ L,R ]的数之和,结果对1000000007取模。
n,m(n,m≤100000),n为点的个数,编号为1-n,m为操作次数
线段树功能:区间更新,区间求和。注意一个足以优化的地方:在query和update操作中,假若segTree[rt]==0,则无需递归下去了;不然容易超时。

p[2]同理可以由p[1]推出。

#include<stdio.h>
#include <string.h>
using namespace std;
#define maxn 100010
typedef long long LL;
LL segTree[maxn<<2];
const LL mod=1000000007;
//void pushUp(int rt)
//{
//    segTree[rt]=(segTree[rt<<1]+segTree[(rt<<1)|1])%mod;
//}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%lld",&segTree[rt]);
        return;
    }
    int mid=l+((r-l)>>1);
    build(l,mid,rt<<1);
    build(mid+1,r,(rt<<1)|1);
    segTree[rt]=(segTree[rt<<1]+segTree[(rt<<1)|1])%mod;
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return segTree[rt];
    if(L<=l&&r<=R&&segTree[rt]==0) return 0;
    int mid=l+((r-l)>>1);
    LL sum=0;
    if(mid>=L) sum=(sum+query(L,R,l,mid,rt<<1))%mod;
    if(mid+1<=R) sum=(sum+query(L,R,mid+1,r,(rt<<1)|1))%mod;
    return sum;
}
void update(int L,int R,int l,int r,int rt)
{
    if(l==r)
    {
        segTree[rt]>>=1;
        return;
    }
    if(L<=l&&r<=R&&segTree[rt]==0) return;
    int mid=l+((r-l)>>1);
    if(L<=mid) update(L,R,l,mid,rt<<1);
    if(mid+1<=R) update(L,R,mid+1,r,(rt<<1)|1);
    segTree[rt]=(segTree[rt<<1]+segTree[(rt<<1)|1])%mod;
}
int main()
{
    int t,L,R;
    char op[5];
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        build(1,n,1);
        for(int i=1;i<=m;i++)
        {
            scanf("%s%d%d",op,&L,&R);
            if(op[0]=='A')
            {
                printf("%lld\n",query(L,R,1,n,1));
            }
            else
            {
                update(L,R,1,n,1);
            }
        }
    }
}

然后每一趟都做一下pushdown,就足以汲取正确答案。

( 6 ) 线段树效能:update :区间增减 query:区间求和
题目大意:给定N个数的队列,有Q个操作。
操作分三种:
1、将某个区间内的所有数都添加某个数。
2、总结某个区间的所有数之和并出口。

旋即像优化一下,少做三回pushdown,即本次的操作类型与上次一模一样就不pushdown,结果这样就会冒出问题,还不如每一趟都pushdown呢。

主意一:逐点更新

咱俩有一个节能的思绪,更新区间时对区间内的富有点逐个立异

#include <cstdio>
#include <algorithm>
#include<cstring>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN=100010;
long long sum[MAXN<<2];
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int L,int R,int l,int r,int rt,long long val)
{
    if(l==r)//对区间内的所有点逐个更新
    {
        sum[rt]+=val;
        return;
    }
    if(R<=mid) update(L,R,l,mid,rt<<1,val);
    else if(mid+1<=L) update(L,R,mid+1,r,rt<<1|1,val);
    else
    {
        update(L,mid,l,mid,rt<<1,val);
        update(mid+1,R,mid+1,r,rt<<1|1,val);
    }
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
long long query(int L,int R,int l,int r,int rt)
{
    if(L==l&&R==r) return sum[rt];
    if(R<=mid) return query(L,R,l,mid,rt<<1);
    else if(mid+1<=L) return query(L,R,mid+1,r,rt<<1|1);
    return query(L,mid,l,mid,rt<<1)+query(mid+1,R,mid+1,r,rt<<1|1);
}
int main()
{
    int n,m,L,R;
    long long val;
    char op[5];
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",op);
        if(op[0]=='Q')
        {
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(L,R,1,n,1));
        }
        else
        {
            scanf("%d%d%lld",&L,&R,&val);
            update(L,R,1,n,1,val);
        }
    }
    return 0;
}

不过,对各种点逐个拓展改进,相当于暴力无疑,这样会很容易超时的,而且也显示不出线段树的优势!!!
所以需要举行延期更新,延迟更新指等到调用update时或者查询时才履新节点的孩子的值

代码:

措施二 :延迟更新法

A Simple Problem with
Integers

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100010;
#define lson l,md,(rt<<1)
#define rson md+1,r,(rt<<1|1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define md ((l+r)>>1)
LL sum[maxn<<2],lazy[maxn<<2];
void up(int rt)
{
    sum[rt]=sum[ls]+sum[rs];
}
void down(int l,int r,int rt)//延迟标记向下(孩子节点)传递
{
    if(lazy[rt])
    {
        sum[ls]+=(md-l+1)*lazy[rt];//更新左孩子节点的val
        lazy[ls]+=lazy[rt];//延迟标记向左孩子传递,以表明我左孩子节点已经更新了,
//但是!!左孩子的子节点还没更新呢!!!

        sum[rs]+=(r-(md+1)+1)*lazy[rt];//更新右孩子
        lazy[rs]+=lazy[rt];//延迟标记向右孩子传递,以表明我右孩子节点已经更新了,
//但是!!右孩子的子节点还没更新呢!!!

        lazy[rt]=0;//当前节点已经更新过了,所以取消标记
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=0;//初始化为0
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    build(lson);
    build(rson);
    up(rt);
}
void update(int L,int R,int l,int r,int rt,LL val)
{
    if(L==l&&r==R)//如果当前要更新的区间和线段树的完美区间一样
    {//那就把当前的区间给它更新,并更新当前节点lazy标记,表明它的两个孩子还没更新
//举个例子,假设总区间为1-12,现在要求更新6-10;假设现在更新到7-9,
//很明显,7-9是线段树的完美区间,所以对该段整段更新:sum[rt]+=(R-L+1)*val;
//但是!!!它的两个孩子节点还没更新呢,它就return了
//所以为这个节点添加延迟标记,以表明它的孩子节点还没更新:lazy[rt]+=val;
        sum[rt]+=(R-L+1)*val;
        lazy[rt]+=val;
        return;
    }
    down(l,r,rt);//如果当前节点有延迟标记,那么更新一下节点的val以及传递延迟标记给孩子节点

    if(md>=R) update(L,R,lson,val);
    else if(md+1<=L) update(L,R,rson,val);
    else{
        update(L,md,lson,val);
        update(md+1,R,rson,val);
    }
    up(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L==l&&r==R) return sum[rt];
    down(l,r,rt);//如果当前节点有延迟标记,那么更新一下节点的val以及传递延迟标记给孩子节点
    if(md>=R) return query(L,R,lson);
    else if(md+1<=L) return query(L,R,rson);
    return query(L,md,lson)+query(md+1,R,rson);
}
int main() {
    int n,m,L,R;
    LL val;
    char op[5];
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",op);
        if(op[0]=='Q')
        {
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(L,R,1,n,1));
        }
        else
        {
            scanf("%d%d%lld",&L,&R,&val);
            update(L,R,1,n,1,val);
        }
    }
    return 0;
}

方法三:
也是延迟更新可是有点不雷同,具体请看代码

#include<cstdio>
#include <algorithm>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN=100010;
long long sum[MAXN*4],mark[MAXN*4];
void build(int l,int r,int rt)
{
    sum[rt]=mark[rt]=0;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int l,int r,int L,int R,int rt,int val)
{
    sum[rt]=sum[rt]+(R-L+1)*val;
    if(l==L&&R==r)
    {
        mark[rt]+=val;
        return;
    }
    if(R<=mid) update(l,mid,L,R,rt<<1,val);
    else if(L>mid) update(mid+1,r,L,R,rt<<1|1,val);
    else
    {
        update(l,mid,L,mid,rt<<1,val);
        update(mid+1,r,mid+1,R,rt<<1|1,val);
    }
}
long long query(int l,int r,int rt,int L,int R)
{
    if(L==l&&R==r) return sum[rt];
    long long ans=(R-L+1)*mark[rt];
    if(R<=mid) ans+=query(l,mid,rt<<1,L,R);
    else if(L>mid) ans+=query(mid+1,r,rt<<1|1,L,R);
    else
    {
        ans+=query(l,mid,rt<<1,L,mid);
        ans+=query(mid+1,r,rt<<1|1,mid+1,R);
    }
    return ans;
}
int main()
{
    int n,m,L,R;
    long long  val;
    char op[5];
    scanf("%d%d",&n,&m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",op);
        if(op[0]=='Q')
        {
            scanf("%d%d",&L,&R);
            printf("%lld\n",query(1,n,1,L,R));
        }
        else
        {
            scanf("%d%d%lld",&L,&R,&val);
            update(1,n,L,R,1,val);
        }
    }
    return 0;
}

( 7 ) 线段树效用: update:区间替换 ,query:区间求和
Just a
Hook

题意:
一段线段由n条小线段组成,每一次操作把一个距离的小线段变成金银铜之一(金的市值为3,银为2,铜为1),最初可看作全为铜;最后求那条线段的总价值。

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100010;
#define lson l,md,(rt<<1)
#define rson md+1,r,(rt<<1|1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define md ((l+r)>>1)
LL sum[maxn<<2],lazy[maxn<<2];
void up(int rt)
{
    sum[rt]=sum[ls]+sum[rs];
}
void down(int l,int r,int rt)
{
    if(lazy[rt])
    {
        sum[ls]=(md-l+1)*lazy[rt];
        lazy[ls]=lazy[rt];

        sum[rs]=(r-(md+1)+1)*lazy[rt];
        lazy[rs]=lazy[rt];

        lazy[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=0;
    if(l==r)
    {
        sum[rt]=1;
        return;
    }
    build(lson);
    build(rson);
    up(rt);
}
void update(int L,int R,int l,int r,int rt,LL val)
{
    if(L==l&&r==R)
    {
        sum[rt]=(R-L+1)*val;
        lazy[rt]=val;
        return;
    }
    down(l,r,rt);

    if(md>=R) update(L,R,lson,val);
    else if(md+1<=L) update(L,R,rson,val);
    else{
        update(L,md,lson,val);
        update(md+1,R,rson,val);
    }
    up(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L==l&&r==R) return sum[rt];
    down(l,r,rt);
    if(md>=R) return query(L,R,lson);
    else if(md+1<=L) return query(L,R,rson);
    return query(L,md,lson)+query(md+1,R,rson);
}
int main() {
    int t,n,m,L,R;
    LL val;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d%d",&n,&m);
        build(1,n,1);
        while(m--)
        {
            scanf("%d%d%lld",&L,&R,&val);
            update(L,R,1,n,1,val);
        }
        printf("Case %d: The total value of the hook is %lld.\n",cas,query(1,1,1,1,1));
    }
    return 0;
}

https://vjudge.net/problem/HDU-1698
( 7 ) 线段树功能: update:区间变成原来的b次方 ,query:区间乘积
题意:操作1: l ,r ,b : 把k∈[l,r] 的妹子, 能力值 a​k变成ak^​b
操作2:l , r : 求累乘 ∏(​l⩽k⩽r)ak
题解:a​^k ≡ a^(​k mod (p−1)) mod p , p是素数.

#include<cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100020;
const LL mod=1000000007;
#define lson l,md,(rt<<1)
#define rson md+1,r,(rt<<1|1)
#define md ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
LL sum[maxn<<2],lazy[maxn<<2];
LL pow_mod(LL a,int b)
{
    LL res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
void up(int rt)
{
    sum[rt]=sum[ls]*sum[rs]%mod;
}
void down(int l,int r,int rt)
{
     if(lazy[rt]!=1)
    {
        sum[ls]=pow_mod(sum[ls],lazy[rt]);
        lazy[ls]=lazy[ls]*lazy[rt]%(mod-1);

        sum[rs]=pow_mod(sum[rs],lazy[rt]);
        lazy[rs]=lazy[rs]*lazy[rt]%(mod-1);

        lazy[rt]=1;
    }
}
void update(int L,int R,int l,int r,int rt,int b)
{
    if(L==l&&r==R)
    {
        sum[rt]=pow_mod(sum[rt],b);
        lazy[rt]=lazy[rt]*b%(mod-1);
        return;
    }
    down(l,r,rt);
    if(R<=md) update(L,R,lson,b);
    else if(L>md) update(L,R,rson,b);
    else{
        update(L,md,lson,b);
        update(md+1,R,rson,b);
    }
    sum[rt]=sum[ls]*sum[rs]%mod;
}
LL query(int L,int R,int l,int r,int rt)
{
    if(L==l&&r==R) return sum[rt];
    down(l,r,rt);
    if(R<=md) return query(L,R,lson);
    else if(L>md) return query(L,R,rson);
    return query(L,md,lson)*query(md+1,R,rson)%mod;
}
void build(int l,int r,int rt)
{
    lazy[rt]=1;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return ;
    }
    build(lson);
    build(rson);
    sum[rt]=sum[ls]*sum[rs]%mod;
}
int main() {
    int t,n,m;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        build(1, n, 1);
        while(m--) {
            int op, l, r, b;
            scanf("%d%d%d", &op, &l, &r);
            if(op == 1) {
                scanf("%d", &b);
                update(l,r,1,n,1,b);
            }
            else {
                LL ans = query(l,r,1,n,1);
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}

ca88亚洲城网站 3ca88亚洲城网站 4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define Mod 10007
#define SMod 10007
using namespace std;
#define N 100017

struct node{
    int p[4];
    int setmark,addmark,mulmark;
}tree[4*N];

void pushup(int rt){
    for(int i=1;i<=3;i++) tree[rt].p[i] = (tree[2*rt].p[i] + tree[2*rt+1].p[i])%SMod;
}

void pushdown(int l,int r,int rt)
{
    int mid = (l+r)/2;
    if(tree[rt].setmark)
    {
        int mk = tree[rt].setmark;
        tree[rt<<1].setmark = tree[rt<<1|1].setmark = mk;
        tree[rt<<1].addmark = tree[rt<<1|1].addmark = 0;
        tree[rt<<1].mulmark = tree[rt<<1|1].mulmark = 1;

        tree[rt<<1].p[1] = (mid-l+1)%Mod*mk%SMod;
        tree[rt<<1|1].p[1] = (r-mid)%Mod*mk%SMod;

        tree[rt<<1].p[2] = (mid-l+1)%Mod*mk%SMod*mk%SMod;
        tree[rt<<1|1].p[2] = (r-mid)%Mod*mk%SMod*mk%SMod;

        tree[rt<<1].p[3] = (mid-l+1)%Mod*mk%SMod*mk%SMod*mk%SMod;
        tree[rt<<1|1].p[3] = (r-mid)%Mod*mk%SMod*mk%SMod*mk%SMod;
        tree[rt].setmark = 0;
    }
    if(tree[rt].mulmark != 1)
    {
        int mk = tree[rt].mulmark;
        tree[rt<<1].mulmark *= mk, tree[rt<<1].mulmark%=SMod;
        tree[rt<<1|1].mulmark *= mk, tree[rt<<1|1].mulmark%=SMod;

        tree[rt<<1].addmark = tree[rt<<1].addmark%SMod*mk%SMod;
        tree[rt<<1|1].addmark = tree[rt<<1|1].addmark%SMod*mk%SMod;

        tree[rt<<1].p[1] = tree[rt<<1].p[1]%Mod*mk%SMod;
        tree[rt<<1|1].p[1] = tree[rt<<1|1].p[1]%Mod*mk%SMod;

        tree[rt<<1].p[2] = tree[rt<<1].p[2]%Mod*mk%SMod*mk%SMod;
        tree[rt<<1|1].p[2] = tree[rt<<1|1].p[2]%Mod*mk%SMod*mk%SMod;

        tree[rt<<1].p[3] = tree[rt<<1].p[3]%Mod*mk%SMod*mk%SMod*mk%SMod;
        tree[rt<<1|1].p[3] = tree[rt<<1|1].p[3]%Mod*mk%SMod*mk%SMod*mk%SMod;
        tree[rt].mulmark = 1;
    }
    if(tree[rt].addmark)
    {
        int mk = tree[rt].addmark;
        tree[rt<<1].addmark += mk, tree[rt<<1].addmark%SMod;
        tree[rt<<1|1].addmark += mk, tree[rt<<1|1].addmark%SMod;

        tree[rt<<1].p[3] = (tree[rt<<1].p[3]%Mod + (mid-l+1)%Mod*mk%SMod*mk%SMod*mk%SMod + 3*mk%Mod*tree[rt<<1].p[2]%SMod + 3*mk%SMod*mk%SMod*tree[rt<<1].p[1]%SMod)%SMod;
        tree[rt<<1|1].p[3] = (tree[rt<<1|1].p[3]%Mod + (r-mid)%Mod*mk%SMod*mk%SMod*mk%SMod + 3*mk%Mod*tree[rt<<1|1].p[2]%SMod + 3*mk%SMod*mk%SMod*tree[rt<<1|1].p[1]%SMod)%SMod;

        tree[rt<<1].p[2] = (tree[rt<<1].p[2]%Mod + (mid-l+1)%Mod*mk%SMod*mk%SMod + 2*mk%Mod*tree[rt<<1].p[1]%SMod)%SMod;
        tree[rt<<1|1].p[2] = (tree[rt<<1|1].p[2]%Mod + (r-mid)%Mod*mk%SMod*mk%SMod + 2*mk%Mod*tree[rt<<1|1].p[1]%SMod)%SMod;

        tree[rt<<1].p[1] = (tree[rt<<1].p[1]%Mod + (mid-l+1)%Mod*mk%SMod)%SMod;
        tree[rt<<1|1].p[1] = (tree[rt<<1|1].p[1]%Mod + (r-mid)%Mod*mk%SMod)%SMod;
        tree[rt].addmark = 0;
    }
}

void build(int l,int r,int rt)
{
    tree[rt].setmark = tree[rt].addmark = 0;
    tree[rt].mulmark = 1;
    memset(tree[rt].p,0,sizeof(tree[rt].p));
    if(l == r) return;
    int mid = (l+r)/2;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}

void update(int l,int r,int aa,int bb,int tag,int val,int rt)  //tag = 3 : set  2:mul 1: add
{
    if(aa <= l && bb >= r)
    {
        if(tag == 3)
        {
            tree[rt].p[1] = (r-l+1)%Mod*val%SMod;
            tree[rt].p[2] = (r-l+1)%Mod*val%SMod*val%SMod;
            tree[rt].p[3] = (r-l+1)%Mod*val%SMod*val%SMod*val%SMod;
            tree[rt].setmark = val;
            tree[rt].addmark = 0;
            tree[rt].mulmark = 1;
        }
        else if(tag == 2)
        {
            tree[rt].p[1] = tree[rt].p[1]%SMod*val%SMod;
            tree[rt].p[2] = tree[rt].p[2]%SMod*val%SMod*val%SMod;
            tree[rt].p[3] = tree[rt].p[3]%SMod*val%SMod*val%SMod*val%SMod;
            tree[rt].mulmark = tree[rt].mulmark%SMod*val%SMod;
            tree[rt].addmark = tree[rt].addmark%SMod*val%SMod;
        }
        else if(tag == 1)
        {
            tree[rt].p[3] = (tree[rt].p[3]%SMod + (r-l+1)%SMod*val%SMod*val%SMod*val%SMod + 3*val%SMod*tree[rt].p[2]%SMod + 3*val%SMod*val%SMod*tree[rt].p[1]%SMod)%SMod;
            tree[rt].p[2] = (tree[rt].p[2]%SMod + (r-l+1)%SMod*val%SMod*val%SMod + 2*val%SMod*tree[rt].p[1]%SMod)%SMod;
            tree[rt].p[1] = (tree[rt].p[1]%SMod + (r-l+1)%SMod*val%SMod)%SMod;
            tree[rt].addmark = (tree[rt].addmark+val)%SMod;
        }
        return;
    }
    int mid = (l+r)/2;
    pushdown(l,r,rt);
    if(aa <= mid) update(l,mid,aa,bb,tag,val,rt<<1);
    if(bb > mid)  update(mid+1,r,aa,bb,tag,val,rt<<1|1);
    pushup(rt);
}

int query(int l,int r,int aa,int bb,int i,int rt)
{
    if(aa > r || bb < l) return 0;
    if(aa <= l && bb >= r)
        return tree[rt].p[i];
    pushdown(l,r,rt);
    int res = 0;
    int mid = (l+r)/2;
    return (query(l,mid,aa,bb,i,rt<<1)%SMod+query(mid+1,r,aa,bb,i,rt<<1|1)%SMod)%SMod;
}

int main()
{
    int n,m,i,j,op,x,y,c;
    while(scanf("%d%d",&n,&m)!=EOF && n+m)
    {
        build(1,n,1);
        while(m--)
        {
            scanf("%d%d%d%d",&op,&x,&y,&c);
            if(op != 4) update(1,n,x,y,op,c,1);
            else        printf("%d\n",query(1,n,x,y,c,1)%SMod);
        }
    }
    return 0;
}

View Code

相关文章