1078 : 线段树的区间修改
题目描述:
对于小Ho表现出的对线段树的理解，小Hi表示挺满意的，但是满意就够了么？于是小Hi将问题改了改，
又出给了小Ho：
假设货架上从左到右摆放了N种商品，并且依次标号为1到N，其中标号为i的商品的价格为Pi
。小Hi的每次操作分为两种可能，第一种是修改价格——小Hi给出一段区间[L, R]和一个新的价格NewP
，所有标号在这段区间中的商品的价格都变成NewP。
第二种操作是询问——小Hi给出一段区间[L, R]，
而小Ho要做的便是计算出所有标号在这段区间中的商品的总价格，然后告诉小Hi。
那么这样的一个问题，小Ho该如何解决呢？
输入描述:
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为一个整数N，意义如前文所述。
每组测试数据的第2行为N个整数，分别描述每种商品的重量，其中第i个整数表示标号为i的商品的重量Pi。
每组测试数据的第3行为一个整数Q，表示小Hi进行的操作数。
每组测试数据的第N+4~N+Q+3行，每行分别描述一次操作，
每行的开头均为一个属于0或1的数字，分别表示该行描述一个询问和一次商品的价格的更改两种情况。
对于第N+i+3行，如果该行描述一个询问，则接下来为两个整数Li, Ri，
表示小Hi询问的一个区间[Li, Ri]；如果该行描述一次商品的价格的更改，
则接下来为三个整数Li，Ri，NewP，表示标号在区间[Li, Ri]的商品的价格全部修改为NewP。
对于100%的数据，满足N<=10^5，Q<=10^5, 1<=Li<=Ri<=N，1<=Pi<=N, 0<Pi, NewP<=10^4。
输出描述:
对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，
表示查询的结果：标号在区间[Li, Ri]中的所有商品的价格之和。
样例输入:
10
4733 6570 8363 7391 4511 1433 2281 187 5166 378
6
1 5 10 1577
1 1 7 3649
0 8 10
0 1 4
1 6 8 157
1 3 4 1557
样例输出
4731
14596
思路:
建树,然后用lazy标记实现logn的修改.
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
struct node{
int left,right;
ll sum,tag;
};//节点记录信息
node Tree[4*maxn];
ll a[maxn];
int num=0;
void Btree(int l,int r,int id){//递归建树
//cout<<id<<endl;
Tree[id].left=l;
Tree[id].right=r;
if(l==r){
Tree[id].sum=a[++num];
//cout<<Tree[id].sum<<" "<<id<<" "<<l<<" "<<r<<endl;
return ;
}
int mid=(Tree[id].left+Tree[id].right)/2;
Btree(l,mid,id<<1);
Btree(mid+1,r,(id<<1)+1);
Tree[id].sum=Tree[id<<1].sum+Tree[(id<<1)+1].sum;
return ;
}
void pushdown(int id){//下放lazy标记
if(Tree[id].tag){
Tree[id<<1].sum=(Tree[id<<1].right-Tree[id<<1].left+1)*Tree[id].tag;
Tree[(id<<1)+1].sum=(Tree[(id<<1)+1].right-Tree[(id<<1)+1].left+1)*Tree[id].tag;
Tree[id<<1].tag=Tree[(id<<1)+1].tag=Tree[id].tag;
Tree[id].tag=0;
}
}
void Uptree(int l,int r,ll w,int id){
if(l<=Tree[id].left&&Tree[id].right<=r){//更新包含在l,r之间的区间,并加上lazy标记,让下次查询或更新子树时可以临时更新.
Tree[id].sum=(Tree[id].right-Tree[id].left+1)*w;
Tree[id].tag=w;
return ;
}
pushdown(id);
if(l<=Tree[id<<1].right){//如果更新的区间在左子树的区间里有涉及就递归更新左子树
Uptree(l,r,w,id<<1);
}
if(r>=Tree[(id<<1)+1].left){//如果更新的区间在右子树的区间里有涉及就递归更新左子树
Uptree(l,r,w,(id<<1)+1);
}
Tree[id].sum=Tree[id<<1].sum+Tree[(id<<1)+1].sum;//返回更新到父节点
return ;
}
ll Query(int l,int r,int id){//和更新一样
if(l<=Tree[id].left&&Tree[id].right<=r){
//cout<<l<<" "<<r<<endl;
return Tree[id].sum;
}
pushdown(id);
ll a=0,b=0;
if(l<=Tree[id<<1].right){
a=Query(l,r,id<<1);
}
if(r>=Tree[(id<<1)+1].left){
b=Query(l,r,(id<<1)+1);
}
Tree[id].sum=Tree[id<<1].sum+Tree[(id<<1)+1].sum;
return a+b;
}
int main(){
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
memset(Tree,0,sizeof(Tree));
Btree(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int q;
scanf("%d",&q);
if(q){
int l,r;
ll w;
scanf("%d%d%lld",&l,&r,&w);
Uptree(l,r,w,1);
}else{
int l,r;
scanf("%d%d",&l,&r);
ll k=Query(l,r,1);
printf("%lld\n",k);
}
}
}
总结:
这是线段树的基本操作,我对于这种高级数据结构还要多多练习,这个要注意的地方是线段树的空间是4*n，我在这里错了好久可以证明。。。
1080:更为复杂的买卖房屋姿势
题目描述：
小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次事件发生之后，这个街道中所有房屋的房价总和。
样例输入：
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
思路：
这个题有两个修改，所以要用到双标记，然后对双标记进行维护。具体维护见代码。
代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int lt,rt,sum;
int sets,add;
};//树的节点信息
const int maxn=1e5+100;
int a[maxn];
node tree[4*maxn];
int num=0;
void build(int l,int r,int id){//建树
tree[id].lt=l;
tree[id].rt=r;
tree[id].sets=0;
tree[id].add=0;
if(l==r){
tree[id].sum=a[++num];
return;
}
int mid=(l+r)>>1;
build(l,mid,id<<1);
build(mid+1,r,id<<1|1);
tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
//cout<<tree[id].sum<<endl;
return ;
}
void pushdown(int id){
if(tree[id].sets){//更据题意set标记会清空add标记但这里只要清空左右子树的，
因为自身的标记在更新的时候被清空了如果还要add标记这意味着add的
修改在set标记的后面不需要清空。
tree[id<<1].sum=(tree[id<<1].rt-tree[id<<1].lt+1)*tree[id].sets;
tree[id<<1|1].sum=(tree[id<<1|1].rt-tree[id<<1|1].lt+1)*tree[id].sets;
tree[id<<1].sets=tree[id<<1|1].sets=tree[id].sets;
tree[id].sets=0;
tree[id<<1].add=tree[id<<1|1].add=0;
}
if(tree[id].add){//这个add标记和一搬的修改维护差不多。
tree[id<<1].sum+=(tree[id<<1].rt-tree[id<<1].lt+1)*tree[id].add;
tree[id<<1|1].sum+=(tree[id<<1|1].rt-tree[id<<1|1].lt+1)*tree[id].add;
tree[id<<1].add+=tree[id].add;
tree[id<<1|1].add+=tree[id].add;
//cout<<tree[id<<1].add<<" "<<tree[id<<1|1].add<<endl;
tree[id].add=0;
}
return ;
}
void update(int t,int l,int r,int w,int id){
if(l<=tree[id].lt&&tree[id].rt<=r){//更据输入的标识来决定那个标记修改
if(t==1){
tree[id].sum=(tree[id].rt-tree[id].lt+1)*w;
tree[id].sets=w;
tree[id].add=0;
}else{
tree[id].sum+=(tree[id].rt-tree[id].lt+1)*w;
tree[id].add+=w;
//cout<<tree[id].lt<<" "<<tree[id].rt<<" "<<tree[id].sum<<endl;
}
return ;
}
pushdown(id);
int mid=(tree[id].lt+tree[id].rt)>>1;
if(l<=mid){
update(t,l,r,w,id<<1);
}
if(r>=mid+1){
update(t,l,r,w,id<<1|1);
}
tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
return ;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n+1;i++)
scanf("%d",&a[i]);
num=0;
build(1,n+1,1);
for(int i=1;i<=m;i++){
int type,l,r,w;
scanf("%d%d%d%d",&type,&l,&r,&w);
update(type,l+1,r+1,w,1);
printf("%d\n",tree[1].sum);
}
return 0;
}
总结：
这是线段树的一种运用，这种题，我现在还做不出，希望训练后有一定的提升。
#1079 : 离散化
题目描述：
小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~
这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，
有些海报就会被其他社团的海报所遮挡住。看到这个场景，
小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？
于是小Ho肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，
所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴在了宣传栏上，
其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示，其中a_i, b_i均为属于[0, L]的整数，
而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。
那么问题就来了：究竟有几张海报能被看到呢？
输入描述：
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为两个整数N和L，分别表示总共贴上的海报数量和宣传栏的宽度。
每组测试数据的第2-N+1行，按照贴上去的先后顺序，每行描述一张海报，
其中第i+1行为两个整数a_i, b_i，表示第i张海报所贴的区间为[a_i, b_i]。
对于100%的数据，满足N<=10^5，L<=10^9，0<=a_i<b_i<=L。
输出描述：
对于每组测试数据，输出一个整数Ans，表示总共有多少张海报能被看到。
样例输入：
5 10
4 10
0 2
1 6
5 9
3 4
样例输出：
5
思路：
一开始我看到题目是无法想到线段树的，后来看到提示我才明白可以用一个标记记录，
如果海报在这个区间整体，可见记录一个标号（标号是递增的），最后只要统计有多少个不同的标号。
但这有个问题是这个叶子点个数和区间长度有关，而l有1e9会炸内存，
但我们有用的信息是区间之间的关系
[1，9]和[2，9] 与 [1，5]和[2，5]的区间关系是一样的。所以我们想到了离散化。
注意的是建树时区间是(l,mid),(mid,r),具体看代码。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
struct node{
int lt,rt,flag;
};
int a[maxn],b[maxn];
vector<int>st;
node tree[4*maxn];
int vis[maxn];
int ans;
int getid(int pos){
int p=lower_bound(st.begin(),st.end(),pos)-st.begin()+1;
return p;
}
void Btree(int l,int r,int id){
tree[id].lt=l;
tree[id].rt=r;
tree[id].flag=0;
if(l+1==r)
return;
int mid=(l+r)>>1;
Btree(l,mid,id<<1);//这是个区间覆盖问题 他的数据是连续的
如果[3，4]和[4，5]区间有海报那么如果 mid+1就不能正确表示出来。
所以这题建树有一定的区别。
Btree(mid,r,id<<1|1);
return ;
}
void update(int l,int r,int x,int id){
if(l==tree[id].lt&&r==tree[id].rt){
tree[id].flag=x;
return ;
}
if(tree[id].lt+1>=tree[id].rt)
return ;
if(tree[id].flag){
tree[id<<1].flag=tree[id<<1|1].flag=tree[id].flag;
tree[id].flag=0;
}
int mid=(tree[id].lt+tree[id].rt)>>1;
if(r<=mid)
update(l,r,x,id<<1);
else if(l>mid)
update(l,r,x,id<<1|1);
else {
update(l,mid,x,id<<1);
update(mid,r,x,id<<1|1);
}
return ;
}
void query(int l,int r,int id){
//cout<<l<<" "<<r<<endl;
//cout<<tree[id].flag<<endl;
if(tree[id].flag&&!vis[tree[id].flag]){
ans++;
vis[tree[id].flag]=1;
}
if(tree[id].lt+1>=tree[id].rt)
return ;
if(!vis[tree[id].flag]){
int mid=(l+r)>>1;
query(l,mid,id<<1);
query(mid,r,id<<1|1);
}
}
int main(){
int n,l;
scanf("%d%d",&n,&l);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
st.push_back(a[i]);
st.push_back(b[i]);
}
sort(st.begin(),st.end());
st.erase(unique(st.begin(),st.end()),st.end());去重为离散化做准备。
int h=st.size();
Btree(1,h,1);//建树
int x=0;
for(int i=1;i<=n;i++){
int l,r;
l=getid(a[i]);//区间进行离散化
r=getid(b[i]);
// cout<<l<<" "<<r<<endl;
update(l,r,++x,1);//给每张海报编号
}
ans=0;
memset(vis,0,sizeof(vis));
query(1,h,1);
printf("%d\n",ans);
return 0;
}
总结：
这题让我看了更多有技巧的操作，这种在线查询线段树还是强，可持续线段树以后有时间再搞搞，下次应该
看看树状数组。
现在的努力只为变得更强。