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 ;
}
           

結果