2010-1083

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

'''题目大意'''[[BR]]
给定DoIt的地形(n*m的格子表示每个海拔)，海平面开始为0，海水从外面淹进来，每年海平面上升一米。
DoIt每年的收入为当年的一个系数A与各个小岛面积通过公式计算得到。
若干个查询，包括年份d和系数A，求DoIt在第d年的总收入。

'''解法'''[[BR]]
第一步：求得每个格子被淹没的时间。
由于水是从外面淹进来的，所以如果一个海拔很低的地方周围都被海拔很高的地方围着，那么它被淹没的时间就不是海平面到达它的高度的时间。
这步的方法可以用类似最短路的方法来做，实际上就是拿个priority_queue处理一下就好。

第二步：查询。
可以先读入所有查询，然后排个序，d大的查询先做。
然后反过来模拟海平面下降的过程，这时就相当于格子逐个凸出来。
用并查集可以维护当前每个小岛的连通状况。
但查询的时候需要获得每个小岛的面积，一个比较方便的方法是利用map<int, int>表示面积为first的小岛个数有second个。
每次查询就是从头到尾扫描一次map，套一下公式计算一下求个和就好了。
但是map的维护每次需要O(logn)。由于查询时候需要从头到尾扫描一次map，而map的first为0-MAXN*MAXN中的整数。
所以可以自己写个list来实现这个map，维护的代价变成O(1)。具体看代码，注释了的部分是用map实现的。

'''代码'''
{{{
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

const int MAXN = 510;
const int MAXQ = 10010;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

priority_queue<pair<int, int> , vector<pair<int, int> >, greater<pair<int, int> > > Q;
pair<int, int> Queue[MAXN * MAXN];
pair<pair<int, int>, int> ask[MAXQ];
//map<int, int> info;
//map<int, int> :: iterator it;
int h[MAXN][MAXN], bits[MAXN * MAXN + 1];
int n, m, q;

int HEAD, TAIL, tot[MAXN * MAXN], last[MAXN * MAXN], next[MAXN * MAXN];

struct DS {
    int father[MAXN * MAXN], size[MAXN * MAXN];   

    void init(int n) {
        memset(father, 0, sizeof(father[0]) * n);
    }

    int getFather(int x) {
        int tx = x;
        while (father[x] != x) x = father[x];
        while (father[tx] != x) {
            int tmp = father[tx];
            father[tx] = x;
            tx = tmp;   
        }   
        return x;
    }

    bool isFriend(int x, int y) {
        x = getFather(x);
        y = getFather(y);
        return x == y;   
    }

    void setFriend(int x, int y) {
        y = getFather(y);
        size[x] += size[y];
        father[y] = x;   
    } 

    int query(int x) {
        x = getFather(x);
        return size[x];   
    }
}ds;

bool cmp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b) {
    return a.first.second < b.first.second;   
}

inline int max(int a, int b) {
    return a > b ? a : b;   
}

inline int MP(int x, int y) {
    return x * m + y;
}

inline void MP(int pos, int &x, int &y) {
    x = pos / m;
    y = pos % m;   
}

inline bool valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;   
}

inline void init() {

    for (int i = 0; i <= n * m; i++) {
        tot[i] = 0;   
    }
    HEAD = n * m + 1;
    TAIL = n * m + 2;
    next[HEAD] = TAIL;
    last[TAIL] = HEAD;

//    info.clear();
    ds.init(n * m);
    while (!Q.empty()) Q.pop();
}

inline void dec(int size) {
    if (tot[size] == 1) {
//        info.erase(size);   
        next[last[size]] = next[size];
        last[next[size]] = last[size];
    }
//        info[size]--;   
    tot[size]--;

}

inline void inc(int size) {
    if (tot[size] == 0) {
        next[last[TAIL]] = size;
        last[size] = last[TAIL];
        next[size] = TAIL;
        last[TAIL] = size;
    } 
    tot[size]++;
//    info[size]++;   
}

inline int count(int a) {
//    int tot = 0;
/*    for (it = info.begin(); it != info.end(); it++) {
        //if (it->second) printf("(%d, %d)\n", it->first, it->second);
        tot += it->second * (1 << bits[(it->first) & a]);   
    }*/
    int cur = next[HEAD], ret = 0;
    while (cur != TAIL) {
        ret += tot[cur] * (1 << bits[cur & a]);
        cur = next[cur];
    }
    return ret;
}

int main() {

    bits[0] = 0;
    for (int i = 1; i <= MAXN * MAXN; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }

    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                scanf("%d", &h[i][j]);
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    Q.push(make_pair(h[i][j], MP(i, j)));   
                    ds.father[MP(i, j)] = 1;    // 1: has already in the priority_queue
                }   
            }
        int tot = 0;
        while (!Q.empty()) {
            int cur = Q.top().first, pos = Q.top().second, x, y;
            MP(pos, x, y);
            Q.pop();
            ds.father[pos] = -1;        // -1: has removed from the priority_queue, under the water
            Queue[tot++] = make_pair(pos, cur);     // <position(x, y), height>
            for (int k = 0; k < 4; k++) {
                int i = x + dx[k], j = y + dy[k], p;    // water flow to adjacent grids
                if (valid(i, j) && ds.father[p = MP(i, j)] == 0) {  // not in the priority_queue
                    Q.push(make_pair(max(h[i][j], cur), p));    // flooded time is max(cur_height, its own height)                    
                    ds.father[p] = 1;   // marked new item in the priority_queue
                }
            }                        
        }
        // after the above process, Queue's items are ordered by their flooded time

        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            int d, a;
            scanf("%d %d", &d, &a);
            ask[i] = make_pair(make_pair(d, i), a);   // <day, query_id, a>
        }        
        sort(ask, ask + q);     // ordered by day
        tot--;
        for (int i = q - 1; i >= 0; i--) {
            while (tot >= 0 && Queue[tot].second > ask[i].first.first) {    // flooded time > current time
                int pos = Queue[tot].first;
                tot--;
                ds.father[pos] = pos;       // DSet: set father = itself, out of water
                ds.size[pos] = 1;           // DSet: set size = 1
                inc(1);
                int x, y, xx, yy, p, tmp;
                MP(pos, x, y);
                for (int k = 0; k < 4; k++) {
                    xx = x + dx[k], yy = y + dy[k];     // DSet: check adjacent out-of-water grids
                    if (valid(xx, yy) && ds.father[p = MP(xx, yy)] != -1 && !ds.isFriend(pos, p)) {
                        //printf("now size = %d\n", (int)info.size());
                        dec(tmp = ds.query(p));     // join pos(x, y) and p(xx, yy)
                        dec(ds.size[pos]);
                        inc(tmp + ds.size[pos]);
                        ds.setFriend(pos, p);
                        //printf("new size = %d\n", (int)info.size());
                    }
                }
            }
            ask[i].second = count(ask[i].second);
        }        
        sort(ask, ask + q, cmp);        // ordered by query_id
        for (int i = 0; i < q; i++) {
            printf("%d\n", ask[i].second);    
        }
    }   
    return 0;    
}

}}}

题目大意

给定DoIt的地形(n*m的格子表示每个海拔)，海平面开始为0，海水从外面淹进来，每年海平面上升一米。

DoIt每年的收入为当年的一个系数A与各个小岛面积通过公式计算得到。

若干个查询，包括年份d和系数A，求DoIt在第d年的总收入。

解法

第一步：求得每个格子被淹没的时间。

由于水是从外面淹进来的，所以如果一个海拔很低的地方周围都被海拔很高的地方围着，那么它被淹没的时间就不是海平面到达它的高度的时间。

这步的方法可以用类似最短路的方法来做，实际上就是拿个priority_queue处理一下就好。

第二步：查询。

可以先读入所有查询，然后排个序，d大的查询先做。

然后反过来模拟海平面下降的过程，这时就相当于格子逐个凸出来。

用并查集可以维护当前每个小岛的连通状况。

但查询的时候需要获得每个小岛的面积，一个比较方便的方法是利用map表示面积为first的小岛个数有second个。

每次查询就是从头到尾扫描一次map，套一下公式计算一下求个和就好了。

但是map的维护每次需要O(logn)。由于查询时候需要从头到尾扫描一次map，而map的first为0-MAXN*MAXN中的整数。

所以可以自己写个list来实现这个map，维护的代价变成O(1)。具体看代码，注释了的部分是用map实现的。

代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN = 510;
const int MAXQ = 10010;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
priority_queue<pair<int, int> , vector<pair<int, int> >, greater<pair<int, int> > > Q;
pair<int, int> Queue[MAXN * MAXN];
pair<pair<int, int>, int> ask[MAXQ];
//map<int, int> info;
//map<int, int> :: iterator it;
int h[MAXN][MAXN], bits[MAXN * MAXN + 1];
int n, m, q;
int HEAD, TAIL, tot[MAXN * MAXN], last[MAXN * MAXN], next[MAXN * MAXN];
struct DS {
    int father[MAXN * MAXN], size[MAXN * MAXN];   
    void init(int n) {
        memset(father, 0, sizeof(father[0]) * n);
    }
    int getFather(int x) {
        int tx = x;
        while (father[x] != x) x = father[x];
        while (father[tx] != x) {
            int tmp = father[tx];
            father[tx] = x;
            tx = tmp;   
        }   
        return x;
    }
    bool isFriend(int x, int y) {
        x = getFather(x);
        y = getFather(y);
        return x == y;   
    }
    void setFriend(int x, int y) {
        y = getFather(y);
        size[x] += size[y];
        father[y] = x;   
    } 
    int query(int x) {
        x = getFather(x);
        return size[x];   
    }
}ds;
bool cmp(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b) {
    return a.first.second < b.first.second;   
}
inline int max(int a, int b) {
    return a > b ? a : b;   
}
inline int MP(int x, int y) {
    return x * m + y;
}
inline void MP(int pos, int &x, int &y) {
    x = pos / m;
    y = pos % m;   
}
inline bool valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;   
}
inline void init() {
    for (int i = 0; i <= n * m; i++) {
        tot[i] = 0;   
    }
    HEAD = n * m + 1;
    TAIL = n * m + 2;
    next[HEAD] = TAIL;
    last[TAIL] = HEAD;
//    info.clear();
    ds.init(n * m);
    while (!Q.empty()) Q.pop();
}
inline void dec(int size) {
    if (tot[size] == 1) {
//        info.erase(size);   
        next[last[size]] = next[size];
        last[next[size]] = last[size];
    }
//        info[size]--;   
    tot[size]--;
}
inline void inc(int size) {
    if (tot[size] == 0) {
        next[last[TAIL]] = size;
        last[size] = last[TAIL];
        next[size] = TAIL;
        last[TAIL] = size;
    } 
    tot[size]++;
//    info[size]++;   
}
inline int count(int a) {
//    int tot = 0;
/*    for (it = info.begin(); it != info.end(); it++) {
        //if (it->second) printf("(%d, %d)\n", it->first, it->second);
        tot += it->second * (1 << bits[(it->first) & a]);   
    }*/
    int cur = next[HEAD], ret = 0;
    while (cur != TAIL) {
        ret += tot[cur] * (1 << bits[cur & a]);
        cur = next[cur];
    }
    return ret;
}
int main() {
    bits[0] = 0;
    for (int i = 1; i <= MAXN * MAXN; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                scanf("%d", &h[i][j]);
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    Q.push(make_pair(h[i][j], MP(i, j)));   
                    ds.father[MP(i, j)] = 1;    // 1: has already in the priority_queue
                }   
            }
        int tot = 0;
        while (!Q.empty()) {
            int cur = Q.top().first, pos = Q.top().second, x, y;
            MP(pos, x, y);
            Q.pop();
            ds.father[pos] = -1;        // -1: has removed from the priority_queue, under the water
            Queue[tot++] = make_pair(pos, cur);     // <position(x, y), height>
            for (int k = 0; k < 4; k++) {
                int i = x + dx[k], j = y + dy[k], p;    // water flow to adjacent grids
                if (valid(i, j) && ds.father[p = MP(i, j)] == 0) {  // not in the priority_queue
                    Q.push(make_pair(max(h[i][j], cur), p));    // flooded time is max(cur_height, its own height)                    
                    ds.father[p] = 1;   // marked new item in the priority_queue
                }
            }                        
        }
        // after the above process, Queue's items are ordered by their flooded time
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            int d, a;
            scanf("%d %d", &d, &a);
            ask[i] = make_pair(make_pair(d, i), a);   // <day, query_id, a>
        }        
        sort(ask, ask + q);     // ordered by day
        tot--;
        for (int i = q - 1; i >= 0; i--) {
            while (tot >= 0 && Queue[tot].second > ask[i].first.first) {    // flooded time > current time
                int pos = Queue[tot].first;
                tot--;
                ds.father[pos] = pos;       // DSet: set father = itself, out of water
                ds.size[pos] = 1;           // DSet: set size = 1
                inc(1);
                int x, y, xx, yy, p, tmp;
                MP(pos, x, y);
                for (int k = 0; k < 4; k++) {
                    xx = x + dx[k], yy = y + dy[k];     // DSet: check adjacent out-of-water grids
                    if (valid(xx, yy) && ds.father[p = MP(xx, yy)] != -1 && !ds.isFriend(pos, p)) {
                        //printf("now size = %d\n", (int)info.size());
                        dec(tmp = ds.query(p));     // join pos(x, y) and p(xx, yy)
                        dec(ds.size[pos]);
                        inc(tmp + ds.size[pos]);
                        ds.setFriend(pos, p);
                        //printf("new size = %d\n", (int)info.size());
                    }
                }
            }
            ask[i].second = count(ask[i].second);
        }        
        sort(ask, ask + q, cmp);        // ordered by query_id
        for (int i = 0; i < q; i++) {
            printf("%d\n", ask[i].second);    
        }
    }   
    return 0;    
}