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
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
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。
【题解】
为什么题目不带BZOJ的格式了？我也不知道。
由于只要维护最值，处理区间时，可以直接对区间最值进行修改。
接着可以用父亲的区间最值去更新儿子的区间最值，然后再用儿子的最值松弛父亲。
接下来是精彩的卡常时间。
首先窝萌阔以手写max和min。
其次窝萌阔以用位运算预处理每个节点的左右儿子。
此外窝萌阔以加inline和读入优化。
然后就水过辣！
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=2000010;
int n,m,i,opt,l,r,x;
int mx1[M*4],mx2[M*4];
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void pushdown(int p){
int l=p<<1,r=p<<1^1;
if (mx2[p]>mx1[l])mx1[l]=mx2[l]=mx2[p];
else if (mx2[p]>mx2[l])mx2[l]=mx2[p];
if (mx2[p]>mx1[r])mx1[r]=mx2[r]=mx2[p];
else if (mx2[p]>mx2[r])mx2[r]=mx2[p];
if (mx1[p]<mx2[l])mx1[l]=mx2[l]=mx1[p];
else if (mx1[p]<mx1[l])mx1[l]=mx1[p];
if (mx1[p]<mx2[r])mx1[r]=mx2[r]=mx1[p];
else if (mx1[p]<mx1[r])mx1[r]=mx1[p];
}
inline void pushup(int p){
int l=p<<1,r=p<<1^1;
mx1[p]=max(mx1[l],mx1[r]);
mx2[p]=min(mx2[l],mx2[r]);
}
inline void update1(int x,int y,int l,int r,int p,int t){
if (x==l&&y==r){
mx1[p]=max(mx1[p],t);
mx2[p]=max(mx2[p],t);
return;
}
int mid=l+r>>1;
pushdown(p);
if (y<=mid)update1(x,y,l,mid,p<<1,t);
else if (x>mid)update1(x,y,mid+1,r,p<<1^1,t);
else update1(x,mid,l,mid,p<<1,t),update1(mid+1,y,mid+1,r,p<<1^1,t);
pushup(p);
}
inline void update2(int x,int y,int l,int r,int p,int t){
if (x==l&&y==r){
mx1[p]=min(mx1[p],t);
mx2[p]=min(mx2[p],t);
return;
}
int mid=l+r>>1;
pushdown(p);
if (y<=mid)update2(x,y,l,mid,p<<1,t);
else if (x>mid)update2(x,y,mid+1,r,p<<1^1,t);
else update2(x,mid,l,mid,p<<1,t),update2(mid+1,y,mid+1,r,p<<1^1,t);
pushup(p);
}
inline void build(int l,int r,int p){
if (l==r){
printf("%d\n",mx1[p]);
return;
}
int mid=l+r>>1;
pushdown(p);
build(l,mid,p<<1);
build(mid+1,r,p<<1^1);
}
int main(){
n=read(),m=read();
for (i=1;i<=m;i++){
opt=read();
if (opt==1){
l=read(),r=read(),x=read();
l++;r++;
update1(l,r,1,n,1,x);
}else{
l=read(),r=read(),x=read();
l++;r++;
update2(l,r,1,n,1,x);
}
}
build(1,n,1);
}
评论 (0)
