hdu 4391 Paint The Wall 線段樹 +優化 2012 Multi-University Training Contest 10 )

http://acm.hdu.edu.cn/showproblem.php?pid=4391

題意：

刷墻， 以開始 有 n個節點，每個節點有一種顏色 ，m 次詢問

?m次? 輸入 a，l，r，z 如果 a=1 將 l到 r 刷為 z 顏色，如果 a=2? 詢問 l 到 r 有 多少個 和 z 相同的 節點

官方題解是： 分段哈希，自己一開始想寫 一下 ，單寫著寫著 就 覺得很麻煩 ，各中判斷條件。。。。。

后來改為 線段樹? 優化了下 ，就是加了 個 mi mx? 判斷 查詢的顏色 是否在這里面。。。。。

?

??1?#include<cstdio>
??2?#include<cstring>
??3?#include<cmath>
??4?#include<iostream>
??5?#include<algorithm>
??6?#include<set>
??7?#include<map>
??8?#include<queue>
??9?#include<vector>
?10?#include<string>
?11?#define?Min(a,b)?a<b?a:b
?12?#define?Max(a,b)?a>b?a:b
?13?#define?CL(a,num)?memset(a,num,sizeof(a));
?14?#define?maxn??100010
?15?#define?eps??1e-6
?16?#define?inf?9999999
?17?#define?ll??__int64
?18?using?namespace?std;
?19?struct?node
?20?{
?21?????int?l;
?22?????int?r;
?23?????int?c;
?24?????int?mi;
?25?????int?mx;
?26?}p[maxn*4];
?27?int?a[maxn]?;
?28?void?build(int?x,int?l,int?r)
?29?{
?30?????if(l?==?r)
?31?????{
?32??????????p[x].l?=?l;
?33??????????p[x].r?=?r;
?34??????????p[x].c=?a[l];
?35??????????p[x].mi?=?a[l];
?36??????????p[x].mx?=?a[l];
?37??????????return?;
?38?????}
?39?????int?mid?=?(l+r)>>1;
?40??????p[x].l?=?l;
?41??????p[x].r?=?r;
?42??????build(x*2,l,mid);
?43??????build(x*2+1,mid+1,r);
?44??????if(p[x*2].c?==?p[x*2+1].c?&&p[x*2].c?!=?-1)p[x].c?=?p[x*2].c;
?45??????else?p[x].c?=?-1;
?46?
?47??????p[x].mi?=?min(p[x*2].mi,p[x*2+1].mi);
?48??????p[x].mx?=?max(p[x*2].mx,p[x*2+1].mx);
?49?
?50?
?51?
?52?}
?53?void?change(int?x,int?l,int?r,int?z)
?54?{
?55?????if(z?==?p[x].c)??return;
?56?????if(l?==?p[x].l&&r?==?p[x].r)
?57?????{
?58?????????p[x].c?=?z?;
?59?????????p[x].mi?=?z;
?60?????????p[x].mx?=?z;
?61?
?62?????????return??;
?63?
?64?????}
?65?????int?mid?=?(p[x].l+p[x].r)>>1;
?66?????if(p[x].c?!=?-1)
?67?????{
?68?????????p[x*2].c?=?p[x].c;
?69?????????p[x*2+1].c?=?p[x].c;
?70?????????p[x*2].mi?=p[x*2+1].mi?=?p[x].mi;//這兩個忘了 下分了 錯了 一次。。。。。。。。
?71?????????p[x*2].mx=p[x*2+1].mx?=?p[x].mx;
?72?????????p[x].c?=?-1;
?73?????}
?74?
?75?????if(r<=mid)?change(x*2,l,r,z);
?76?????else
?77?????{
?78?????????if(l>mid)change(x*2+1,l,r,z);
?79?????????else
?80?????????{
?81?????????????change(x*2,l,mid,z);
?82?????????????change(x*2+1,mid+1,r,z);
?83?????????}
?84?????}
?85??????p[x].mi?=?min(p[x*2].mi,p[x*2+1].mi);
?86??????p[x].mx?=?max(p[x*2].mx,p[x*2+1].mx);
?87?}
?88?int?get(int?x,int?l,int?r,int?z)
?89?{
?90?????if(p[x].c!=-1?&&p[x].c!=z)return?0;
?91?????if(z<p[x].mi?||z>p[x].mx)?return?0;
?92?
?93?????if(p[x].l?<=?l&&p[x].r?>=?r&&p[x].c?==?z)
?94?????{
?95?????????return?r?-?l?+?1;
?96?????}
?97?????int?mid?=?(p[x].l?+?p[x].r)>>1;
?98?
?99?????if(r<=mid)?return?get(x*2,l,r,z);
100?????else
101?????{
102?????????if(l>mid)?return?get(x*2+1,l,r,z);
103?????????else
104?????????{
105?????????????int?t1?=?get(x*2,l,mid,z);
106?????????????int?t2?=?get(x*2+1,mid+1,r,z);
107?????????????return?t1+t2;
108?????????}
109?????}
110?
111?
112?
113?}
114?
115?int?main()
116?{
117?????int?n,m,d,l,r,z,i;
118????//freopen("data.in","r",stdin);
119?????while(scanf("%d%d",&n,&m)!=EOF)
120?????{
121?????????for(i?=?0;?i?<?n;i++)
122?????????{
123?????????????scanf("%d",&a[i]);
124?????????}
125?????????build(1,0,n?-?1);
126?????????while(m--)
127?????????{
128?????????????scanf("%d%d%d%d",&d,&l,&r,&z);
129?????????????if(d?==?1)
130?????????????{
131?????????????????change(1,l,r,z);
132?????????????}
133?????????????else
134?????????????{
135?????????????????int?ans?=?get(1,l,r,z);
136?????????????????printf("%d\n",ans);
137?????????????}
138?????????}
139?????}
140?}

?

?