HDU - 4578 线段树+三重操作

这道题自己写了很久，还是没写出来，也看了很多题解，感觉多数还是看的迷迷糊糊，最后面看到一篇大佬的才感觉恍然大悟。

先上一篇大佬的题解：https://blog.csdn.net/aqa2037299560/article/details/82872866?tdsourcetag=s_pcqq_aiomsg (既简单又高效代码还短！%%%)

先说下题意：

　　就是给你n个数，每个数的初始值都是为0

　　然后给你m个操作

　　每个操作有 4 个数 op x y c

　　当 op==1 的时候，把 x到y 范围内的数都加上 c

　　当 op==2 的时候，把 x到y 范围内的数都乘以 c

　　当 op==3 的时候，把 x到y 范围内的数都等于 c

　　当 op==4 的时候，把 x到y 范围内的每一个数的 c 次方的和输出（注意，当op等于4的时候，c的范围为1~3)

下面说说思路：

　　关键就是在于这个懒惰值的传递，和区间的每一个值是否都相等的问题

　　一.先说说树的数据

　　　这个大家参考下就可以，实现的方法有很多，不一定需要这么写，把这个先放上来是便于理解。（我这么写是因为我太菜了）

　　　　struct Data {

   　　 　　ll l, r, val;//分别是左边界，右边界，懒惰值（也是该区间每一个叶节点的值）

    　　　　bool dif;//判断区间内每一个区间是否的相同

　　　　}tree[M << ];

　　二.再说这个区间值都相等

　　　我们可以知道，如果区间内的每一个值都相等，那么我们只要求其中一个的值的c次方，然后把该数乘以（右边界减去左边界再加 1 ），便是该区间值的次方总和了

　　　如果该区间的每一个值不相等，那么我们必须接着向下探索，直到找到一个区间内的每一个值都相等的区间，最坏的情况也就是找到叶节点。

　　三.懒惰值的传递

　　　如果这个区间的每一个值都相等，那么它的左右子区间肯定也都是相等的。

　　　如果这个区间不是全等区间，那么我们就没必要传递懒惰值，因为你这个区间每一个值不一定相等 ; 但是如果是全等区间，就要传递懒惰值。

　　　如果我们在更新数据的过程中，需要用到传递懒惰值，那么肯定是要修改这个区间的某一个子区间，所以传递后，这个区间肯定不会再是全等区间

　　四.数据的更新

　　　我们在更新完值后，肯定也需要更新区间是否相等的信息

　　　有三种情况：

　　　　　　1.如果该区间的左右子区间都不是全等区间的话，那这个区间肯定也不是全等区间

　　　　　　2.如果该区间的左右子区间都是全等区间，但是它们的叶节点的值都不相等，那么这个区间肯定也不是全等区间

　　　　　　3.如果该区间的左右区间都是全等区间，并且它们的叶节点的值都全等，那么这个区间肯定是全等区间

下面上代码：

#include <algorithm>

#include <iostream>

#include<sstream>

#include<iterator>

#include<cstring>

#include<string>

#include<cstdio>

#include<cctype>

#include<vector>

#include<deque>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define M 100005

#define mod 10007

#define inf 0x3f3f3f3f

#define left k<<1

#define right k<<1|1

#define ms(a,b) memset(a,b,sizeof(a))

typedef long long ll;

using namespace std;

struct Data {

    ll l, r, val; // 分别是左边界，右边界，懒惰值（也是该区间每一个叶节点的值

    bool dif;//判断区间内每一个区间是否的相同

}tree[M << ];

ll ans, temp;

ll op, c, p;

int x, y, n, m;

void built(int l, int r, int k) {

    tree[k].l = l, tree[k].r = r, tree[k].val = , tree[k].dif = true;//初始化，每一个区间肯定都是全等的

    if (l == r)return;

    int mid = (l + r) >> ;

    built(l, mid, left);

    built(mid + , r, right);

}

void down(int k) {

    if (tree[k].l == tree[k].r)return;//如果这个数就是子区间那么没必要往下传递了

    tree[k].dif = false;//传递后可能不是全等区间了

    tree[left].val = tree[right].val = tree[k].val;//传递懒惰值

    tree[left].dif = tree[right].dif = true;//暂时都是全等区间

}

void updata(int k) {

    if (tree[k].l >= x && tree[k].r <= y && tree[k].dif) {//在要操作的区间范围内，并且是全等区间就可以直接操作

        if (op == ) {//操作一，加上c

            tree[k].val = (tree[k].val + c) % mod;

        }

        else if (op == ) {//操纵二，乘以c

            tree[k].val = (tree[k].val * c) % mod;

        }

        else {//操作三，等于c

            tree[k].val = c % mod;

        }

        return;

    }

    if (tree[k].dif)down(k);//如果该区间是全等区间，那么就要传递懒惰值,并且传递后该区间肯定是 不全等区间

    int mid = (tree[k].l + tree[k].r) >> ;

    if (x <= mid)updata(left);

    if (y > mid)updata(right);

    //传递后三种情况分析更新

    if (!tree[left].dif || !tree[right].dif)tree[k].dif = false;

    else {

        if (tree[left].val != tree[right].val)tree[k].dif = false;

        else {

            tree[k].dif = true;

            tree[k].val = tree[left].val;

        }

    }

}

void query(int k) {

    if (tree[k].l >= x && tree[k].r <= y && tree[k].dif) {//如果是全等区间，那么每一个数的值都相等

        temp = pow(tree[k].val, c);

        temp *= (tree[k].r - tree[k].l + );

        ans = (ans + temp) % mod;

        return;

    }

    if (tree[k].dif)down(k);//如果该区间是全等区间，那么就要传递懒惰值,并且传递后该区间肯定是 ”全等区间“

    int mid = (tree[k].l + tree[k].r) >> ;

    if (x <= mid)query(left);

    if (y > mid)query(right);

}

int main() {

    while (scanf("%d%d", &n, &m) != EOF && n && m) {

        built(, n, );

        for (int i = ; i <= m; i++) {

            scanf("%d%d%d%d", &op, &x, &y, &c);

            if (op == ) {

                ans = ;

                query();

                cout << ans << endl;

            }

            else {

                updata();

            }

        }

    }

    return ;

}

巴特西

HDU - 4578 线段树+三重操作

最新文章

热门文章