orz Fop_zz,当然我的题解更暴力

4.琵琶湖
对于T次讯问，倒叙考察之。则问题变成了水面不断下降的情况。这个时候，每一单位时间，会有额外的格子露出水平，并有可能合并原有的不相连的区域。这样的问题可以被描述为对若干集合进行合并，用并查集是最高效的处理方案。总的时间复杂度为O(TlogT+nm)。
暴力的方法可以在这一题中得到20分。而对于n<=1的情况，我们知道任意时间每一个连通块总是单连通的。所以可以利用链表来维护，从而得到这额外的40分部分分。

肯定是要引用 “doc小姐姐” 的题解啦 （快去上面赞她！）。

“ 对于T次讯问，倒叙考察之。 则问题变成了水面不断下降的情况 。这个时候，每一单位时间，会有额外的格子露出水平，并有可能合并原有的不相连的区域。这样的问题可以被描述为 对若干集合进行合并 ，用 并查集 是最高效的处理方案。总的时间复杂度为O(TlogT+nm)。 ”

细节一下 ，可知，倒叙操作时，假如新出现的小方格周围全是海洋，那么它就能提供一个答案值（当成一个小块）。
接着，我们易知， 每次的方格更新最多只会联通它四个方向上的块 ，所以我们 不需要对整个方格整体进行扫描 ，只需要让当前格 与四个方向上块依次进行合并（还没出现的块不合并） 。当发现他们在同一个块上时，不操作。但他们分别属于不同块时，将其合并，并将答案值减一即可。

#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct QUESTION {
    int id, h;
};
struct POINT {
    int x, y, h;    
};
int N, M, T;
vector<POINT> A;
vector<QUESTION> B;
int Cnt, Ans[100005], Fa[1000005], Vis[1000005], Dx[5]={0, 0, 1, 0, -1}, Dy[5]={0, -1, 0, 1, 0};
int ID (int x, int y) {
    if (x<1||x>N||y<1||y>M) return 0;
    return (x-1)*M+y;
}
bool QUESTIONCMP (QUESTION a, QUESTION b) {
    return a.h>b.h;
}
bool POINTCMP (POINT a, POINT b) {
    return a.h>b.h;
}
void INIT () {
    for(int i=1; i<=N*M; i++) Fa[i]=i;
}
int FIND (int x) {
    return x==Fa[x]?x:Fa[x]=FIND(Fa[x]); 
} 
void UNION (int a, int b) {
    int fa=FIND(a), fb=FIND(b); 
    if (fa==fb) return;
    Fa[fa]=fb;
    Cnt--;
}
int main () {

    ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=1; i<=N; i++)
        for(int j=1, h; j<=M; j++) {
            cin >> h;
            A.push_back((POINT){i, j, h}); 
        }
    cin >> T;
    for(int i=1, h; i<=T; i++) {
        cin >> h;   
        B.push_back((QUESTION){i, h});
    }
    sort(A.begin(), A.end(), POINTCMP);
    sort(B.begin(), B.end(), QUESTIONCMP);
    INIT();
    int k=0;
    for(int i=0; i<T; i++) {
        while(k<A.size()&&A[k].h>B[i].h) {
            int id1=ID(A[k].x, A[k].y);
            if (!Vis[id1]) {
                Vis[id1]=1;
                Cnt++;
                for(int j=1; j<=4; j++) {
                    int id2=ID(A[k].x+Dx[j], A[k].y+Dy[j]);
                    if (Vis[id2]) UNION(id1, id2);
                }
            }
            k++;
        }
        Ans[B[i].id]=Cnt;   
    }
    for(int i=1; i<=T; i++) cout << Ans[i] << " ";
    return  0;
    
}

题解

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn = 1000*1000+5;
int n, m, T, u, c = 1, v, t, x[maxn], y[maxn], a[maxn], pa[maxn], M[1000+5][1000+5];
int e[maxn];
pair<int, int>P[maxn];
int findset(int x){return pa[x] == x ? x : pa[x] = findset(pa[x]);}
int read(){
char t = getchar();
while(!isdigit(t))t = getchar();
int r = 0;
while(isdigit(t)){
r = r*10+t-'0';
t = getchar();
}
return r;
}
int main()
{
n = read(), m = read();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
u = read();
M[i][j] = u;
P[c] = make_pair(u, c);
x[c] = i, y[c] = j;
c++;
}
}
for(int i = 1; i < c; i++)pa[i] = i;
T = read(); t = T;
for(int i = 1; i <= T; i++)a[i] = read();
sort(P, P+c), c--;
int count = c, co = 0;
while(T > 0 && c > 0){
while(T > 0&&P[c].first <= a[T]){e[T] = count-c-co; T--;}
while(c > 0&&P[c].first > a[T]){
int k = P[c].second;
int X = x[k], Y = y[k];
if(X - 1 >= 0 && M[X-1][Y] > a[T]){
u = findset(k), v = findset(k-m);
if(u != v){pa[u] = v; co++; }
}
if(Y - 1 >= 0 && M[X][Y-1] > a[T]){
u = findset(k), v = findset(k-1);
if(u != v){pa[u] = v; co++; }
}
if(X + 1 < n && M[X+1][Y] > a[T]){
u = findset(k), v = findset(k+m);
if(u != v){pa[u] = v; co++; }
}
if(Y + 1 < m && M[X][Y+1] > a[T]){
u = findset(k), v = findset(k+1);
if(u != v){pa[u] = v; co++; }
}
c--;
}
}
while(T)e[T--] = 1;
for(int i = 1; i <= t; i++){
printf("%d", e[i]);
if(i != t)printf(" ");
}
return 0;
}

#include<algorithm>
#include<iostream>
#include<stdio.h>
using namespace std;

int dir[2][5]={{1,-1,0,0},{0,0,1,-1}};

int n,m;
int h[1005][1005];
int father[1000005];
typedef pair<int,int> nodexy;
inline nodexy getxy(int t){
return make_pair((t-1)/m+1,(t-1)%m+1);
}
inline int getrl(int x,int y){
return (x-1)*m+y;
}
int T,t[100005];
int ans[100005];
int head[100005];
int NEXT[1000005];

int find(int x){
if(father[x]==x) return x;
father[x]=find(father[x]);
return father[x];
}

int main(){
cin>>n>>m;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{ scanf("%d",&h[i][j]);}
cin>>T;
for(i=1;i<=T;i++)
{ scanf("%d",&t[i]);}
int x,y,k;
nodexy xy;
for(i=1;i<=n*m;i++)
{ x=(i-1)/m+1; y=(i-1)%m+1;
int bot=0,top=T,mid=T/2;
while(bot<top)
{ if(t[mid]<h[x][y])
{ bot=mid;}
else
{ top=mid-1;}
mid=(bot+top+1)/2;
}
h[x][y]=mid;
NEXT[i]=head[mid];
head[mid]=i;
}
for(i=T;i>=1;i--)
{ k=head[i];
ans[i]=ans[i+1];
while(k)
{ ans[i]++;
father[k]=k;
k=NEXT[k];}
k=head[i];
int x1,y1,f0,f1;
while(k)
{ xy=getxy(k);
x=xy.first;
y=xy.second;
for(j=0;j<4;j++)
{ x1=x+dir[0][j];
y1=y+dir[1][j];
if(x1>=1&&x1<=n&&y1>=1&&y1<=m){
f0=find(getrl(x,y));
f1=find(getrl(x1,y1));
if(f0!=f1&&f0&&f1){
ans[i]--;
father[f0]=f1;
}}
}
k=NEXT[k];
}
}
for(i=1;i<=T;i++)
printf("%d ",ans[i]);
return 0;
}

请联系我，，，数据，，dllp555@163.com

有没有测试数据啊。。。