hdu 4391 Paint The Wall
http://acm.hdu.edu.cn/showproblem.php?pid=4391
n個機關長度,m個操作
n個數,表示n個機關長度中起始顔色
m行, a, l, r, z
a== 1表示把l到r塗為z色(z>= 0 && z<= 2^31)
a==2 表示詢問l到r為z色的有多少
用lazy,同時,節點中,加入mi和ma記錄該段中的最大和最小值是多少
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 100010;
struct node{
int num, lef, rig, mid, ans, lazy, col, mi, ma;
}seg[maxn*4];
int m, n;
void maketree(int num, int lef, int rig){
seg[num].lef = lef;
seg[num].rig = rig;
seg[num].mid = (lef + rig)>> 1;
seg[num].lazy = 0;
seg[num].col = -1;
seg[num].ans = rig - lef + 1;
seg[num].mi = -1;
seg[num].ma = -1;
if( lef != rig){
maketree(num*2, lef, seg[num].mid);
maketree(num*2+ 1, seg[num].mid+1, rig);
}
}
void insert(int num, int lef, int rig, int col){
if( seg[num].lef == seg[num].rig){
seg[num].col = col;
seg[num].lazy = 1;
seg[num].mi =col;
seg[num].ma = col;
return ;
}
if( seg[num].lazy == 1){
seg[num*2].col = seg[num].col;
seg[num*2+1].col = seg[num].col;
seg[num*2].lazy = 1;
seg[num*2+1].lazy = 1;
seg[num*2].mi = seg[num].col;
seg[num*2].ma = seg[num].col;
seg[num*2+1].mi = seg[num].col;
seg[num*2+1].ma = seg[num].col;
seg[num].lazy = 0;
}
//這裡注意……ma,mi與lazy更新變化位置相同
if( seg[num].mi == -1){
seg[num].mi = col;
seg[num].ma = col;
}
else{
seg[num].mi = min( seg[num].mi, col);
seg[num].ma = max( seg[num].ma, col);
}
if( lef == seg[num].lef && rig == seg[num].rig){
seg[num].mi = col;
seg[num].ma = col;
seg[num].col = col;
seg[num].lazy = 1;
}
else if( rig <= seg[num].mid ){
insert(num*2, lef, rig, col);
}
else if( lef > seg[num].mid){
insert(num*2+1, lef, rig, col);
}
else{
insert(num*2, lef, seg[num].mid, col);
insert( num*2+1, seg[num].mid + 1, rig, col);
}
}
int cal(int num, int lef, int rig, int col){
if( col < seg[num].mi || col > seg[num].ma) return 0;
if( lef == seg[num].lef && rig == seg[num].rig){
if( seg[num].lazy == 1){
if( seg[num].col == col){
return seg[num].ans;
}
else return 0;
}
else{
return cal(num*2, lef, seg[num].mid, col) + cal(num*2+1, seg[num].mid+1, rig, col);
}
}
//lazy在cal中同樣需要更新
if( seg[num].lazy == 1){
seg[num*2].col = seg[num].col;
seg[num*2+1].col = seg[num].col;
seg[num*2].mi = seg[num].col;
seg[num*2+1].mi = seg[num].col;
seg[num*2].ma = seg[num].col;
seg[num*2+1].ma = seg[num].col;
seg[num*2].lazy = 1;
seg[num*2+1].lazy = 1;
seg[num].lazy = 0;
}
if( rig <= seg[num].mid){
return cal(num*2, lef, rig, col);
}
else if( lef > seg[num].mid){
return cal(num*2+1, lef, rig, col);
}
else{
return cal(num*2, lef, seg[num].mid, col) + cal(num*2+1, seg[num].mid+1, rig, col);
}
}
int main(){
//freopen("1.txt", "r", stdin);
int i, j, k, aa, bb, cc, dd;
while( scanf("%d%d", &n, &m) != EOF){
maketree(1, 0, n-1);
for( i= 0; i<n; i++){
scanf("%d", &aa);
insert( 1, i, i, aa);
}
for( i= 0; i<m; i++){
scanf("%d%d%d%d", &aa, &bb, &cc, &dd);
if( aa == 2){
printf("%d\n", cal(1, bb, cc, dd));
}
if( aa == 1){
insert(1, bb, cc, dd);
}
}
}
return 0;
}