【IOI2014】【线段树】Wall 砖墙

luogu

bzoj

就数据范围来看此题需要用线段树维护墙高度的区间

我们观察到对于灰色区间而言

绿色区间的下传可以正常取min或者max

橙色区间则需要整体赋值

分类讨论即可

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=1<<21;
const int INF=2139062143;

int n,m;
int tag[2][MAXN<<1];

inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||'9'<ch) ch=getchar();
    while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}

void pd(int k,int i)
{
    if(tag[1][i]>=tag[0][k]) tag[1][i]=tag[0][i]=tag[0][k];
    else if(tag[1][k]>tag[1][i]) tag[1][i]=tag[1][k];
    if(tag[1][k]>=tag[0][i]) tag[1][i]=tag[0][i]=tag[1][k];
    else if(tag[0][k]<tag[0][i]) tag[0][i]=tag[0][k];
    return;
}

void pushdown(int k,int l,int r)
{
    if(l==r||(tag[0][k]==INF&&!tag[1][k])) return;
    int mid=l+r>>1,i=k<<1;
    pd(k,i);pd(k,i|1);
    tag[0][k]=INF,tag[1][k]=0;
    return;
}

void ctag(int k,int l,int r,int le,int ri,int val,int kd)
{
    pushdown(k,l,r);
    if(le<=l&&r<=ri){
        if(kd==1) tag[kd][k]=max(tag[kd][k],val);
        else tag[kd][k]=min(tag[kd][k],val);
        if(tag[1][k]>tag[0][k]) tag[1][k]=tag[0][k]=val;
        return;
    }int mid=l+r>>1,i=k<<1;
    if(le<=mid) ctag(i,l,mid,le,ri,val,kd);
    if(mid<ri) ctag(i|1,mid+1,r,le,ri,val,kd);
}

int cask(int k,int l,int r,int x)
{
    pushdown(k,l,r);
    if(l==r) return tag[1][k];
    int mid=l+r>>1,i=k<<1;
    if(x<=mid) return cask(i,l,mid,x);
    return cask(i|1,mid+1,r,x);
}

int main()
{
    n=read(),m=read();
    memset(tag[0],0x7f,sizeof(tag[0]));
    while(m--){
        int t=read(),l=read(),r=read(),v=read();
        ctag(1,1,n,l+1,r+1,v,t&1);
    }for(int i=1;i<=n;++i) printf("%d\n",cask(1,1,n,i));
    return 0;
}