[关闭]
@lunar 2016-04-08T13:17:54.000000Z 字数 3314 阅读 1445

HiHo一下 Week22 更复杂的房屋买卖姿势

HiHo一下的合集参见这里，不断更新
HiHo

描述

在这个游戏里，会不断的发生如下两种事件：一种是房屋自发的涨价或者降价，而另一种是政府有关部门针对房价的硬性调控。房价的变化自然影响到小Hi和小Ho的决策，所以他们希望能够知道任意时刻某个街道中所有房屋的房价总和是多少——但是很不幸的，游戏本身并不提供这样的计算。不过这难不倒小Hi和小Ho，他们将这个问题抽象了一下，成为了这样的问题：

小Hi和小Ho所关注的街道的长度为N米，从一端开始每隔1米就有一栋房屋，依次编号为0..N，在游戏的最开始，每栋房屋都有一个初始价格，其中编号为i的房屋的初始价格为p_i，之后共计发生了M次事件，所有的事件都是对于编号连续的一些房屋发生的，其中第i次事件如果是房屋自发的涨价或者降价，则被描述为三元组(L_i, R_i, D_i)，表示编号在[L_i, R_i]范围内的房屋的价格的增量（即正数为涨价，负数为降价）为D_i；如果是政府有关部门针对房价的硬性调控，则被描述为三元组(L_i, R_i, V_i)，表示编号在[L_i, R_i]范围内的房屋的价格全部变为V_i。而小Hi和小Ho希望知道的是——每次事件发生之后，这个街道中所有房屋的房价总和是多少。

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为两个整数N、M，分别表示街道的长度和总共发生的事件数。

每组测试数据的第2行为N+1个整数，其中第i个整数位p_i，表示编号为i的房屋的初始价格。

每组测试数据的第3-M+2行，按照发生的时间顺序，每行描述一个事件，如果该行描述的事件为，“房屋自发的涨价或者降价”，则该行为4个整数0, L_i, R_i, D_i，意义如前文所述；如果该行描述的事件为“政府有关部门针对房价的硬性调控”，则该行为4个整数1, L_i, R_i, V_i，意义如前文所述。

对于100%的数据，满足N<=10^5，1<=p_i, |D_i|, V_i<=10^4，0<=l_i < r_i <= n。

对于100%的数据，满足在任意时刻，任何房屋的价格都处于[1, 10^4]内。

输出

对于每组测试数据，输出M行，其中第i行为一个整数Ans_i，表示第i次事件发生之后，这个街道中所有房屋的房价总和。

样例

  1. //样例输入
  2. 10 6
  3. 3195 2202 4613 3744 2892 4858 619 5079 9478 7366 8942 
  4. 0 1 6 886
  5. 1 0 2 9710
  6. 1 0 10 7980
  7. 0 4 9 -7594
  8. 0 2 8 1581
  9. 0 4 4 -1010
  10. //样例输出
  11. 58304
  12. 75652
  13. 87780
  14. 42216
  15. 53283
  16. 52273

思路

这个题目一看，又是用线段树，但是这里比较复杂的是有两种不同的操作，其中难点就在于搞清这两种操作的关系，我们还是用懒惰标记来维护线段树，但是由于操作有两种，所以要分为两个懒惰标记。一个是sflag一个是cflag。s表示设置价格，c表示浮动价格。
每次更新到某个节点时会出现以下情况：

  1. 节点无任何懒惰标记 那么就检测该节点区间是否包含于要修改的区间，即这个区间内的点是否全部要修改，是的话就进行修改并置相应懒惰标记，否则遍历其子节点，等其子节点遍历完再用子节点信息更新这个节点。
  2. 节点有set标记，那先要把这个标记向下传递。传递过程中要注意，set标记是可以覆盖子节点add(cflag)标记的。然后接下来该节点的懒惰标记去除之后就按照1的步骤继续。
  3. 节点有add标记 ，那么同样传递标记，传递时会发现，add标记不能覆盖set但是会对原有的add标记进行叠加（所以这里add标记初始化应该为0，我初始化为-1了一开始，。，检查了老半天）。然后继续1中操作。
  4. 节点既有set，又有add标记。这个要理清了，一定要先处理传递set再传递add，如果反了那么add的信息就会被set覆盖。有人可能会问，有没有可能输入里面就是同一个区间先给add一个再set？当然可能，这就是第2种可能，我们已经做了如果在add基础上来了set就用set覆盖的处理，所以如果两种懒惰标记都有的话，一定是执行set再执行add。

最后每次更新完之后输出根节点的值就可以了。

代码

  1. #include<iostream>
  2. using namespace std;
  4. #define MAX 100005
  5. #define lchild p<<1
  6. #define rchild p<<1|1
  8. int tree[3*MAX];
  9. int cflag[3*MAX];
  10. int sflag[3*MAX];
  11. int price[MAX];
  12. void buildTree(int l, int r, int p){
  13.     if(l==r){
  14.         tree[p] = price[l];
  15.         cflag[p] = 0;
  16.         sflag[p] = -1;  
  17.         return ;
  18.     }
  19.     int m = (l+r)>>1;
  20.     buildTree(l,m,lchild);
  21.     buildTree(m+1,r,rchild);
  22.     tree[p] = tree[lchild] + tree[rchild];
  23.     cflag[p] = 0;
  24.     sflag[p] = -1;
  25. }
  26. void release(int l, int r,int p){
  27.     if(l!=r){
  28.         int m = (l+r)>>1;
  29.         if(sflag[p] != -1){
  30.             sflag[lchild] = sflag[p];
  31.             sflag[rchild] = sflag[p];
  32.             cflag[lchild] = 0;
  33.             cflag[rchild] = 0;
  34.             tree[lchild] = (m-l+1) * sflag[p];
  35.             tree[rchild] = (r-m) * sflag[p];
  36.             sflag[p] = -1;
  37.         }
  38.         if(cflag[p] != 0){
  39.             tree[lchild] += (m-l+1) * cflag[p];
  40.             tree[rchild] += (r-m) * cflag[p];
  41.             cflag[lchild] += cflag[p];
  42.             cflag[rchild] += cflag[p];          
  43.             cflag[p] = 0;
  44.         }
  45.     }
  46. }
  47. void setupdate(int l, int r, int v, int L, int R, int p){
  48.     if(L==R){
  49.         tree[p] = v;
  50.         cflag[p] = 0;
  51.         sflag[p] = -1;
  52.         return;
  53.     }
  54.     if(sflag[p]!=-1||cflag[p]!=0) release(L,R,p);
  55.     if(l<=L&&r>=R){
  56.         tree[p] = (R-L+1) * v;
  57.         sflag[p] = v;
  58.         cflag[p] = 0;
  59.         return;
  60.     }
  61.     int M = (L+R)>>1;
  62.     if(l<=M) setupdate(l,r,v,L,M,lchild);
  63.     if(r>M) setupdate(l,r,v,M+1,R,rchild);
  64.     tree[p] = tree[lchild] + tree[rchild];
  65.     return ;
  66. }
  67. void addupdate(int l, int r, int v, int L, int R, int p){
  68.     if(L==R){
  69.         tree[p] += v;
  70.         cflag[p] = 0;
  71.         sflag[p] = -1;
  72.         return;
  73.     }
  74.     if(sflag[p]!=-1||cflag[p]!=0) release(L,R,p);
  75.     if(l<=L&&r>=R){
  76.         tree[p] += (R-L+1) * v;
  77.         sflag[p] = -1;
  78.         cflag[p] += v;
  79.         return;
  80.     }   
  81.     int M = (L+R)>>1;
  82.     if(l<=M) addupdate(l,r,v,L,M,lchild);
  83.     if(r>M) addupdate(l,r,v,M+1,R,rchild);
  84.     tree[p] = tree[lchild] + tree[rchild];
  85.     return ;
  86. }
  87. int main(){
  88.     int n,m;
  89.     cin >> n >> m;
  90.     for(int i=0;i<=n;i++) cin >> price[i];
  91.     buildTree(0,n,1);
  92.     while(m--){
  93.         int a,b,c,d;
  94.         cin >> a >> b >> c >> d;
  95.         if(a)setupdate(b,c,d,0,n,1);
  96.         else addupdate(b,c,d,0,n,1);
  97.         cout << tree[1]<<endl;
  98. //      cout << endl;
  99. //      show(0,n,1);
  100. //      cout <<endl;
  102.     }
  103.     return 0;
  104. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注