首页 > 代码库 > 线段树复习
线段树复习
#1080 : 更为复杂的买卖房屋姿势
- 样例输入
10 6 3195 2202 4613 3744 2892 4858 619 5079 9478 7366 8942 0 1 6 886 1 0 2 9710 1 0 10 7980 0 4 9 -7594 0 2 8 1581 0 4 4 -1010
- 样例输出
58304 75652 87780 42216 53283 52273
描述
小Hi和小Ho都是游戏迷，“模拟都市”是他们非常喜欢的一个游戏，在这个游戏里面他们可以化身上帝模式，买卖房产。
在这个游戏里，会不断的发生如下两种事件：一种是房屋自发的涨价或者降价，而另一种是政府有关部门针对房价的硬性调控。房价的变化自然影响到小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次事件发生之后，这个街道中所有房屋的房价总和。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e5+10;
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
#define MID(a,b) ((a+b)>>1)
int sum[maxn<<2],addv[maxn<<2],setv[maxn<<2],sz[maxn<<2];
int ql,qr,op,x;
void push_up(int o)
{
sum[o]=sum[lc(o)]+sum[rc(o)];
}
void Modify_add(int o,int val)
{
addv[o]+=val;
sum[o]+=val*sz[o];
}
void Modify_set(int o,int val)
{
setv[o]=val;
addv[o]=0;
sum[o]=val*sz[o];
}
void push_down(int o)
{
if(setv[o]){
Modify_set(lc(o),setv[o]);
Modify_set(rc(o),setv[o]);
setv[o]=0;
}if(addv[o]){
Modify_add(lc(o),addv[o]);
Modify_add(rc(o),addv[o]);
addv[o]=0;
}
}
void built(int o,int L,int R)
{
setv[o]=addv[o]=0;
sz[o]=(R-L+1);
if(L==R){
scanf("%d",sum+o);
return ;
}
int mid=MID(L,R);
built(lc(o),L,mid);
built(rc(o),mid+1,R);
push_up(o);
}
void Modify(int o,int L,int R)
{
if(ql<=L&&qr>=R){
if(op)Modify_set(o,x);
else Modify_add(o,x);
return ;
}
int mid=MID(L,R);
push_down(o);
if(ql<=mid)Modify(lc(o),L,mid);
if(qr>mid)Modify(rc(o),mid+1,R);
push_up(o);
}
int Query(int o,int L,int R)
{
if(ql<=L&&qr>=R){
return sum[o];
}
int mid=MID(L,R),ans=0;
push_down(o);
if(ql<=mid)ans+=Query(lc(o),L,mid);
if(qr>mid)ans+=Query(rc(o),mid+1,R);
push_up(o);
return ans;
}
int main(int argc, char const *argv[])
{
int n,m;
while(~scanf("%d%d",&n,&m)){
++n;
built(1,1,n);
while(m--){
scanf("%d%d%d%d",&op,&ql,&qr,&x);
ql++,qr++;
Modify(1,1,n);
ql=1,qr=n;
printf("%d\n",Query(1,1,n));
}
}
return 0;
}线段树复习