Description

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

题解

这题我也想了一会才弄出来
首先，我决定离线
我们把修改倒着插进去
然后对于每一个点维护两个东西，一个是他的下界，一个是他的下界
然后如果如果出现了第一次上下界相交，那么他的答案就是相交时没有修改的那个
如果一直没有相交，那么答案肯定就是下界了。。
写成代码是这样的：

void change (int now,int l,int r,int x)//1 
{if (s[now].l==s[now].r){s[now].c=mymax(s[now].c,x);s[now].c=mymin(s[now].c,s[now].c1);return ;}int s1=s[now].s1,s2=s[now].s2;int mid=(s[now].l+s[now].r)>>1;if (r<=mid) change(s1,l,r,x);else if (l>mid) change(s2,l,r,x);else change(s1,l,mid,x),change(s2,mid+1,r,x);
}
void change1 (int now,int l,int r,int x)//2
{if (s[now].l==s[now].r){s[now].c1=mymin(s[now].c1,x);s[now].c1=mymax(s[now].c1,s[now].c);return ;}int s1=s[now].s1,s2=s[now].s2;int mid=(s[now].l+s[now].r)>>1;if (r<=mid) change1(s1,l,r,x);else if (l>mid) change1(s2,l,r,x);else change1(s1,l,mid,x),change1(s2,mid+1,r,x);
}

于是有了这个就好办了，随便打下lazy就好了
lazy也做一样的操作
CODE：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int K=500005;
const int N=2000005;
const int MAX=1<<30;
int n,k;
struct qq
{int l,r;int s1,s2;int c,c1;//第一个是下面的线 第二个是上面的线//其实在非叶子地方是lazy标记 
}s[N*2];int num=0;
int mymax (int x,int y)
{if (x==-1) return y;if (y==-1) return x;return x>y?x:y;
}
int mymin (int x,int y)
{if (x==-1) return y;if (y==-1) return x;return x<y?x:y;
}
void bt (int l,int r)
{int a=++num;s[a].l=l;s[a].r=r;s[a].c=s[a].c1=-1;if (l==r) {s[a].c=0;s[a].c1=MAX;return ;}int mid=(l+r)>>1;s[a].s1=num+1;bt(l,mid);s[a].s2=num+1;bt(mid+1,r);
}
struct qt
{int op,l,r,x;
}A[K];
void Push_down (int now)
{int s1=s[now].s1,s2=s[now].s2;if (s[now].c!=-1){s[s1].c=mymax(s[s1].c,s[now].c);s[s1].c=mymin(s[s1].c,s[s1].c1);s[s2].c=mymax(s[s2].c,s[now].c);s[s2].c=mymin(s[s2].c,s[s2].c1);s[now].c=-1;}if (s[now].c1!=-1){s[s1].c1=mymin(s[s1].c1,s[now].c1);s[s1].c1=mymax(s[s1].c1,s[s1].c);s[s2].c1=mymin(s[s2].c1,s[now].c1);s[s2].c1=mymax(s[s2].c1,s[s2].c);s[now].c1=-1;}
}
void change (int now,int l,int r,int x)
{if (s[now].l==l&&s[now].r==r){// printf("YES:%d %d %d\n",now,l,r);s[now].c=mymax(s[now].c,x);s[now].c=mymin(s[now].c,s[now].c1);return ;}Push_down(now);int s1=s[now].s1,s2=s[now].s2;int mid=(s[now].l+s[now].r)>>1;if (r<=mid) change(s1,l,r,x);else if (l>mid) change(s2,l,r,x);else change(s1,l,mid,x),change(s2,mid+1,r,x);
}
void change1 (int now,int l,int r,int x)
{if (s[now].l==l&&s[now].r==r){s[now].c1=mymin(s[now].c1,x);s[now].c1=mymax(s[now].c1,s[now].c);return ;}Push_down(now);int s1=s[now].s1,s2=s[now].s2;int mid=(s[now].l+s[now].r)>>1;if (r<=mid) change1(s1,l,r,x);else if (l>mid) change1(s2,l,r,x);else change1(s1,l,mid,x),change1(s2,mid+1,r,x);
}
int ans[N];
void dfs (int now)
{/*printf("%d %d %d %d\n",s[now].l,s[now].r,s[now].c,s[now].c1);system("pause");*/if (s[now].l==s[now].r){ans[s[now].l]=s[now].c;return ;}Push_down(now);int s1=s[now].s1,s2=s[now].s2;dfs(s1);dfs(s2);
}
int main()
{scanf("%d%d",&n,&k);bt(1,n);for (int u=1;u<=k;u++)  {scanf("%d%d%d%d",&A[u].op,&A[u].l,&A[u].r,&A[u].x);A[u].l++;A[u].r++;}for (int u=k;u>=1;u--){if (A[u].op==1)//增加change(1,A[u].l,A[u].r,A[u].x); else change1(1,A[u].l,A[u].r,A[u].x);}dfs(1);for (int u=1;u<=n;u++) printf("%d\n",ans[u]);return 0;
}