Codeforces Round #368 (Div. 2) D. Persistent Bookcase （离线算法+lazy标记优化）

链接

D. Persistent Bookcase

题意

给出一个n*m的矩阵，代表有n个书架，每个书架有m个位置用来放书。接下来有q个询问，(1, i, j)和(2, i, j)分别表示从i书架的j位置添加/删除一本书（如果[i][j]已存在书则添加操作无效，删除亦然），(3, i)表示将i书架的每个位置取反，(4, k)表示将目前的状态（所有书架的状态）退回到第k个询问之后。对每个询问输出一个值，代表该询问执行后所有书架的书籍个数之和。

思路

主要难在操作4上，要使该问题的整个状态回退到某一步。

该问题可以利用离线数据结构+回溯解决。需要对q个询问之间的关系进行建树，如果第i+1个询问是普通操作123，则该询问是第i个询问的next之一，如果第i+1个询问是回退操作4，则该询问是第k个询问的next之一（k是其回退到的那个询问）。建树完毕后，对该状态树进行深搜，当处理到i节点时，如果它的next有多个（说明有其他询问回退至该步骤），对每个next[j]搜下去即可。注意需要对树进行回溯，撤销其后继节点对书架的影响。

在执行询问的时候可以模拟去改变书架上位置的状态，但是由于操作是置1置0和异或，我们用lazy标记去标记某书架是否被异或过，这样可以使每个询问都在O(1)时间内完成。

PS：其实模拟也可以过，数据不强。下面代码给出两个版本，后者加了lazy标记优化。

代码

模拟询问操作

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define maxn (100010)
int N, M, Q;
struct _node
{
    int k, i, j, n;
    vector<int> next;
} node[maxn];
int bookcase[][], n;
bool exec(int i, int j, int o)
{
    switch(o)
    {
    case :
        if(bookcase[i][j]) return false;
        n += (bookcase[i][j] = );
        return true;
    case -:
        if(!bookcase[i][j]) return false;
        n--;
        bookcase[i][j] = ;
        return true;
    case :
        int p = , q = ;
        for(int k = ; k <= M; k++)
        {
            if(bookcase[i][k]) p++;
            else q++;
            bookcase[i][k] ^= ;
        }
        n = n - p + q;
        return true;
    }
    return true;
}
void dfs(int i)
{
    bool ret = exec(node[i].i, node[i].j, node[i].k);
    node[i].n = n;
    for(unsigned int j = ; j < node[i].next.size(); j++)
        dfs(node[i].next[j]);
    if(ret) exec(node[i].i, node[i].j, -node[i].k);
}
int main()
{
    cin >> N >> M >> Q;
    for(int i = , op, a, b; i <= Q; i++)
    {
        scanf("%d", &op);
        if(op < )
            scanf("%d%d", &a, &b);
        else
            scanf("%d", &a);
        node[i].i = a, node[i].j = b;
        if(op == ) op = -;
        if(op == ) op = ;
        node[i].k = op;
        if(op != ) node[i-].next.push_back(i);
        else node[a].next.push_back(i);
    }
    node[].next.push_back();
    node[].k = ;
    dfs();
    for(int i = ; i <= Q; i++)
        printf("%d\n", node[i].n);
    return ;
}
           

lazy标记优化询问操作

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define maxn (100010)
int N, M, Q;
struct _node
{
    int k, i, j, n;
    vector<int> next;
} node[maxn];
int bookcase[][], lazy[], books[], n;
bool exec(int i, int j, int o)
{
    switch(o)
    {
    case :
        if(lazy[i] ^ bookcase[i][j])
            return false;
        n++;
        books[i]++;
        bookcase[i][j] ^= ;
        return true;
    case -:
        if(!(lazy[i] ^ bookcase[i][j]))
            return false;
        n--;
        books[i]--;
        bookcase[i][j] ^= ;
        return true;
    case :
        lazy[i] ^= ;
        n -= books[i];
        books[i] = M - books[i];
        n += books[i];
        return true;
    }
    return true;
}
void dfs(int i)
{
    bool ret = exec(node[i].i, node[i].j, node[i].k);
    node[i].n = n;
    for(unsigned int j = ; j < node[i].next.size(); j++)
        dfs(node[i].next[j]);
    if(ret) exec(node[i].i, node[i].j, -node[i].k);
}
int main()
{
    cin >> N >> M >> Q;
    for(int i = , op, a, b; i <= Q; i++)
    {
        scanf("%d", &op);
        if(op < )
            scanf("%d%d", &a, &b);
        else
            scanf("%d", &a);
        node[i].i = a, node[i].j = b;
        if(op == ) op = -;
        if(op == ) op = ;
        node[i].k = op;
        if(op != ) node[i-].next.push_back(i);
        else node[a].next.push_back(i);
    }
    node[].next.push_back();
    node[].k = ;
    dfs();
    for(int i = ; i <= Q; i++)
        printf("%d\n", node[i].n);
    return ;
}
           

结果