Chrysanthemum's Blog

健佳正在用大小相同的砖块来砌起一面墙。这面墙由 列砖块所组成，它们从左到右的编号0至n-1。各列的高度可以不同。各列的高度就是该列砖块的数量。健佳用如下方式来建造这面墙。最开始每列都没有砖块。此后，健佳通过k个阶段的增加(adding)或移除(removing)砖块操作来砌墙。当所有k个阶段完成后，这面墙就砌好了。在每个阶段中，健佳都会被告知一个连续的砖块列的范围，以及一个高度值h，然后他就完成如下过程：在增加砖块(adding)阶段，对于给定的列范围中高度小于h的列，健佳会增加砖块使它们的高度都恰好等于h。此时他不会改变那些高度大于或等于h的列。在移除砖块(removing)阶段，对于给定的列范围中高度大于 的列，健佳会移除砖块使它们的高度都恰好等于h。此时他不会改变那些高度小于或等于h的列。你的任务就是计算出这面墙的最后形状。

第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。

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

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

输入样例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

输出样例1

0
0
0
39412
39412
39412
48623
48623
48623
48623

输出样例2

3
4
5
4
3
3
0
0
1
0

 

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

为什么这道题题面复制过来格式会变成这样。。。所以我们加一条分割线吧。

------------------------------------------------------------------------------------------------------------------------------

用线段树就可以了，直接记录区间的最大值和最小值。不用加tag数组，pushdown的时候，只要用当前父亲的最大最小值去更新儿子的最大最小值就可以了，具体可以看代码。最后加点常数优化就可以了。

代码：

 

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,opt,l,r,x;
struct node{int min,max;}tr[8000010];
void read(int &x)
{
    char ch,fu=0;
    for (ch='*';(ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if (ch=='-') fu=1,ch=getchar();
    for (x=0;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    if (fu) x=-x;
}
inline void pushdown(int l,int r,int p)
{
    if (l==r) return;
    int sl=p<<1,sr=p<<1^1;
    if (tr[p].max<tr[sl].min) tr[sl].min=tr[sl].max=tr[p].max;else if (tr[p].max<tr[sl].max) tr[sl].max=tr[p].max;
    if (tr[p].max<tr[sr].min) tr[sr].min=tr[sr].max=tr[p].max;else if (tr[p].max<tr[sr].max) tr[sr].max=tr[p].max;
    if (tr[p].min>tr[sl].max) tr[sl].min=tr[sl].max=tr[p].min;else if (tr[p].min>tr[sl].min) tr[sl].min=tr[p].min;
    if (tr[p].min>tr[sr].max) tr[sr].min=tr[sr].max=tr[p].min;else if (tr[p].min>tr[sr].min) tr[sr].min=tr[p].min;
}
inline void change1(int l,int r,int p,int x,int y,int val)
{
    pushdown(l,r,p);
    if (l==x&&r==y){tr[p].max=max(tr[p].max,val);tr[p].min=max(tr[p].min,val);return;}
    int mid=(l+r)>>1,sl=p<<1,sr=p<<1^1;
    if (y<=mid) change1(l,mid,sl,x,y,val);else
    if (x>mid) change1(mid+1,r,sr,x,y,val);else
    {change1(l,mid,sl,x,mid,val);change1(mid+1,r,sr,mid+1,y,val);}
    tr[p].max=max(tr[sl].max,tr[sr].max);
    tr[p].min=min(tr[sl].min,tr[sr].min);
}
inline void change2(int l,int r,int p,int x,int y,int val)
{
    pushdown(l,r,p);
    if (l==x&&r==y){tr[p].max=min(tr[p].max,val);tr[p].min=min(tr[p].min,val);return;}
    int mid=(l+r)>>1,sl=p<<1,sr=p<<1^1;
    if (y<=mid) change2(l,mid,sl,x,y,val);else
    if (x>mid) change2(mid+1,r,sr,x,y,val);else
    {change2(l,mid,sl,x,mid,val);change2(mid+1,r,sr,mid+1,y,val);}
    tr[p].max=max(tr[sl].max,tr[sr].max);
    tr[p].min=min(tr[sl].min,tr[sr].min);
}
inline void print(int l,int r,int p)
{
    pushdown(l,r,p);
    if (l==r){printf("%d\n",tr[p].max);return;}
    int mid=(l+r)>>1;
    print(l,mid,p<<1);print(mid+1,r,p<<1^1);
}
int main()
{
    read(n);read(m);
    while (m--)
    {
        read(opt);read(l);read(r);read(x);l++;r++;
        if (opt==1) change1(1,n,1,l,r,x);else change2(1,n,1,l,r,x);
    }
    print(1,n,1);
}