题意：n*n的矩阵，m次赋值一个子矩阵为c，最后输出答案。
n<=1e3 m<=1e5
解：倒序处理。
拆行处理。
每行内并查集维护未被赋值的地方。
这样每个地方最多被赋值一次，每次修改要访问n行，时间复杂度是O(n(n + m))
#include <cstdio>
inline void read(int &x) {
char c = getchar();
x = ;
while(c < '' || c > '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
}
const int N = , M = ;
struct Node {
int opt, c, x, y, xx, yy;
}a[M];
int n, k, m, fa[M], sv[M], num, path[M], top;
char s[];
struct ROW {
int a[N], fa[N];
ROW() {
for(int i = ; i < N; i++) {
fa[i] = i;
a[i] = ;
}
}
int find(int x) {
if(x == fa[x]) {
return x;
}
return fa[x] = find(fa[x]);
}
inline void change(int v, int l, int r) {
int p = find(r);
while(p >= l) {
a[p] = v;
fa[p] = find(p - );
p = fa[p];
}
return;
}
}row1[N], row2[N];
int main() {
read(n);
read(k);
read(m);
for(int i = ; i <= m; i++) {
scanf("%s", s);
if(s[] == 'P') { // print
fa[i] = i - ;
a[i].opt = ;
read(a[i].c);
read(a[i].x);
read(a[i].y);
read(a[i].xx);
read(a[i].yy);
}
else if(s[] == 'S') { // save
fa[i] = i - ;
sv[++num] = i;
}
else { // load
int x;
//scanf("%d", &x);
read(x);
fa[i] = sv[x];
}
}
int x = m;
while(x) {
path[++top] = x;
x = fa[x];
}
for(int e = ; e <= top; e++) {
int i = path[e];
if(!a[i].opt) {
continue;
}
for(int j = a[i].x + ; j <= a[i].xx + ; j++) {
//printf(" j = %d c = %d \n", j, a[i].c);
if((a[i].x - + a[i].y) & ) {
row1[j].change(a[i].c, a[i].y + , a[i].yy + );
}
else {
row2[j].change(a[i].c, a[i].y + , a[i].yy + );
}
}
}
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
if((i + j) & ) {
printf("%d ", row2[i].a[j]);
}
else {
printf("%d ", row1[i].a[j]);
}
}
puts("");
}
return ;
}AC代码
说一下原来的题意：
有个矩阵，每次间隔染色一个子矩阵(类似国际象棋那样，左上角要染)，还要支持存档/读档。最后一次输出。
#include <cstdio>
#include <algorithm> inline void read(int &x) {
char c = getchar();
x = ;
while(c < '' || c > '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} const int N = , M = ; struct Node {
int opt, c, x, y, xx, yy;
}a[M]; int n, k, m, fa[M], sv[M], num, path[M], top;
char s[];
int sa[N * N * ], sb[N * N * ], sc[N * N * ], sd[N * N * ];
int tag1[N * N * ], tag2[N * N * ], G[N][N]; void build(int x, int y, int xx, int yy, int o) {
if(x == xx && y == yy) {
tag1[o] = ;
return;
}
int mx = (x + xx) >> ;
int my = (y + yy) >> ; sa[o] = ++num;
build(x, y, mx, my, num); if(yy > y) {
sb[o] = ++num;
build(x, my + , mx, yy, num);
}
if(xx > x) {
sc[o] = ++num;
build(mx + , y, xx, my, num);
} if(yy > y && xx > x) {
sd[o] = ++num;
build(mx +, my + , xx, yy, num);
}
return;
} inline void pushdown(int x, int y, int xx, int yy, int o) {
int mx = (x + xx) >> ;
int my = (y + yy) >> ;
if(tag1[o]) {
int t = tag1[o];
if(sa[o]) {
tag1[sa[o]] = t;
}
if(sb[o]) {
if((my - y + ) & ) {
tag2[sb[o]] = t;
}
else {
tag1[sb[o]] = t;
}
}
if(sc[o]) {
if((mx - x + ) & ) {
tag2[sc[o]] = t;
}
else {
tag1[sc[o]] = t;
}
}
if(sd[o]) {
if((mx - x + my - y + ) & ) {
tag1[sd[o]] = t;
}
else {
tag2[sd[o]] = t;
}
}
tag1[o] = ;
}
if(tag2[o]) {
int t = tag2[o];
if(sa[o]) {
tag2[sa[o]] = t;
}
if(sb[o]) {
if((my - y + ) & ) {
tag1[sb[o]] = t;
}
else {
tag2[sb[o]] = t;
}
}
if(sc[o]) {
if((mx - x + ) & ) {
tag1[sc[o]] = t;
}
else {
tag2[sc[o]] = t;
}
}
if(sd[o]) {
if((mx - x + my - y + ) & ) {
tag2[sd[o]] = t;
}
else {
tag1[sd[o]] = t;
}
}
tag2[o] = ;
}
return;
} int X, XX, Y, YY;
inline void change(int v, int f, int x, int y, int xx, int yy, int o) {
int mx = (x + xx) >> ;
int my = (y + yy) >> ;
if(X <= x && xx <= XX) {
if(Y <= y && yy <= YY) {
if(f) {
tag1[o] = v;
}
else {
tag2[o] = v;
}
return;
}
}
pushdown(x, y, xx, yy, o);
if(X <= mx && Y <= my) { // sa
change(v, f, x, y, mx, my, sa[o]);
}
if(X <= mx && my < YY) { // sb
if((my - y + ) & ) {
change(v, f ^ , x, my + , mx, yy, sb[o]);
}
else {
change(v, f, x, my + , mx, yy, sb[o]);
}
}
if(mx < XX && Y <= my) { // sc
if((mx - x + ) & ) {
change(v, f ^ , mx + , y, xx, my, sc[o]);
}
else {
change(v, f, mx + , y, xx, my, sc[o]);
}
}
if(mx < XX && my < YY) { // sd
if((mx - x + my - y + ) & ) {
change(v, f, mx + , my + , xx, yy, sd[o]);
}
else {
change(v, f ^ , mx + , my + , xx, yy, sd[o]);
}
}
return;
} void ed(int x, int y, int xx, int yy, int o) {
if(x == xx && y == yy) {
G[x][y] = tag1[o];
return;
}
int mx = (x + xx) >> ;
int my = (y + yy) >> ;
pushdown(x, y, xx, yy, o);
ed(x, y, mx, my, sa[o]);
if(yy > y) {
ed(x, my + , mx, yy, sb[o]);
}
if(xx > x) {
ed(mx + , y, xx, my, sc[o]);
}
if(xx > x && yy > y) {
ed(mx + , my + , xx, yy, sd[o]);
}
return;
} int main() { read(n);
read(k);
read(m); for(int i = ; i <= m; i++) {
scanf("%s", s);
if(s[] == 'P') { // print
fa[i] = i - ;
a[i].opt = ;
read(a[i].c);
read(a[i].x);
read(a[i].y);
read(a[i].xx);
read(a[i].yy);
}
else if(s[] == 'S') { // save
fa[i] = i - ;
sv[++num] = i;
}
else { // load
int x;
read(x);
fa[i] = sv[x];
}
} int x = m;
while(x) {
path[++top] = x;
x = fa[x];
}
std::reverse(path + , path + top + );
num = ;
build(, , n, n, );
for(int e = ; e <= top; e++) {
int i = path[e];
if(!a[i].opt) {
continue;
}
a[i].x++;
a[i].xx++;
a[i].y++;
a[i].yy++;
X = a[i].x;
Y = a[i].y;
XX = a[i].xx;
YY = a[i].yy;
if((a[i].x - + a[i].y) & ) {
change(a[i].c, , , , n, n, );
}
else {
change(a[i].c, , , , n, n, );
}
} ed(, , n, n, );
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
printf("%d ", G[i][j]);
}
puts("");
}
return ;
}
四分树
这是考场上写的，四分树每次修改貌似是O(n)的，但是卡成6s......只有75分。
话说我第一次写四分树居然是在考场上，而且一个字符都没调就一次写对了......
时间复杂度到底是多少呀......nm的话应该能过呀？莫非是我常数大？