bzoj 4364: [IOI2014]wall砖墙

.

题意：在长度为n的一条砖墙，有k个操作，每次可以把l到r小于x的列变为x或把大于x的列变为x，问最后形状。
题解：线段树。一开始想了个奇怪的表示方法，发现没得下传，，于是膜了。。
正解是用线段树记录区间内l~r最高和最低的高度。父亲和儿子的数据冲突怎么办？按父亲的，因为儿子的信息是旧的，父亲的是新的。想通这点就好了。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,k,num=0,a[2000010];
struct tree
{
    int l,r,lc,rc,mx,mn;
}tr[4000010];

int bt(int l,int r)
{
    int i=++num;
    tr[i].l=l;
    tr[i].r=r;
    if(l<r)
    {
        int md=l+r>>1;
        tr[i].lc=bt(l,md);
        tr[i].rc=bt(md+1,r);
    }
    return i;
}
void pushdown(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc;
    if(tr[x].mx<tr[lc].mn)
    tr[lc].mn=tr[lc].mx=tr[x].mx;
    else if(tr[x].mx<tr[lc].mx)
    tr[lc].mx=tr[x].mx;
    if(tr[x].mn>tr[lc].mx)
    tr[lc].mn=tr[lc].mx=tr[x].mn;
    else if(tr[x].mn>tr[lc].mn)
    tr[lc].mn=tr[x].mn;
    if(tr[x].mx<tr[rc].mn)
    tr[rc].mn=tr[rc].mx=tr[x].mx;
    else if(tr[x].mx<tr[rc].mx)
    tr[rc].mx=tr[x].mx;
    if(tr[x].mn>tr[rc].mx)
    tr[rc].mn=tr[rc].mx=tr[x].mn;
    else if(tr[x].mn>tr[rc].mn)
    tr[rc].mn=tr[x].mn;
}
void pushup(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc;
    tr[x].mx=max(tr[lc].mx,tr[rc].mx);
    tr[x].mn=min(tr[lc].mn,tr[rc].mn);
}
void chg(int i,int l,int r,int c,int type)
{
    if(tr[i].l==l&&tr[i].r==r)
    {
        if(type==1)
        {
            tr[i].mx=max(tr[i].mx,c);
            tr[i].mn=max(tr[i].mn,c);
        }
        else
        {
            tr[i].mx=min(tr[i].mx,c);
            tr[i].mn=min(tr[i].mn,c);
        }
        return;
    }
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    pushdown(i);
    if(r<=md)
    chg(lc,l,r,c,type);
    else if(l>md)
    chg(rc,l,r,c,type);
    else
    {
        chg(lc,l,md,c,type);
        chg(rc,md+1,r,c,type);
    }
    pushup(i);
}
void get(int i)
{
    if(tr[i].l==tr[i].r)
    {
        printf("%d\n",tr[i].mx);
        return;
    }
    pushdown(i);
    get(tr[i].lc);
    get(tr[i].rc);
}
int main()
{
    scanf("%d%d",&n,&k);
    bt(1,n);
    for(int i=0;i<k;i++)
    {
        int op,l,r,x;
        scanf("%d%d%d%d",&op,&l,&r,&x);
        l++;
        r++;
        chg(1,l,r,x,op);/*
        get(1);
        for(int i=1;i<=num;i++)
        printf("i:%d l:%d r:%d mx:%d mn:%d\n",i,tr[i].l,tr[i].r,tr[i].mx,tr[i].mn);*/
    }
    get(1);
}