学步园

下推标记法，更新区间最值，并维护一个属性------区间是否平齐，更新时把所有区间一直分解成平齐区间在决定是否修改。

感觉跑上去很慢，但实际却已经足够快，原因可能是数据弱。

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype>
//using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max(a,b) ((a) > (b) ? (a) : (b))
const int maxn = 211;
const int M    = 101111;
int MAX[M<<2],col[M<<2],flush[M<<2];
void build(int l,int r,int rt){
  col[rt] = 0;
  flush[rt] = true;
  MAX[rt] = 0;
  if(l==r) return ;
  int m = (l+r)>>1;
  build(lson);
  build(rson);
}
int push_up(int rt){
  flush[rt]=(flush[rt<<1]&&flush[rt<<1|1]&&MAX[rt<<1]==MAX[rt<<1|1]);
  MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
int push_down(int rt){
  if(col[rt]){
    if(col[rt]>col[rt<<1]){
        col[rt<<1] = col[rt];
        MAX[rt<<1] = col[rt];
        flush[rt<<1] = true;
    }
    if(col[rt]>col[rt<<1|1]){
        col[rt<<1|1] = col[rt];
        MAX[rt<<1|1] = col[rt];
        flush[rt<<1|1] = true;
    }
    col[rt] = 0;
  }
}
int ans = 0;
void update(int l,int r,int rt,int L,int R,int h){
  if(L<=l&&r<=R&&flush[rt]){
    if(MAX[rt]>h) return ;
    col[rt] = h;
    MAX[rt] = h;
    ans+=r-l+1;
    return ;
  }
  push_down(rt);
  int m = (l+r)>>1;
  if(L <= m) update(lson,L,R,h);
  if(R >  m) update(rson,L,R,h);
  push_up(rt);
}
int main()
{
    int x,y,z;
    int lim = 100005;
    int T,Q;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&Q);
        ans = 0;
        build(1,lim,1);
        while(Q--){
            scanf("%d %d %d",&x,&y,&z);
            if(x==y) continue;
            update(1,lim,1,x,y-1,z);
        }
        printf("%d\n",ans);
    }
    return 0;
}