专题七：线段树 / 线段树

 

Yuanfang is puzzled with the question below:
There are n integers, a 1, a 2, …, a n. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between a x and a y inclusive. In other words, do transformation a k<—a k+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between a x and a y inclusive. In other words, do transformation a k<—a k×c, k = x,x+1,…,y.
Operation 3: Change the numbers between a x and a y to c, inclusive. In other words, do transformation a k<—c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between a x and a y inclusive. In other words, get the result of a x p+a x+1 p+…+a y p.
Yuanfang has no idea of how to do it. So he wants to ask you to help him.

Input

There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines contains an operation. Operation 1 to 3 is in this format: “1 x y c” or “2 x y c” or “3 x y c”. Operation 4 is in this format: “4 x y p”. (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)
The input ends with 0 0.
Output

For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.Sample Input

5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3
0 0

Sample Output

307
7489
  • 题意
    • 三种区间修改：
      • add  l r d
      • mul l r d
      • set l r d（将值置为d）
    • 三种查询
      • 区间和
      • 区间平方和
      • 区间立方和
  • 题解
    • 同值标记
      • 这题和http://47.106.118.63/2019/05/03/hdu-4027/b本质上是一类问题
      • 只不过4027只需要一种修改（开方）和一种查询（区间和）
      • 由于4027开方操作的特殊性，它的区间返回标记不是显式的，而是sum=r-l+1
      • 如果要改为显式的，可以用更为一般的返回标记——区间内所有值相等标记，而我们最终只会以访问到的区间相等的节点作为访问的最后一层，且该节点中储存着一个值，这个值就是区间内任意一个数的值，当我们求区间和时，只要找到访问的最后一层节点p，返回(r(p)-l(p)+1)*x即可
      • 所以对于本题，也同样维护同值区间即可
      • 而本题中有三种修改，看似很乱，但实际上我们要理解这一点：区间和、平方和、立方和都只和线段树中具体所访问到的最后一层节点值有关，而有关节点之间不互相影响
      • 所以说，只要我们按照线段树的性质去维护，那我们就可以得到答案
      • 具体看代码
      •  代码 
        • #include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 10007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(ll x) {
	if(x<0)putchar('-'),x=-x;
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn = 1e6+10;
struct SegmentTree {
	int l,r;
	long long dat,add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define dat(x) tree[x].dat
#define add(x) tree[x].add
} tree[1000010*4];
int n,q;
void build(int p,int l,int r) {
	l(p)=l,r(p)=r;
	add(p)=1;
	dat(p)=0;
	if(l==r){
		return ;
	}
	int mid=(l+r)/2;//只有这里的一半是直接用传入的l，r，但实际上这里的l，r就是下面的p.l,p.r
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
//延迟标记代表：该节点已经被修改，但子节点尚未被更新
void spread(int p) {
	if(add(p)) {
		add(p*2)=add(p*2+1)=add(p);
		dat(p*2)=dat(p*2+1)=dat(p); 
		add(p)=0;
	}
}
void change(int p,int l,int r,int d,int type) {
	if(add(p) && l<=l(p) && r>=r(p)) { //完成覆盖
		if(type==1)dat(p)=(dat(p)+d)%mod;
		else if(type==2)dat(p)=(dat(p)*d)%mod;
		else dat(p)=d;
		return ;
	}
	spread(p); //下传延迟标记
	int mid=(l(p)+r(p))/2; //这里的中间是当前节点的中间（或者说是偏左的中间）位置
	if(l<=mid)change(p*2,l,r,d,type);
	if(r>mid)change(p*2+1,l,r,d,type);//注意这里不是非此即彼的关系
	//合并区间 
	if(!add(p*2)||!add(p*2+1))add(p)=0;//子段不同一 
	else if(dat(p*2)!=dat(p*2+1))add(p)=0;//左右子段独立同一但不相互同一 
	else add(p)=1,dat(p)=dat(p*2);//合并相邻相同区间 更新区间值 
}
long long ask(int p,int l,int r,int val) {
	if(l<=l(p) && r>=r(p) && add(p)){
		ll ans=1;
		for(int i=1;i<=val;i++)ans=(ans*dat(p))%mod;
		ans=(ans*(r(p)-l(p)+1))%mod;
		return ans;
	}
	spread(p);
	int mid=(l(p)+r(p))/2;
	long long sum=0;
	if(l <= mid) sum+=ask(p*2,l,r,val);//注意！这里对中间元素进行比较的是l不是tree[p].l
	if(r > mid) sum+=ask(p*2+1,l,r,val);
	return sum%mod;
}
int main() {
	while(~scanf("%d%d",&n,&q)&&(n+q))
    {
    	build(1,1,n);
        int x,l,r,val;
        while(q--)
        {
            scanf("%d%d%d%d",&x,&l,&r,&val);
            if(x>=1&&x<=3) change(1,l,r,val,x);
			else printf("%I64d\n",ask(1,l,r,val)); 
        }
    }
    return 0;
}
    • 思维分类标记
      • 这里直接套用https://www.cnblogs.com/H-Vking/p/4297973.html
      • 这道题坑在有三种询问：set , add , mul。所以lazy标记要有三个，如果三个标记同时出现的处理方法——当更新set操作时，就把add标记和mul标记全部取消；当更新mul操作时，如果当前节点add标记存在，就把add标记改为：add * mul。这样的话就可以在PushDown()操作中先执行set，然后mul，最后add。

        麻烦在有三种询问：和 , 平方和 , 立方和。对于set和mul操作来说，这三种询问都比较好弄。

        对于add操作，和的话就比较好弄，按照正常方法就可以；

        平方和这样来推：(a + c)2 = a2 + c2 + 2ac  , 即sum2[rt] = sum2[rt] + (r – l + 1) * c * c + 2 * sum1[rt] * c；

        立方和这样推：(a + c)3 = a3 + c3 + 3a(a2 + ac) , 即sum3[rt] = sum3[rt] + (r – l + 1) * c * c * c + 3 * c * (sum2[rt] + sum1[rt] * c)；

        几个注意点：add标记取消的时候是置0，mul标记取消的时候是置1；在PushDown()中也也要注意取消标记，如set操作中取消add和mul，mul操作中更新add； 在add操作中要注意sum3 , sum2 , sum1的先后顺序，一定是先sum3 , 然后sum2 , 最后sum1； int容易爆，还是用LL要保险一点； 最后就是运算较多，不要漏掉东西。

      • #include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF INT_MAX
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = 10007; 
const int maxn = 100000 + 5;
const int N = 12;
LL add[maxn << 2] , set[maxn << 2] , mul[maxn << 2];
LL sum1[maxn << 2] , sum2[maxn << 2] , sum3[maxn << 2];
void PushUp(int rt)
{
    sum1[rt] = (sum1[rt << 1] + sum1[rt << 1 | 1]) % MOD;
    sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % MOD;
    sum3[rt] = (sum3[rt << 1] + sum3[rt << 1 | 1]) % MOD;
}
void build(int l , int r , int rt)
{
    add[rt] = set[rt] = 0;
    mul[rt] = 1;
    if(l == r) {
        sum1[rt] = sum2[rt] = sum3[rt] = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUp(rt);
}
void PushDown(int rt , int len)
{
    if(set[rt]) {
        set[rt << 1] = set[rt << 1 | 1] = set[rt];
        add[rt << 1] = add[rt << 1 | 1] = 0;    //注意这个也要下放
        mul[rt << 1] = mul[rt << 1 | 1] = 1;
        LL tmp = ((set[rt] * set[rt]) % MOD) * set[rt] % MOD;
        sum1[rt << 1] = ((len - (len >> 1)) % MOD) * (set[rt] % MOD) % MOD;
        sum1[rt << 1 | 1] = ((len >> 1) % MOD) * (set[rt] % MOD) % MOD;
        sum2[rt << 1] = ((len - (len >> 1)) % MOD) * ((set[rt] * set[rt]) % MOD) % MOD;
        sum2[rt << 1 | 1] = ((len >> 1) % MOD) * ((set[rt] * set[rt]) % MOD) % MOD;
        sum3[rt << 1] = ((len - (len >> 1)) % MOD) * tmp % MOD;
        sum3[rt << 1 | 1] = ((len >> 1) % MOD) * tmp % MOD;
        set[rt] = 0;
    }
    if(mul[rt] != 1) {    //这个就是mul[rt] != 1 ， 当时我这里没注意所以TLE了
        mul[rt << 1] = (mul[rt << 1] * mul[rt]) % MOD;
        mul[rt << 1 | 1] = (mul[rt << 1 | 1] * mul[rt]) % MOD;
        if(add[rt << 1])    //注意这个也要下放
            add[rt << 1] = (add[rt << 1] * mul[rt]) % MOD;
        if(add[rt << 1 | 1])
            add[rt << 1 | 1] = (add[rt << 1 | 1] * mul[rt]) % MOD;
        LL tmp = (((mul[rt] * mul[rt]) % MOD * mul[rt]) % MOD);
        sum1[rt << 1] = (sum1[rt << 1] * mul[rt]) % MOD;
        sum1[rt << 1 | 1] = (sum1[rt << 1 | 1] * mul[rt]) % MOD;
        sum2[rt << 1] = (sum2[rt << 1] % MOD) * ((mul[rt] * mul[rt]) % MOD) % MOD;
        sum2[rt << 1 | 1] = (sum2[rt << 1 | 1] % MOD) * ((mul[rt] * mul[rt]) % MOD) % MOD;
        sum3[rt << 1] = (sum3[rt << 1] % MOD) * tmp % MOD;
        sum3[rt << 1 | 1] = (sum3[rt << 1 | 1] % MOD) * tmp % MOD;
        mul[rt] = 1;
    }
    if(add[rt]) {
        add[rt << 1] += add[rt];    //add是+= ， mul是*=
        add[rt << 1 | 1] += add[rt];
        LL tmp = (add[rt] * add[rt] % MOD) * add[rt] % MOD;        //注意sum3 , sum2 , sum1的先后顺序
        sum3[rt << 1] = (sum3[rt << 1] + (tmp * (len - (len >> 1)) % MOD) + 3 * add[rt] * ((sum2[rt << 1] + sum1[rt << 1] * add[rt]) % MOD)) % MOD;
        sum3[rt << 1 | 1] = (sum3[rt << 1 | 1] + (tmp * (len >> 1) % MOD) + 3 * add[rt] * ((sum2[rt << 1 | 1] + sum1[rt << 1 | 1] * add[rt]) % MOD)) % MOD;
        sum2[rt << 1] = (sum2[rt << 1] + ((add[rt] * add[rt] % MOD) * (len - (len >> 1)) % MOD) + (2 * sum1[rt << 1] * add[rt] % MOD)) % MOD;
        sum2[rt << 1 | 1] = (sum2[rt << 1 | 1] + (((add[rt] * add[rt] % MOD) * (len >> 1)) % MOD) + (2 * sum1[rt << 1 | 1] * add[rt] % MOD)) % MOD;
        sum1[rt << 1] = (sum1[rt << 1] + (len - (len >> 1)) * add[rt]) % MOD;
        sum1[rt << 1 | 1] = (sum1[rt << 1 | 1] + (len >> 1) * add[rt]) % MOD;
        add[rt] = 0;
    }
}
void update(int L , int R , int c , int ch , int l , int r , int rt)
{
    if(L <= l && R >= r) {
        if(ch == 3) {
            set[rt] = c;
            add[rt] = 0;
            mul[rt] = 1;
            sum1[rt] = ((r - l + 1) * c) % MOD;
            sum2[rt] = ((r - l + 1) * ((c * c) % MOD)) % MOD;
            sum3[rt] = ((r - l + 1) * (((c * c) % MOD) * c % MOD)) % MOD;
        } else if(ch == 2) {
            mul[rt] = (mul[rt] * c) % MOD;
            if(add[rt])
                add[rt] = (add[rt] * c) % MOD;
            sum1[rt] = (sum1[rt] * c) % MOD;
            sum2[rt] = (sum2[rt] * (c * c % MOD)) % MOD;
            sum3[rt] = (sum3[rt] * ((c * c % MOD) * c % MOD)) % MOD;
        } else if(ch == 1) {
            add[rt] += c;
            LL tmp = (((c * c) % MOD * c) % MOD * (r - l + 1)) % MOD;    //(r - l + 1) * c^3
            sum3[rt] = (sum3[rt] + tmp + 3 * c * ((sum2[rt] + sum1[rt] * c) % MOD)) % MOD;
            sum2[rt] = (sum2[rt] + (c * c % MOD * (r - l + 1) % MOD) + 2 * sum1[rt] * c) % MOD;
            sum1[rt] = (sum1[rt] + (r - l + 1) * c) % MOD;
        }
        return;
    }
    PushDown(rt , r - l + 1);
    int m = (l + r) >> 1;
    if(L > m)
        update(L , R , c , ch , rson);
    else if(R <= m)
        update(L , R , c , ch , lson);
    else {
        update(L , R , c , ch , lson);
        update(L , R , c , ch , rson);
    }
    PushUp(rt);
}
LL query(int L , int R , int p , int l , int r , int rt)
{
    if(L <= l && R >= r) {
        if(p == 1)
            return sum1[rt] % MOD;
        else if(p == 2)
            return sum2[rt] % MOD;
        else
            return sum3[rt] % MOD;
    }
    PushDown(rt , r - l + 1);
    int m = (l + r) >> 1;
    if(L > m)
        return query(L , R , p , rson);
    else if(R <= m)
        return query(L , R , p , lson);
    else 
        return (query(L , R , p , lson) + query(L , R , p , rson)) % MOD;
}
int main()
{
    int n , m;
    int a , b , c , ch;
    while(~scanf("%d %d" , &n , &m))
    {
        if(n == 0 && m == 0)
            break;
        build(1 , n , 1);
        while(m--) {
            scanf("%d %d %d %d" , &ch , &a , &b , &c);
            if(ch != 4) {
                update(a , b , c , ch , 1 , n , 1);
            } else {
                printf("%I64d\n" , query(a , b , c , 1 , n , 1));
            }
        }
    }
    return 0;
}

         

  • 比较一下两种方法
    • 同值标记代码量少，逻辑上更好理解，且适用性好
    • 而思维分类打多种标记，要考虑各种冲突，不易实现
    • 而且思维分类能解决的本类多种修改+多种区间和的问题，同值标记基本也能解决
    • 唯一的问题是题目输入数据怎么给，比如经常访问的是同一性较强的区间，那么第一种方法比较快；当然，第二种方法无论什么时候，都比较慢…(大概当修改完立即询问区间时比较快？)

 

发表评论

邮箱地址不会被公开。 必填项已用*标注