Count Color poj2777 線段樹

題意

有一個長木板，現在往上面在一定區間內刷顏色，后來刷的顏色會掩蓋掉前面刷的顏色，問每次一定區間內可以看到多少種顏色。

解題思路

這里使用線段樹，因為刷顏色可以看作是區間修改，使用lazy標記區間的顏色種類，下傳標記后，當前節點的lazy標記就標記為0，然后使用vis數組來標記顏色（顏色種類很少）。剩下的基本就是線段樹的模板了。

代碼實現

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e5+17; struct node{int l, r, lazy; }a[maxn<<2]; int vis[35];//顏色種類 int L, T, O, ans; void build(int rt, int l, int r) {a[rt].l=l;a[rt].r=r;a[rt].lazy=1;//默認為第一種顏色if(l==r){return ;}int mid=(l+r)>>1;build(rt<<1, l, mid);build(rt<<1|1, mid+1, r); } void down(int k) {a[k<<1].lazy=a[k].lazy;a[k<<1|1].lazy=a[k].lazy;a[k].lazy=0;//表示他的節點下面可能是兩種不同的顏色 } void update(int rt, int L, int R, int x) {if(L<=a[rt].l && a[rt].r<=R){a[rt].lazy=x;return ; }int mid=(a[rt].l+a[rt].r)>>1;if(a[rt].lazy !=0 ) //記得一定要下傳標記 down(rt); if(L<=mid) update(rt<<1, L, R, x);if(R>mid) update(rt<<1|1, L, R, x); } void query(int rt, int L, int R) {if(a[rt].lazy!=0) //如果不為零就可以進行判斷，因為下面的也是這種顏色{if(!vis[a[rt].lazy])// 看是否之前標記過{ans++; //沒有標記就加一vis[a[rt].lazy]=1; //標記}return ;}int mid=(a[rt].l+a[rt].r)>>1;if(a[rt].lazy!=0)down(rt);if(L<=mid) query(rt<<1, L, R);if(R>mid) query(rt<<1|1, L, R); } int main() {int l, r, c;char s[4];while(scanf("%d%d%d", &L, &T, &O)!=EOF){build(1, 1, L);for(int i=1; i<=O; i++){scanf("%s", s);if(s[0]=='C'){scanf("%d%d%d", &l, &r, &c);if(l > r){swap(l, r);}update(1, l, r, c);}else {scanf("%d%d", &l, &r);if(l > r) {swap(l, r); }memset(vis, 0, sizeof(vis));ans=0;query(1, l, r);printf("%d\n", ans);}} }return 0; }

轉載于:https://www.cnblogs.com/alking1001/p/11316507.html

總結

以上是生活随笔為你收集整理的Count Color poj2777 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。