kuangbin专题七 ZOJ1610 Count the Colors (灵活线段树)
Painting some colored segments on a line,some previously painted segments may be covered by some the subsequent ones. Your task is counting the segments of different colors you can see at last. Input ? Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces: All the numbers are in the range [0,8000],and they are all integers. Input may contain several data set,process to the end of file.
Output ? If some color can‘t be seen,you shouldn‘t print it. Print a blank line after every dataset.
Sample Input ?
Sample Output ? 1 1 0 2 ? 因为是线段树专题,就思考线段树,由于刚用线段树,这里的建树感觉没用,但是不确定,不过Pushup果断弃用。还有就是Query的时候是需要跑所有叶节点的,所以不需要那些判断, 大体思路正确,就是没想到用last记录。 ? 1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 #include <string.h> 5 #include <stdlib.h> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <queue> 11 #include <algorithm> 12 #include <sstream> 13 #include <stack> 14 using namespace std; 15 #define FO freopen("in.txt","r",stdin); 16 #define rep(i,a,n) for (int i=a;i<n;i++) 17 #define per(i,n) for (int i=n-1;i>=a;i--) 18 #define pb push_back 19 #define mp make_pair 20 #define all(x) (x).begin(),(x).end() 21 #define fi first 22 #define se second 23 #define SZ(x) ((int)(x).size()) 24 #define debug(x) cout << "&&" << x << "&&" << endl; 25 #define lowbit(x) (x&-x) 26 #define mem(a,b) memset(a,b,sizeof(a)); 27 typedef vector<int> VI; 28 typedef long long ll; 29 typedef pair<int,int> PII; 30 const ll mod=1000000007; 31 const int inf = 0x3f3f3f3f; 32 ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} 33 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} 34 //head 35 36 const int maxn=8010; //last 上一段的颜色 37 int lazy[maxn<<2],n,ans[maxn],last;//lazy就是树,不需要处理什么信息 38 39 void Pushdown(int rt) { 40 if(lazy[rt]!=-1) { 41 lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; 42 lazy[rt]=-1; 43 } 44 } 45 46 void Updata(int rt,int L,int R,int l,int r,int val) { 47 if(L>=l&&R<=r) { 48 lazy[rt]=val; 49 return; 50 } 51 Pushdown(rt); 52 int mid=(L+R)>>1; 53 if(l<=mid) Updata(rt<<1,L,mid,l,r,val); 54 if(r>mid) Updata(rt<<1|1,mid+1,R,val); 55 } 56 57 void Query(int rt,int r) {//不要太死板,学会变通 58 if(L==R) { 59 if(lazy[rt]!=-1&&lazy[rt]!=last) {//巧妙 60 ans[lazy[rt]]++; 61 } 62 last=lazy[rt]; 63 return; 64 } 65 Pushdown(rt); 66 int mid=(L+R)>>1;//需要遍历所有叶节点 67 Query(rt<<1,r); 68 Query(rt<<1|1,r); 69 } 70 71 int main() { 72 while(~scanf("%d",&n)) { 73 mem(ans,0); 74 mem(lazy,-1); 75 int x,y,val; 76 while(n--) { 77 scanf("%d%d%d",&x,&y,&val); 78 Updata(1,1,maxn,x+1,val);//把0 变为 1 79 } 80 last=-1; 81 Query(1,1,maxn); 82 rep(i,0,maxn) { 83 if(ans[i]) printf("%d %dn",i,ans[i]); 84 } 85 printf("n"); 86 } 87 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |