HDU - 4578 线段树+三重操作-白红宇

HDU - 4578 线段树+三重操作

阅读量：6242 次

发布时间：2019-06-22

本文共 3424 字，大约阅读时间需要 11 分钟。

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

先上一篇大佬的题解： (既简单又高效代码还短！%%%)

先说下题意：

　　就是给你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 << 2];

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

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

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

　　三.懒惰值的传递

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

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

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

　　四.数据的更新

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

　　　有三种情况：

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

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

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

下面上代码：

#include 
     
      #include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #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 << 2];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 = 0, tree[k].dif = true;//初始化，每一个区间肯定都是全等的 if (l == r)return; int mid = (l + r) >> 1; built(l, mid, left); built(mid + 1, 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 == 1) { //操作一，加上c tree[k].val = (tree[k].val + c) % mod; } else if (op == 2) { //操纵二，乘以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) >> 1; 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 + 1); ans = (ans + temp) % mod; return; } if (tree[k].dif)down(k);//如果该区间是全等区间，那么就要传递懒惰值,并且传递后该区间肯定是 ”全等区间“ int mid = (tree[k].l + tree[k].r) >> 1; if (x <= mid)query(left); if (y > mid)query(right);}int main() { while (scanf("%d%d", &n, &m) != EOF && n && m) { built(1, n, 1); for (int i = 1; i <= m; i++) { scanf("%d%d%d%d", &op, &x, &y, &c); if (op == 4) { ans = 0; query(1); cout << ans << endl; } else { updata(1); } } } return 0;}

转载于:https://www.cnblogs.com/caibingxu/p/10821750.html

你可能感兴趣的文章