在一個N*M(N<=200,M<=50000)像素的畫板上畫Q(Q<=50000)個圖形,有矩形,圓形,倒等腰三角形,菱形四種,每個圖形有九種顏色可選擇。對于一個像素,后畫的顏色會覆蓋前面的顏色,請求出最后每種顏色的像素有多少個?
吐槽:
1. 線段樹會MLE...大概...
2. ...并查集ms只能在這種問題上優化
算法分析:
額,嚴格的說不是并查集啊... 只是在一個數組上亂搞出一個類似并查集的東西...
現在我來簡要講述一下這個方法,這個方法非常好寫,也就10行左右... 而且比線段樹快很多~~
我目前知道的這個優化必須要把所有的線段"一視同仁",插入線段[1,3]和[2,4]后,一同視為[1,4]....
所以在任何時候,這個數組存的都是一段一段的不相交區間~~
對于一個區間[l,r],l到r上的所有點的“代表”都是r+1.....
如果要插入某線段[l',r'],那么從l'到r'掃一遍就可以了:
如果某個點p代表是自己的話,那么就把p的代表改為Parent[r],然后檢查p+1。
如果p的代表不是自己的話,那么就檢查parent[p]就可以了,因為parent[p]一定是未被覆蓋的點。
在查找p的代表中,用并查集中的“路徑壓縮”優化就可以了
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define re(i,n) for(int i=0;i<n;i++)
5 #define re1(i,n) for(int i=1;i<=n;i++)
6 #define re2(i,n) for(int i=0;i<=n;i++)
7 #define re3(i,n) for(int i=1;i<n;i++)
8 const int N = 205;
9 const int M = 50005;
10 int ans[10];
11 int seg[N][M];
12 int n,m,q;
13 void init(){
14 re(i,n) re2(j,m) {
15 seg[i][j] = j;
16 }
17 re(i,10) ans[i] = 0;
18 }
19 int find(int pos, int x){ return seg[pos][x] == x ? x: seg[pos][x] = find(pos,seg[pos][x]);}
20 void ins(int pos,int l, int r,int c){
21 // cout<<pos<<" "<<l<<" "<<r-1<<" "<<c<<endl;
22 r = find(pos, r);
23 while(l < r) {
24 if(find(pos,l) == l){
25 ans[c] ++;
26 seg[pos][l] = r;
27 l++;
28 }
29 else {
30 l = seg[pos][l];
31 }
32 }
33 }
34 struct query{
35 int x,y,r,c,w,l;
36 char Q;
37 }num[M];
38 int main(){
39 while(~scanf("%d%d%d",&n,&m,&q)){
40 char ch[10];
41 init();
42 re(i,q) {
43 scanf("%s%d%d",ch,&num[i].x,&num[i].y);
44 num[i].Q = ch[0];
45 if(ch[0] == 'R'){
46 scanf("%d%d%d",&num[i].l,&num[i].w,&num[i].c);
47 }
48 else if(ch[0] == 'T'){
49 scanf("%d%d",&num[i].w,&num[i].c);
50 }
51 else {
52 scanf("%d%d",&num[i].r,&num[i].c);
53 }
54 }
55 for(int i=q-1;i>=0;i--){
56 int x = num[i].x,y=num[i].y, r= num[i].r, w=num[i].w,l = num[i].l,c = num[i].c;
57 if(num[i].Q=='C'){
58 int left = max(y - r ,0), right = min(y + r, m-1);
59 ins(x,left,right+1,c);
60 for(int j = 1; j <= r; j++){
61 if(x + j >= n && x - j < 0) break;
62 while((y-left)*(y-left) + j*j > r*r) left ++;;
63 while((right-y)*(right-y) + j*j > r*r) right--;
64 if(x + j < n) ins(x + j, left, right +1 ,c);
65 if(x - j >=0) ins(x - j, left, right +1 ,c);
66 }
67 }
68 else if(num[i].Q=='D'){
69 int left = max(y - r ,0), right = min(y + r, m-1);
70 ins(x,left,right+1,c);
71 for(int j = 1; j <= r; j++){
72 if(x + j >= n && x - j < 0) break;
73 while((y-left)+j > r) left ++;;
74 while((right-y)+j > r) right--;
75 if(x + j < n) ins(x + j, left, right +1 ,c);
76 if(x - j >=0) ins(x - j, left, right +1 ,c);
77 }
78 }
79 else if(num[i].Q=='R'){
80 for(int X = x;X < n && X < x + l ; X++){
81 ins(X,y,min(y+w,m),c);
82 }
83 }
84 else {
85 for(int X = x,W = w/2; X<n && W>=0; X++,W--){
86 int left = max(0,y-W);
87 int right = min(m-1,y+W);
88 ins(X,left,right+1,c);
89 }
90 }
91 }
92 re1(i,9) {cout<<ans[i]; if(i != 9) cout<<" ";} cout<<endl;
93 }
94 }
95
2 #include<cstdio>
3 using namespace std;
4 #define re(i,n) for(int i=0;i<n;i++)
5 #define re1(i,n) for(int i=1;i<=n;i++)
6 #define re2(i,n) for(int i=0;i<=n;i++)
7 #define re3(i,n) for(int i=1;i<n;i++)
8 const int N = 205;
9 const int M = 50005;
10 int ans[10];
11 int seg[N][M];
12 int n,m,q;
13 void init(){
14 re(i,n) re2(j,m) {
15 seg[i][j] = j;
16 }
17 re(i,10) ans[i] = 0;
18 }
19 int find(int pos, int x){ return seg[pos][x] == x ? x: seg[pos][x] = find(pos,seg[pos][x]);}
20 void ins(int pos,int l, int r,int c){
21 // cout<<pos<<" "<<l<<" "<<r-1<<" "<<c<<endl;
22 r = find(pos, r);
23 while(l < r) {
24 if(find(pos,l) == l){
25 ans[c] ++;
26 seg[pos][l] = r;
27 l++;
28 }
29 else {
30 l = seg[pos][l];
31 }
32 }
33 }
34 struct query{
35 int x,y,r,c,w,l;
36 char Q;
37 }num[M];
38 int main(){
39 while(~scanf("%d%d%d",&n,&m,&q)){
40 char ch[10];
41 init();
42 re(i,q) {
43 scanf("%s%d%d",ch,&num[i].x,&num[i].y);
44 num[i].Q = ch[0];
45 if(ch[0] == 'R'){
46 scanf("%d%d%d",&num[i].l,&num[i].w,&num[i].c);
47 }
48 else if(ch[0] == 'T'){
49 scanf("%d%d",&num[i].w,&num[i].c);
50 }
51 else {
52 scanf("%d%d",&num[i].r,&num[i].c);
53 }
54 }
55 for(int i=q-1;i>=0;i--){
56 int x = num[i].x,y=num[i].y, r= num[i].r, w=num[i].w,l = num[i].l,c = num[i].c;
57 if(num[i].Q=='C'){
58 int left = max(y - r ,0), right = min(y + r, m-1);
59 ins(x,left,right+1,c);
60 for(int j = 1; j <= r; j++){
61 if(x + j >= n && x - j < 0) break;
62 while((y-left)*(y-left) + j*j > r*r) left ++;;
63 while((right-y)*(right-y) + j*j > r*r) right--;
64 if(x + j < n) ins(x + j, left, right +1 ,c);
65 if(x - j >=0) ins(x - j, left, right +1 ,c);
66 }
67 }
68 else if(num[i].Q=='D'){
69 int left = max(y - r ,0), right = min(y + r, m-1);
70 ins(x,left,right+1,c);
71 for(int j = 1; j <= r; j++){
72 if(x + j >= n && x - j < 0) break;
73 while((y-left)+j > r) left ++;;
74 while((right-y)+j > r) right--;
75 if(x + j < n) ins(x + j, left, right +1 ,c);
76 if(x - j >=0) ins(x - j, left, right +1 ,c);
77 }
78 }
79 else if(num[i].Q=='R'){
80 for(int X = x;X < n && X < x + l ; X++){
81 ins(X,y,min(y+w,m),c);
82 }
83 }
84 else {
85 for(int X = x,W = w/2; X<n && W>=0; X++,W--){
86 int left = max(0,y-W);
87 int right = min(m-1,y+W);
88 ins(X,left,right+1,c);
89 }
90 }
91 }
92 re1(i,9) {cout<<ans[i]; if(i != 9) cout<<" ";} cout<<endl;
93 }
94 }
95