BZOJ3189 : [Coci2011] Slika

Slika

The question ：

First , The title has a coat , It is the concept that the operation has version , He can archive and read files , But we know that , We build the operation into a tree , When he reads a document, he goes back to an ancestor , The only effect on the final shape is the stacking operation from the current point to the root .
Then we will build a tree , Maintain a fa Array , Finally, we can know the effective operation and sequence by constantly skipping our ancestors .
Practice one ：
Maintain the rightmost point of the current row that is not stained with a union query set .
We put the operation , Reverse order , Because the operation of dyeing in the back will cover the operation of dyeing in the front .
Then, a colored interval will not be traversed repeatedly .
So the overall complexity is （$m\ast n+n\ast n$）.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n,m) for(int i=n;i<=m;i++)
#define repp(i,n,m) for(int i=n;i>=m;i--)

int n,k,m;
char op[10];
int sa[100040];
int cnts=0,tot=0;
struct node{
    
	int cl;
	int x1,y1,x2,y2;
}z[100040];
queue<int>q;
int f[100050];
int fa[1010][1010];
int col[1004][1004];
int find(int x,int i){
    
	if(x==fa[i][x])return x;
	return fa[i][x]=find(fa[i][x],i);
}
int main(){
    
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>k>>m;
	int now=0;
	for(int i=1;i<=m;i++){
    
		cin>>op;
		if(op[0]=='P'){
    
			tot++;
			cin>>z[tot].cl>>z[tot].x1>>z[tot].y1>>z[tot].x2>>z[tot].y2;
			f[tot]=now;
			now=tot;
		}else if(op[0]=='S'){
    
			cnts++;
			sa[cnts]=now;
		}else{
    
			int a;
			cin>>a;
			now=sa[a];
		}
	}
	for(int i=0;i<n+2;i++){
    
		for(int j=0;j<n+2;j++)col[i][j]=1,fa[i][j]=j;
	}
	while(now){
    
		int u=now;
		for(int i=z[u].x1;i<=z[u].x2;i++){
    
			int p;
			if((i-z[u].x1)%2==0)p=find(z[u].y1,i);
			else p=find(z[u].y1+1,i);
			
			for(int j=p;j<=z[u].y2;j=find(j+2,i)){
    
				fa[i][j]=j+2;
				col[i][j]=z[u].cl;
			}
		}
		now=f[now];
	}
	for(int i=0;i<n;i++){
    
		for(int j=0;j<n;j++)cout<<col[i][j]<<" ";
		cout<<"\n";
	}
	return 0;
}

Practice two ：