BZOJ4364: [IOI2014]wall砖墙-布布扣-bubuko.com

BZOJ4364: [IOI2014]wall砖墙

Description

健佳正在用大小相同的砖块来砌起一面墙。

这面墙由列砖块所组成，它们从左到右的编号0至n-1。

各列的高度可以不同。各列的高度就是该列砖块的数量。健佳用如下方式来建造这面墙。最开始每列都没有砖块。

此后，健佳通过k个阶段的增加(adding)或移除(removing)砖块操作来砌墙。

当所有k个阶段完成后，这面墙就砌好了。

在每个阶段中，健佳都会被告知一个连续的砖块列的范围，以及一个高度值h，然后他就完成如下过程：

在增加砖块(adding)阶段，对于给定的列范围中高度小于h的列，健佳会增加砖块使它们的高度都恰好等于h。此时他不会改变那些高度大于或等于h的列。

在移除砖块(removing)阶段，对于给定的列范围中高度大于的列，健佳会移除砖块使它们的高度都恰好等于h。此时他不会改变那些高度小于或等于h的列。

你的任务就是计算出这面墙的最后形状。

Input

第1行：n, k。

第2+i 行(0≤i≤k-1)：op[i], left[i], right[i], height[i]。

n: 这面墙中的列数。

k: 阶段数。

op: 大小为k的数组；op[i]是第i个阶段的类型：1 表示增加阶段(adding) 而 2表示移除阶段(removing) 其中0≤i≤k-1。

left 和 right: 大小为k的数组；

在第i个阶段中，列的范围从第left[i] 列开始到第right[i]列结束（包括两端left[i] 和 right[i]），其中0≤i≤k-1。这里保证满足left[i]≤right[i]。

height: 大小为k的数组；height[i] 表示在阶段i的高度参数，其中0≤i≤k-1。

Output

共n行

第i行包含一个整数表示finalHeight[i]。

finalHeight: 大小为n的数组；你需要把第i列砖块的最终数量存放到finalHeight[i]中做为返回结果

其中0≤i≤n-1。

Sample Input

输入样例1
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412

输入样例2
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

Sample Output

输出样例1
0
0
0
39412
39412
39412
48623
48623
48623
48623

输出样例2
3
4
5
4
3
3
0
0
1
0

HINT

技术分享图片

对于100%的数据，1≤n≤2,000,000，1≤k≤500,000。

2016.6.17时限放至60s

题解Here!

额，调了一上午的线段树，然后发现把左儿子$LSON$打成了$rt$，尴尬。。。

这题就维护一下$left,right$的最大值和最小值，重点是$pushdown$怎么写。

如果发现有全部覆盖的情况，直接全部改，否则特判一下就好了。

然后就是线段树板子了。

话说$IOI$啥时候开始考板子了。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA1(x) a[x].data1
#define DATA2(x) a[x].data2
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
#define MAXN 2000010
using namespace std;
int n,m;
struct Segment_Tree{
    int data1,data2;
    int l,r;
}a[MAXN<<2];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
    return date*w;
}
inline void pushup(int rt){
    DATA1(rt)=max(DATA1(LSON),DATA1(RSON));
    DATA2(rt)=min(DATA2(LSON),DATA2(RSON));
}
inline void pushdown(int rt){//这是重点
    if(LSIDE(rt)==RSIDE(rt))return;
    //--------------------------------------------------------------------------
    if(DATA1(rt)<DATA2(LSON))DATA1(LSON)=DATA2(LSON)=DATA1(rt);
    else if(DATA1(rt)<DATA1(LSON))DATA1(LSON)=DATA1(rt);
    if(DATA2(rt)>DATA1(LSON))DATA1(LSON)=DATA2(LSON)=DATA2(rt);
    else if(DATA2(rt)>DATA2(LSON))DATA2(LSON)=DATA2(rt);
    //--------------------------------------------------------------------------
    if(DATA1(rt)<DATA2(RSON))DATA1(RSON)=DATA2(RSON)=DATA1(rt);
    else if(DATA1(rt)<DATA1(RSON))DATA1(RSON)=DATA1(rt);
    if(DATA2(rt)>DATA1(RSON))DATA1(RSON)=DATA2(RSON)=DATA2(rt);
    else if(DATA2(rt)>DATA2(RSON))DATA2(RSON)=DATA2(rt);
    //--------------------------------------------------------------------------
}
void buildtree(int l,int r,int rt){
    int mid;
    LSIDE(rt)=l;
    RSIDE(rt)=r;
    if(l==r){
        DATA1(rt)=DATA2(rt)=0;
        return;
    }
    mid=l+r>>1;
    buildtree(l,mid,LSON);
    buildtree(mid+1,r,RSON);
    pushup(rt);
}
void update_up(int l,int r,int c,int rt){
    int mid;
    if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
        DATA1(rt)=max(DATA1(rt),c);
        DATA2(rt)=max(DATA2(rt),c);
        return;
    }
    pushdown(rt);
    mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)update_up(l,r,c,LSON);
    if(mid<r)update_up(l,r,c,RSON);
    pushup(rt);
}
void update_low(int l,int r,int c,int rt){
    int mid;
    if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
        DATA1(rt)=min(DATA1(rt),c);
        DATA2(rt)=min(DATA2(rt),c);
        return;
    }
    pushdown(rt);
    mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)update_low(l,r,c,LSON);
    if(mid<r)update_low(l,r,c,RSON);
    pushup(rt);
}
void query(int l,int r,int rt){
    int mid;
    if(l==r){
        printf("%d\n",DATA1(rt));
        return;
    }
    pushdown(rt);
    mid=l+r>>1;
    query(l,mid,LSON);
    query(mid+1,r,RSON);
}
void work(){
    int f,x,y,k;
    while(m--){
        f=read();x=read()+1;y=read()+1;k=read();
        if(f==1)update_up(x,y,k,1);
        else update_low(x,y,k,1);
    }
    query(1,n,1);
}
void init(){
    n=read();m=read();
    buildtree(1,n,1);
}
int main(){
    init();
    work();
    return 0;
}

BZOJ4364: [IOI2014]wall砖墙

原文：https://www.cnblogs.com/Yangrui-Blog/p/9425177.html