洛谷4560 [IOI2014]Wall 砖墙

Luogu

UOJ

分析

考虑在线段树上维护两个标记 $maxv$ 和 $minv$ ,分别表示取 $\max$ 的操作和取 $\min$ 的操作。

$maxv$ 初始化为 $0$ ,$minv$ 初始化为 $\infty$ 。

打标记和 pushdown 大概是这样:

inline void update_max(int o,int w) {
    maxv[o]=max(maxv[o],w),minv[o]=max(minv[o],w);
}
inline void update_min(int o,int w) {
    maxv[o]=min(maxv[o],w),minv[o]=min(minv[o],w);
}
inline void pushdown(int o) {
    update_min(ls,minv[o]),update_min(rs,minv[o]);
    update_max(ls,maxv[o]),update_max(rs,maxv[o]);
    maxv[o]=0,minv[o]=2e9;
}

最后遍历一下整棵线段树即可得到答案。

代码

洛谷版

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000000+10;

int n,m,ans[N];

#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2],minv[N<<2];
inline void update_max(int o,int w) {
    maxv[o]=max(maxv[o],w),minv[o]=max(minv[o],w);
}
inline void update_min(int o,int w) {
    maxv[o]=min(maxv[o],w),minv[o]=min(minv[o],w);
}
inline void pushdown(int o) {
    update_min(ls,minv[o]),update_min(rs,minv[o]);
    update_max(ls,maxv[o]),update_max(rs,maxv[o]);
    maxv[o]=0,minv[o]=2e9;
}
inline void build(int o,int l,int r) {
    maxv[o]=0,minv[o]=2e9;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
inline void modify_max(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { update_max(o,w); return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify_max(ls,l,mid,ql,qr,w);
    if (qr>mid) modify_max(rs,mid+1,r,ql,qr,w);
}
inline void modify_min(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { update_min(o,w); return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify_min(ls,l,mid,ql,qr,w);
    if (qr>mid) modify_min(rs,mid+1,r,ql,qr,w);
}
inline void query(int o,int l,int r) {
    if (l==r) { ans[l]=maxv[o]; return; }
    int mid=(l+r)>>1; pushdown(o);
    query(ls,l,mid),query(rs,mid+1,r);
}
#undef ls
#undef rs

int main() {
    n=read(),m=read(); build(1,1,n);
    while (m--) {
        int op=read(),l=read()+1,r=read()+1,w=read();
        if (op==1) modify_max(1,1,n,l,r,w);
        else modify_min(1,1,n,l,r,w);
    }
    query(1,1,n);
    for (re int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

UOJ版

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include "wall.h"
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000000+10;

int n,m,ans[N];

#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2],minv[N<<2];
inline void update_max(int o,int w) {
    maxv[o]=max(maxv[o],w),minv[o]=max(minv[o],w);
}
inline void update_min(int o,int w) {
    maxv[o]=min(maxv[o],w),minv[o]=min(minv[o],w);
}
inline void pushdown(int o) {
    update_min(ls,minv[o]),update_min(rs,minv[o]);
    update_max(ls,maxv[o]),update_max(rs,maxv[o]);
    maxv[o]=0,minv[o]=2e9;
}
inline void build(int o,int l,int r) {
    maxv[o]=0,minv[o]=2e9;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
}
inline void modify_max(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { update_max(o,w); return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify_max(ls,l,mid,ql,qr,w);
    if (qr>mid) modify_max(rs,mid+1,r,ql,qr,w);
}
inline void modify_min(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { update_min(o,w); return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify_min(ls,l,mid,ql,qr,w);
    if (qr>mid) modify_min(rs,mid+1,r,ql,qr,w);
}
inline void query(int o,int l,int r) {
    if (l==r) { ans[l]=maxv[o]; return; }
    int mid=(l+r)>>1; pushdown(o);
    query(ls,l,mid),query(rs,mid+1,r);
}
#undef ls
#undef rs

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]) {
    build(1,1,n);
    for (re int i=0;i<k;++i) {
        if (op[i]==1) modify_max(1,1,n,left[i]+1,right[i]+1,height[i]);
        else modify_min(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    query(1,1,n);
    for (re int i=0;i<n;++i) finalHeight[i]=ans[i+1];
}
最后修改:2019 年 10 月 03 日 04 : 24 PM

2 条评论

  1. smy

    %%%IOI大佬

    1. M_sea
      @smy

      不是您吗 %%%%%

发表评论