題目描寫敘述：
長度為L個單位的畫板，有T種不同的顏料?，F(xiàn)要求按序做O個操作，操作分兩種：
1.“C A B C”,即將A到B之間的區(qū)域涂上顏色C
2.“P A B”。查詢[A，B]區(qū)域內(nèi)出現(xiàn)的顏色種類
出現(xiàn)操作2時。請輸出答案
PS:初始狀態(tài)下畫板顏色為1
一開始沒有想那么好，用int整型位移來取代顏色。還是使用了最傳統(tǒng)的bool color[來記錄。但是不知道錯在了哪里。
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>#define ll long long#define LL __int64#define eps 1e-8#define inf 0xfffffff//const LL INF = 1LL<<61;using namespace std;//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;const int N = 100000 + 5;typedef struct Node {int color;int l,r;
};Node tree[N * 4];
bool vis[50];void init() {memset(vis,false,sizeof(vis));
}void build(int l,int r,int id) {tree[id].color = 1;tree[id].l = l;tree[id].r = r;if(tree[id].l == tree[id].r)return;int mid = (l + r)/2;build(l,mid,id<<1);build(mid + 1,r,id<<1|1);
}void update(int l,int r,int id,int color) {if(tree[id].l >= l && tree[id].r <= r) {tree[id].color = color;return;}int mid = (tree[id].l + tree[id].r)/2;tree[id].color = -1;if(r <= mid) update(l,r,id<<1,color);else {if(l > mid)update(l,r,id<<1|1,color);else {update(l,mid,id<<1,color);update(mid+1,r,id<<1|1,color);}}
}void update2(int l,int r,int id) {if(tree[id].color > 0) {vis[tree[id].color] = true;return;}if(tree[id].l == tree[id].r)return;int mid = (tree[id].l + tree[id].r)/2;if(r <= mid) update2(l,r,id<<1);else {if(l > mid)update2(l,r,id<<1|1);else {update2(l,mid,id<<1);update2(mid+1,r,id<<1|1);}}
}int find(int x) {int ans = 0;for(int i=1;i<=x;i++)if(vis[i])ans++;return ans;
}int main() {int n,m,q;while(scanf("%d %d %d",&n,&m,&q) == 3 ){memset(tree,0,sizeof(tree));init();build(1,n,1);while(q--) {char s[2];scanf("%s",s);if(s[0] == 'C') {int x,y,c;scanf("%d %d %d",&x,&y,&c);if(x > y)swap(x,y);update(x,y,1,c);}else {int x,y;scanf("%d %d",&x,&y);init();if(x > y)swap(x,y);update2(x,y,1);printf("%d\n",find(m));}}}return 0;
}
后來看了別人的一下，看到方法不一樣，跑了案例也沒發(fā)現(xiàn)自己的錯誤，繼續(xù)檢查還是不行。難道真的是方法不行？換了個方法過了。可是上面的代碼錯誤原因還是沒有查出來，WA哭
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>#define ll long long#define LL __int64#define eps 1e-8#define inf 0xfffffff//const LL INF = 1LL<<61;using namespace std;//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;const int N = 100000 + 5;typedef struct Node {int l,r;int color;int flag;
};Node tree[N * 4];void init() {memset(tree,0,sizeof(tree));
}void cal(int id) {tree[id].color = tree[id<<1].color | tree[id<<1|1].color;
}void build(int l,int r,int id) {tree[id].l = l;tree[id].r = r;tree[id].color = 1;tree[id].flag = 1;if(tree[id].l == tree[id].r) return;int mid = (l + r)/2;build(l,mid,id<<1);build(mid+1,r,id<<1|1);
}void cover(int id) {tree[id<<1].color = tree[id].color;tree[id<<1].flag = 1;tree[id<<1|1].color = tree[id].color;tree[id<<1|1].flag = 1;tree[id].flag = 0;
}void updata(int l,int r,int id,int col) {if(l <= tree[id].l && r >= tree[id].r) {tree[id].color = col;tree[id].flag = 1;return;}if(tree[id].color == col)return;if(tree[id].flag)cover(id);int mid = (tree[id].l + tree[id].r)/2;if(r <= mid) updata(l,r,id<<1,col);else if(l > mid)updata(l,r,id<<1|1,col);else {updata(l,mid,id<<1,col);updata(mid+1,r,id<<1|1,col);}cal(id);
}int ans;void query(int l,int r,int id) {if(l <= tree[id].l && r >= tree[id].r) {ans |= tree[id].color;return;}if(tree[id].flag) {ans |= tree[id].color;return;}int mid = (tree[id].l + tree[id].r)/2;if(r <= mid) query(l,r,id<<1);else if(l > mid) query(l,r,id<<1|1);else {query(l,mid,id<<1);query(mid+1,r,id<<1|1);}
}int main() {int n,m,q;while(scanf("%d %d %d",&n,&m,&q) == 3) {init();build(1,n,1);char s[2];while(q--) {scanf("%s",s);if(s[0] == 'C') {int x,y,c;scanf("%d %d %d",&x,&y,&c);if(x > y)swap(x,y);updata(x,y,1,1<<(c-1));//把顏色改成用正向委員算表示}else {int x,y;scanf("%d %d",&x,&y);if(x > y)swap(x,y);ans = 0;query(x,y,1);int cnt = 0;while(ans) {if(ans%2)cnt++;ans /= 2;}printf("%d\n",cnt);}}}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的POJ2777 Count Color 线段树区间更新的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
