线段树---区间更新

线段树的区间更新一般是指，对一段区间做如下操作:

把一段区间的值变成某一个值
把一段区间的是加上某一个值

然后求再给定一个区间 $[l,r]$ ，查询给定区间的和

这种问题我们可以通过一种lazy标记的方式来解决，比如现在有一个序列1~10，下标也是1~10现在要给区间[1,4]加上一个值3(请参考线段树开始的那一个图)，我们首先会遇见区间[1,10],这个区间不能被[1,4]包含所以向下走，到了[1,5]还是不行，继续向下，到了[1,3]，这个区间完全被[1,4]包含，我们就可以在这里打上lazy标记，让lazy所表示的值是当前的区间需要加上的但是还没加的值，然后再更新sum的值，使sum+=c*(l-r+1),但是现在[1,4]还没被包括完，所以我们还会找到[4,4],继续打上lazy标记，继续更新。。。在更新的时候我们如果遇到了lazy标记，就需要下放，也就是向下更新把lazy的值传递下去，使得当前的lazy值为0.

以两个例题来说明.

HDU1698 Just a Hook(线段树+成段更新+lazy标记)

这个是把区间的某一段变成一个值

#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
const int N=1e6+50;
int lazy[N<<2],sum[N<<2];
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int m)//下放lazy标记
{
    if(lazy[rt])
    {
        lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];//把左右儿子的值变成需要的
        sum[rt<<1]=(m-(m>>1))*lazy[rt];//更新sum的值
        sum[rt<<1|1]=(m>>1)*lazy[rt];
        lazy[rt]=0;//取消lazy标记
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=0;
    if(l==r)
    {
        sum[rt]=1;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)//符合条件后打上lazy标记和更新sum
    {
        lazy[rt]=c;
        sum[rt]=c*(r-l+1);
        return;
    }
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(R>m) update(L,R,c,rson);
    pushup(rt);
}

int main()
{
    int t,n,m,a,b,c,q=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        build(1,n,1);
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            update(a,b,c,1,n,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",q++,sum[1]);
    }
    return 0;
}

POJ3468 A Simple Problem with Integers(线段树区间更新，lazy标记)

这是把一段区间的值加某一个值

#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
const ll N=100000+50;
ll lazy[N<<2],sum[N<<2];
void pushup(ll rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(ll rt,ll m)//下放lazy标记
{
    if(lazy[rt])
    {
        lazy[rt<<1]+=lazy[rt];//给左儿子下放lazy
        lazy[rt<<1|1]+=lazy[rt];//给右儿子下放lazy
        sum[rt<<1]+=lazy[rt]*(m-(m>>1));//更新sum
        sum[rt<<1|1]+=lazy[rt]*(m>>1);
        lazy[rt]=0;
    }
}
void build(ll l,ll r,ll rt)
{
    lazy[rt]=0;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    ll m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(ll L,ll R,ll c,ll l,ll r,ll rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]+=c;
        sum[rt]+=c*(r-l+1);
        return;
    }
    pushdown(rt,r-l+1);
    ll m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(R>m) update(L,R,c,rson);
    pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
    if(L<=l&&r<=R)
        return sum[rt];
    pushdown(rt,r-l+1);
    ll m=(l+r)>>1;
    ll ans=0;
    if(L<=m) ans+=query(L,R,lson);
    if(R>m) ans+=query(L,R,rson);
    return ans;
}

int main()
{
    char s[5];
    ll n,m,a,b,c;
    scanf("%lld%lld",&n,&m);
    build(1,n,1);
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='Q')
        {
            scanf("%lld%lld",&a,&b);
            printf("%lld\n",query(a,b,1,n,1));
        }
        if(s[0]=='C')
        {
            scanf("%lld%lld%lld",&a,&b,&c);
            update(a,b,c,1,n,1);
        }
    }
    return 0;
}

HDU4027 Can you answer these queries?(线段树区间更新,区间开根号)

题目先给了一段区间，然后给了m组询问，0代表把a~b这个区间的每个值变成它的平方根，1代表查询a~b这个区间的和。这个题容易超时，我们应该知道，一个数开平方开上几次后肯定会变成1，所以我们需要加上一句判断，判断当前要更新的节点的和是否等于他左右区间的差，如果等于，那就证明这一段区间都是1，已经不用再更新了，剩下的就是普通的线段树了

#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  
const ll N=100000+20;  
ll sum[N<<2];  
ll flag[N<<2];  
void pushup(ll rt)  
{  
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];  
    flag[rt]=flag[rt<<1]&flag[rt<<1|1];  
}  
void build(ll l,ll r,ll rt)  
{  
    if(l==r)  
    {  
        scanf("%lld",&sum[rt]);  
        if(sum[rt]<=1)flag[rt]=1;  
        return;  
    }  
    ll m=(l+r)>>1;  
    build(lson);  
    build(rson);  
    pushup(rt);  
}  
void update(ll a,ll b,ll l,ll r,ll rt)  
{  
    if(flag[rt]==1) return;  
    if(l==r)  
    {  
        sum[rt]=floor(sqrt(sum[rt]));  
        if(sum[rt]<=1)flag[rt]=1;  
        return;  
    }  
    ll m=(l+r)>>1;  
    if(a<=m)  
        update(a,b,lson);  
    if(b>m)  
        update(a,b,rson);  
    pushup(rt);  
}  
ll query(ll L,ll R,ll l,ll r,ll rt)  
{  
    if(L<=l&&r<=R)  
        return sum[rt];  
    ll m=(l+r)>>1;  
    ll ans=0;  
    if(L<=m)  
        ans+=query(L,R,lson);  
    if(R>m)  
        ans+=query(L,R,rson);  
    return ans;  
}  
int main()  
{  
    ll n,m;  
    ll q=1,a,b,x;  
    while(~scanf("%lld",&n))  
    {  
        mem(flag,0);  
        printf("Case #%lld:\n",q++);  
        build(1,n,1);  
        scanf("%lld",&m);  
        while(m--)  
        {  
            scanf("%lld%lld%lld",&x,&a,&b);  
            if(a>b)swap(a,b);  
            if(x==1)  
                printf("%lld\n",query(a,b,1,n,1));  
            else if(x==0)  
                update(a,b,1,n,1);  
        }  
        puts("");  
    }  
    return 0;  
}

区间染色: ZOJ1610 Count the Colors(线段树区间染色，成段更新) 题目给出n个数据，有一个0~8000的区间，每组数据包含区间的左右端点和要染成的颜色，最后要输出每种颜色有几个区间。在建树的时候要用8000来建树，还要注意一个区间问题：比如 1 2 1,3 4 1 这时候应该输出1 2，所以我们在更新区间的时候要给左区间加上1.剩下的就是在询问的时候，用一个值来代表当前的颜色，只有当颜色不同时，对应的记录颜色区间个数点的数组要+1

#define mem(a,b) memset(a,b,sizeof(a))  
#define inf 0x3f3f3f3f  
#define N 10050x  
#define ll long long  
using namespace std;  
#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  
int sum[N<<2],num[N],tot;  
void pushdown(int rt)  
{  
    if(sum[rt]!=-1)  
    {  
        sum[rt<<1]=sum[rt<<1|1]=sum[rt];  
        sum[rt]=-1;  
    }  
}  
void update(int L,int R,int c,int l,int r,int rt)  
{  
    if(L<=l&&r<=R)  
    {  
        sum[rt]=c;  
        return;  
    }  
    pushdown(rt);  
    int m=(l+r)>>1;  
    if(L<=m) update(L,R,c,lson);  
    if(m<R) update(L,R,c,rson);  
}  
void query(int l,int r,int rt)  
{  
    if(l==r)  
    {  
        if(sum[rt]>=0&&sum[rt]!=tot)  
            num[sum[rt]]++;  
        tot=sum[rt];//如果区间连续就不记录  
        return;  
    }  
    pushdown(rt);  
    int m=(l+r)>>1;  
    query(lson);  
    query(rson);  
}  
int main()  
{  
    int n,a,b,c;  
    while(~scanf("%d",&n))  
    {  
        mem(num,0);  
        mem(sum,-1);  
        tot=-1;  
        for(int i=1; i<=n; i++)  
        {  
            scanf("%d%d%d",&a,&b,&c);  
            update(a+1,b,c,1,8000,1);  
        }  
        query(1,8000,1);  
        for(int i=0; i<=8000; i++)  
            if(num[i])  
                printf("%d %d\n",i,num[i]);  
        puts("");  
    }  
    return 0;  
}

HDU5239 Doom(线段树，区间更新，区间平方)

首先说题意，给了n个数，有m次询问，定义一个和为sum=0,每次询问一个区间[a,b]的和+sum，在输出这个区间的和之后，把这个区间的每个数变成自己的平方，然后对9223372034707292160这个数取模

因为模数太大，所以要在进行平方的时候用到快速乘法，用unsigned long long来进行输入输出，我们有一个规律，一个数一直平方，在平方到一定的次数以后，这个数对模数取模的值就不会改变了，所以我们用一个flag数组记录一下这个区间的值还改不改变，当flag=1时就代表已经不变了，就不用去更新了提交选择G++

#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const ll N=1e5+20;
const ll mod=9223372034707292160ull;
ll sum[N<<2];
int flag[N<<2];
void pushup(ll rt)
{
    sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;
    flag[rt]=flag[rt<<1]&flag[rt<<1|1];
}
void build(ll l,ll r,ll rt)
{
    if(l==r)
    {
        scanf("%llu",&sum[rt]);
        flag[rt]=0;
        return;
    }
    ll m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
ll q_mul(ll a,ll b)
{
    ll ans=0;
    while(b)
    {
        if(b&1)
        {
            ans=(ans+a)%mod;
        }
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}
void update(ll a,ll b,ll l,ll r,ll rt)
{
    if(flag[rt])return;
    if(l==r)
    {
        ll tmp=q_mul(sum[rt],sum[rt]);
        if(tmp==sum[rt])
            flag[rt]=1;
        sum[rt]=tmp;
        return;
    }
    ll m=(l+r)>>1;
    if(a<=m)
        update(a,b,lson);
    if(b>m)
        update(a,b,rson);
    pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
    if(L<=l&&r<=R)
        return sum[rt];
    ll m=(l+r)>>1;
    ll ans=0;
    if(L<=m)
        ans=(ans+query(L,R,lson))%mod;
    if(R>m)
        ans=(ans+query(L,R,rson))%mod;
    return ans;
}
int main()
{
    ll t,n,m,q=1,x;
    scanf("%llu",&t);
    while(t--)
    {
        scanf("%llu%llu",&n,&m);
        build(1,n,1);
        ll sum=0,a,b;
        printf("Case #%llu:\n",q++);
        while(m--)
        {
            scanf("%llu%llu",&a,&b);
            sum=(sum+query(a,b,1,n,1))%mod;
            printf("%llu\n",sum);
            update(a,b,1,n,1);
        }
    }
    return 0;
}

洛谷-P3373 线段树 2(线段树,区间更新,lazy标记)

如题，已知一个数列，你需要进行下面三种操作：

1.将某区间每一个数乘上x

2.将某区间每一个数加上x

3.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间[x,y]内每个数乘上k

操作2：格式：2 x y k 含义：将区间[x,y]内每个数加上k

操作3：格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果

输出格式：

输出包含若干行整数，即为所有操作3的结果。

输入输出样例
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
输出样例#1：
17
2

思路:

这个题数据特别大，在有区间加法的同时，还增加了区间乘法,这就是难度增大了

引用:milkfilling的题解

面对这两种操作，可以联想到线段树的一个非常好的功能就是lazytag，只计算出确实需要访问的区间的真实值，其他的保存在lazytag里面，这样可以近似O(NlogN)的运行起来。在尝试着写了只有一个lazetag的程序之后我们发现一个lazytag是不能够解决问题的，那就上两个，分别表示乘法意义上的lazytag和加法意义上的lazytag。紧接着想到pushdown操作之后我们又发现必须在向下传递lazytag的时候人为地为这两个lazytag规定一个先后顺序，排列组合一下只有两种情况：

①加法优先，即规定好segtree[root2].value=((segtree[root2].value+segtree[root].add)*segtree[root].mul)%p，问题是这样的话非常不容易进行更新操作，假如改变一下add的数值，mul也要联动变成奇奇怪怪的分数小数损失精度，我们内心是很拒绝的；

②乘法优先，即规定好segtree[root2].value=(segtree[root2].valuesegtree[root].mul+segtree[root].add(本区间长度))%p，这样的话假如改变add的数值就只改变add，改变mul的时候把add也对应的乘一下就可以了，没有精度损失，看起来很不错。

所以我们在线段树pushdown向下更新的时候,先更新区间和的左右儿子，根据我们规定的优先度，儿子的值=此刻儿子的值*爸爸的乘法lazy+儿子的区间长度*爸爸的加法lazy，然后再分别维护乘法的lazy和加法的lazy，最后取消标记

在update更新的时候，当更新到乘法的时候，需要更新区间和，乘法lazy和加法lazy;当更新加法的时候，只需要更新区间和和加法的lazy就可以了。

还有不要忘记对p取模,数据很大需要用到long long

代码:

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem(a,b) mem(a,b,sizeof(a))
typedef long long ll;
const ll N=100000+20;
ll mul[N<<2],add[N<<2];//两个lazy标记
ll sum[N<<2],p;
void pushup(ll rt)
{
    sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p;
}
void build(ll l,ll r,ll rt)
{
    mul[rt]=1;
    add[rt]=0;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        sum[rt]%=p;
        return;
    }
    ll m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void pushdown(ll l,ll r,ll rt)
{
    ll m=(l+r)>>1;
    sum[rt<<1]=(sum[rt<<1]*mul[rt]+add[rt]*(m-l+1))%p;
    sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt]+add[rt]*(r-m))%p;
    //维护lazy
    mul[rt<<1]=(mul[rt<<1]*mul[rt])%p;
    mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%p;
    add[rt<<1]=(add[rt<<1]*mul[rt]+add[rt])%p;
    add[rt<<1|1]=(add[rt<<1|1]*mul[rt]+add[rt])%p;
    //初始化父节点的lazy
    mul[rt]=1;
    add[rt]=0;
}
void update1(ll L,ll R,ll k,ll l,ll r,ll rt)//乘法
{
    if(L<=l&&r<=R)
    {
        sum[rt]=(sum[rt]*k)%p;
        mul[rt]=(mul[rt]*k)%p;
        add[rt]=(add[rt]*k)%p;
        return;
    }
    pushdown(l,r,rt);
    ll m=(l+r)>>1;
    if(L<=m) update1(L,R,k,lson);
    if(R>m) update1(L,R,k,rson);
    pushup(rt);
    return;
}
void update2(ll L,ll R,ll k,ll l,ll r,ll rt)//加法
{
    if(L<=l&&r<=R)
    {
        add[rt]=(add[rt]+k)%p;
        sum[rt]=(sum[rt]+k*(r-l+1))%p;
        return;
    }
    ll m=(l+r)>>1;
    pushdown(l,r,rt);
    if(L<=m) update2(L,R,k,lson);
    if(R>m) update2(L,R,k,rson);
    pushup(rt);
    return;
}
ll query(ll L,ll R,ll l,ll r,ll rt)
{
    if(L<=l&&r<=R)
        return sum[rt];
    ll m=(l+r)>>1;
    pushdown(l,r,rt);
    ll ans=0;
    if(L<=m) ans=(ans+query(L,R,lson))%p;
    if(R>m) ans=(ans+query(L,R,rson))%p;
    return ans;
}
int main()
{
    ll n,m;
    scanf("%lld%lld%lld",&n,&m,&p);
    build(1,n,1);
    ll x,y,k,op;
    for(ll i=1; i<=m; i++)
    {
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            update1(x,y,k,1,n,1);
        }
        else if(op==2)
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            update2(x,y,k,1,n,1);
        }
        else
        {
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(x,y,1,n,1));
        }
    }
    return 0;
}

POJ3667 Hotel(线段树区间合并+lazy标记)

首先说明题意：有一个旅馆，里面有n个房间,刚开始所有的房间都是空的，现在给你一个m，接下来有m行，每行第一个数op是操作,当操作值为1的时候,说明现在有一个查询，第二个数k代表要在旅馆要开连续的k个房间，如果可以开房，那就输出这k个房间的第一个房间的位置，如果旅馆住不下就输出0.当操作数op为2的时候，接下来给出两个数l,r代表一个区间以l为起点，从l从左往右数r个位置的人退房，也就是清空这个区间。

首先暴力不可取，利用线段树做，当时学线段树的时候太懒了，没学区间合并，导致今天凉了，所以还是要补一补相关知识...

因为是区间问题，所以肯定要用到lazy标记，还需要额外三个数组：

msum[rt]:当前端点代表的区间最大连续空房间的个数
lsum[rt]:当前端点代表的区间从左到右最大连续空房间的个数
rsum[rt]:当前端点代表的区间从右到左最大连续空房间的个数
cover[rt]:lazy标记，-1代表不操作,0代表此区间置空,1代表置满

先说明cover标记一共有3个值，-1代表没有操作，1代表要住人，0代表退房

在更新的时候可以通过c的值来直接对rsum,lsum,msum进行赋值，还要给相关节点打上lazy标记。先向下更新，在回溯的时候向上更新，向下更新的时候和普通的线段树基本一样，在向上更新的时候要注意，先更新当前端点从左到右的左子树和从右到左的右子树，当lsum左子树区间住满的时候，证明还可以住人，就加上它右子树区间的值，当rsum的右子树区间住满的时候，就可以加上左子树区间的值

查询的时候，先找msum左儿子是否足够，然后如果不够就找lsum左儿子的右区间和rsum右儿子的左区间的和是否足够，如果两个都不够的话就找右儿子（这个时候右儿子就肯定满足了）。

具体看代码...

代码

#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
const int N=50000+20;
int lsum[N<<2],rsum[N<<2],msum[N<<2],cover[N<<2];
/*
msum[rt]:当前端点代表的区间最大连续空房间的个数
lsum[rt]:当前端点代表的区间从左到最大连续空房间的个数
rsum[rt]:当前端点代表的区间从右到左最大连续空房间的个数
cover[rt]:lazy标记，-1代表不操作,0代表此区间置空,1代表置满
*/
void pushup(int rt,int m)//向上更新
{
    //更新当前端点从左到右的左子树和从右到左的右子树
    lsum[rt]=lsum[rt<<1];
    rsum[rt]=rsum[rt<<1|1];
    if(lsum[rt]==m-(m>>1))//当左子树区间住满
        lsum[rt]+=lsum[rt<<1|1];
    if(rsum[rt]==(m>>1))//当右子树区间住满
        rsum[rt]+=rsum[rt<<1];
    //这个大区间连续的个数为:这个区间的左右子树的最大连续长度和从左到右的右子树+从右到左的左子树
    msum[rt]=max(lsum[rt<<1|1]+rsum[rt<<1],max(msum[rt<<1],msum[rt<<1|1]));
}
void pushdown(int rt,int m)
{
    if(~cover[rt])//当存在延迟标记
    {
        cover[rt<<1]=cover[rt<<1|1]=cover[rt];
        msum[rt<<1]=lsum[rt<<1]=rsum[rt<<1]=cover[rt]?0:m-(m>>1);
        msum[rt<<1|1]=lsum[rt<<1|1]=rsum[rt<<1|1]=cover[rt]?0:(m>>1);
        cover[rt]=-1;
    }
}
void build(int l,int r,int rt)
{
    cover[rt]=-1;
    lsum[rt]=rsum[rt]=msum[rt]=r-l+1;
    if(l==r) return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void update(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        msum[rt]=lsum[rt]=rsum[rt]=c?0:r-l+1;//如果要增加人,就变成0,如果是消去人,就变成区间的长度
        cover[rt]=c;//进行lazy标记
        return;
    }
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(R>m) update(L,R,c,rson);
    pushup(rt,r-l+1);
}
int query(int w,int l,int r,int rt)//查询能放下w个位置的最左端点
{
    if(l==r) return l;
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if(msum[rt<<1]>=w)
        return query(w,lson);
    else if(rsum[rt<<1]+lsum[rt<<1|1]>=w)//从右到左连续的左子树 +从左到右连续的右子树
        return m-rsum[rt<<1]+1;
    else
        return query(w,rson);
}
int main()
{
    int n,m,op,k,a,b;
    while(~scanf("%d%d",&n,&m))
    {
        build(1,n,1);
        while(m--)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d",&k);
                if(msum[1]<k)//当整个区间连续房间数小于k时
                    puts("0");
                else
                {
                    int p=query(k,1,n,1);//查询最小的房间位置
                    printf("%d\n",p);
                    update(p,p+k-1,1,1,n,1);//更新区间[p,p+k-1]
                }
            }
            else if(op==2)
            {
                scanf("%d%d",&a,&b);
                update(a,a+b-1,0,1,n,1);//更新区间[a,a+b-1]
            }
        }
    }
    return 0;
}

CodeForces - 877E Danil and a Part-time Job(线段树区间异或,lazy标记，dfs序)

首先说明题意，给你了一个有n个节点的树，给出方式是给出从[2,n]的父亲，树中的每个节点有一个灯，有亮的也有灭的，题目在第二行给出，用1表示亮灯，用0表示灭灯，然后有两种操作:

pow x：表示把x以及x的子树的等变为相反状态，其实也就是异或操作
get x:表示求出x及x的子树节点中亮灯的个数

首先我们可以用dfs先预处理出每个树中的每个节点到达时的编号in[i]和返回这个节点的编号out[i]，然后可以利用这个编号来建立一棵线段树，线段树维护的是区间亮灯的个数。

当对一个区间进行异或操作的时候，我们知道这个区间内的总点数，那么每个值变成自己的异或值之后，区间的和就变成了区间的数的个数减去区间原本为1的个数。

因为是区间问题，所以要用到lazy标记，当要对每一个区间进行异或的时候，先给这个区间的lazy进行异或操作，等到需要更新子区间的时候再下放lazy.

const int N=200000+20;
int in[N],out[N],a[N],times,x;
int sum[N<<2],lazy[N<<2];
vector<int>e[N];
void dfs(int rt)
{
    in[rt]=times;
    for(auto i:e[rt])
    {
        times++;
        dfs(i);
    }
    out[rt]=times;
}
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int m)
{
    if(lazy[rt])
    {
        lazy[rt<<1]^=lazy[rt];
        lazy[rt<<1|1]^=lazy[rt];
        sum[rt<<1]=(m-(m>>1))-sum[rt<<1];
        sum[rt<<1|1]=(m>>1)-sum[rt<<1|1];
        lazy[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=0;
    if(l==r)
    {
        sum[rt]=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]^=1;
        sum[rt]=(r-l+1)-sum[rt];
        return;
    }
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,lson);
    if(R>m) update(L,R,rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
        return sum[rt];
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    int ans=0;
    if(L<=m) ans+=query(L,R,lson);
    if(R>m) ans+=query(L,R,rson);
    return ans;
}
int main()
{
    char s[5];
    int n,q;
    times=1;
    scanf("%d",&n);
    for(int i=2; i<=n; i++)
    {
        scanf("%d",&x);
        e[x].push_back(i);
    }
    dfs(1);
    for(int i=1; i<=n; i++)scanf("%d",&a[in[i]]);
    build(1,n,1);
    scanf("%d",&q);
    while(q--)
    {
        scanf("%s%d",s,&x);
        if(s[0]=='g') printf("%d\n",query(in[x],out[x],1,n,1));
        else update(in[x],out[x],1,n,1);
    }
    return 0;
}

区间更新

线段树---区间更新

输入输出格式

输入输出样例

代码

results matching ""

No results matching ""