bzoj4364: [IOI2014]wall砖墙

#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];
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;
}
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];
}
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]);
}
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);
}
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);
}
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();
        l=read(),r=read(),x=read();
        l++;r++;
        if (opt==1)
            update1(l,r,1,n,1,x);
        else
            update2(l,r,1,n,1,x);
        }
    }
    build(1,n,1);
}