通过离线将操作建树,即可得到最终存在的操作。

然后逆着操作的顺序,倒着进行染色,对于每行维护一个并查集即可。

时间复杂度$O(n(n+m))$。

#include<cstdio>
const int N=1010,M=100010;
int n,m,i,j,x,C,X1,Y1,X2,Y2,f[M],cnt,pos[M],e[M][5],col[N][N];char ch;
struct DSU{
int f[N];
void init(){for(int i=0;i<=n+1;i++)f[i]=i;}
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
}g[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
read(n),read(m),read(m);
for(i=1;i<=m;i++){
while((ch=getchar())!='P'&&ch!='S'&&ch!='L');
if(ch=='P'){
f[i]=x;x=i;
for(j=0;j<5;j++)read(e[i][j]);
}
if(ch=='S')pos[++cnt]=x;
if(ch=='L')read(x),x=pos[x];
}
for(i=0;i<n;i++)for(j=0;j<n;j++)col[i][j]=1;
for(i=0;i<n;i++)g[i].init();
while(x){
C=e[x][0],X1=e[x][1],Y1=e[x][2],X2=e[x][3],Y2=e[x][4];
for(i=X1;i<=X2;i+=2)for(j=g[i].F(Y1);j<=Y2;j=g[i].F(j+2))g[i].f[j]=j+2,col[i][j]=C;
for(i=X1+1;i<=X2;i+=2)for(j=g[i].F(Y1+1);j<=Y2;j=g[i].F(j+2))g[i].f[j]=j+2,col[i][j]=C;
x=f[x];
}
for(i=0;i<n;puts(""),i++)for(j=0;j<n;j++)printf("%d ",col[i][j]);
return 0;
}

  

最新文章

  1. Git使用详细教程(二)
  2. loadrunner数据库MySQL参数化列表乱码问题
  3. C++程序结构---1
  4. Delphi中nil和null的区别
  5. Windows Phone 同步方式获取网络类型
  6. java:高速排序算法与冒泡排序算法
  7. Ext.ux.form.SuperBoxSelect
  8. FZU 2089 数字游戏
  9. PKU-1704-Georgia and Bob
  10. 【技术干货】听阿里云CDN安防技术专家金九讲SystemTap使用技巧
  11. linux下Tomcat 安装后执行startup.sh,出现– Cannot find …bin/catalina.sh
  12. vue2.0项目引入element-ui
  13. Python_FTP通讯软件
  14. .NET快速信息化系统开发框架 V3.2 -&gt; WinForm“组织机构管理”界面组织机构权限管理采用新的界面,操作权限按模块进行展示
  15. WPF-------依赖项属性
  16. chrome 下 input[file] 元素cursor设置pointer不生效的解决
  17. “一切都是消息”--iMSF(即时消息服务框架)之【发布-订阅】模式
  18. Linux设置和查看环境变量的方法 详解
  19. Html5多媒体相关的API---video
  20. PLsql登录数据库提示密码即将过期-

热门文章

  1. postgresql导入及导出
  2. win7下python3.4 ImportError: No module named &#39;MySQLdb&#39;错误解决方法
  3. bootstrap的验证和确认对话框
  4. JustSniffer
  5. Sexagenary Cycle(天干地支法表示农历年份)
  6. Big Data, MapReduce, Hadoop, and Spark with Python
  7. Java代码实现excel数据导入到Oracle
  8. OGG异常处理
  9. hdu 3032 sg打表找规律 *
  10. Linux下常用命令