首页 > 代码库 > POJ2777

POJ2777

2024-08-13 04:27:55   218人阅读

http://poj.org/problem?id=2777

前几天看到一个大神说，要搞，就搞专题或者套题，我觉得现在这么菜的我，还是搞搞专题吧。

一道比较裸也比较基础的线段树的题目。

题意：就是有一段木头，可以对这个木头进行两种操作，一是进行涂色，而是进行查询，如果一个木头之前涂过色，那么之后涂色的话，会对之前的进行覆盖。

很明显的一个线段树的题目，不用线段树肯定超时的。

 1 #include <stdio.h> 2 #include <string.h> 3 #define maxn 1000005 4  5 struct note{ 6     int l,r; 7     int col; 8 }Tegtree[ 3*maxn ]; 9 bool mark[40];10 11 void bulid(int root,int st,int en)12 {13     Tegtree[ root ].l = st;14     Tegtree[ root ].r = en;15     if(st == en) return ;16     int mid = ( Tegtree[ root ].l + Tegtree[ root ].r )>>1;17     bulid( root << 1 , st , mid );18     bulid( (root << 1) + 1 , mid + 1 , en );19 }20 21 void Update(int root,int x,int y,int colc)22 {23     if(Tegtree[ root ].l >= x && Tegtree[ root ].r <=y )24     {25         Tegtree[ root ].col = colc;26         return ;27     } else28     {29         if(Tegtree[root].col > 0)    //进行延迟标记。30         {31             Tegtree[ root << 1 ].col = Tegtree[root].col;32             Tegtree[( root << 1 ) + 1 ].col = Tegtree[root].col;33             Tegtree[root].col = 0;34         }35         int mid = (Tegtree[ root ].l + Tegtree[ root ].r ) >> 1;36         if(x>mid){37             Update((root<<1)+1,x,y,colc);38         }else if(y<=mid){39             Update(root<<1,x,y,colc);40         }else {41             Update(root<<1,x,mid,colc);42             Update((root<<1)+1,mid+1,y,colc);43         }44     }45 }46 void Find(int root,int x,int y)47 {48     if(Tegtree[root].col > 0 )49     {50         mark[Tegtree[root].col] = true;51     }else{52         int mid = (Tegtree[ root ].l + Tegtree[ root ].r ) >> 1;53             if(x>mid){54                 Find((root<<1)+1,x,y);55             }else if(y<=mid){56                 Find(root<<1,x,y);57             }else {58                 Find(root<<1,x,mid);59                 Find((root<<1)+1,mid+1,y);60             }61     }62 }63 64 int main()65 {66    // freopen("in.txt","r",stdin);67     int l,t,o,a,b,c;68     char tmp[5];69     while(scanf("%d%d%d",&l,&t,&o)!=EOF)70     {71         Tegtree[1].col = 1;72         bulid(1,1,l);73         while(o--)74         {75             76             scanf("%s",tmp);77          //   printf("%s\n",tmp);78             if(tmp[0]==‘C‘)79             {80                 scanf("%d%d%d",&a,&b,&c);81                 getchar();82                 Update(1,a,b,c);83             }84             else if(tmp[0]==‘P‘)85             {86                 scanf("%d%d",&a,&b);87                 getchar();88                 memset(mark,false,sizeof(mark));89                 Find(1,a,b);90                 int ans = 0;91                 for(int i = 0 ; i <= 40 ; i++)92                     if(mark[i]) ans++;93                 printf("%d\n",ans);94             }95         }96     }97     return 0;98 }

 

POJ2777


联系
我们