省赛选拔-单调队列

发表于 | 更新于 | 阅读次数：
本文字数： 3.5k | 阅读时长 ≈ 3 分钟

单调队列写法。

Py&hyh想脱单

Description

总所周知,，py和hyh有十分浓烈的脱单意愿，但是非常不幸，在一个风和日丽的下午，他们穿越到一个没有妹子的世界，他必须回答一个问题才能回到本来的世界，这个问题是给出一个nm的矩阵，然后有q次操作，每一个操作，给出xi,yi,ti,表示在ti时刻摧毁(xi,yi)这个格子，然后他们要求出一个最早时刻，出现至少一个kk的矩阵被毁坏，注意：一个kk矩阵被毁坏的意思是某一个kk的矩阵中的每一个格子都被摧毁过一次或一次以上。聪明的acmer能帮他们回答这个问题吗（如果没人能ac这个题，就代表他们两个没有脱单的可能了哦）

Input

Input：采用多组输入第一行输入n,m,k,q,(1 ≤ n, m ≤ 500, 1 ≤ k ≤ min(n, m), 1 ≤ q ≤ n·m)分别代表nm的矩阵，kk的矩阵，和q次操作接下来q行每一行输入xi,yi,ti(1 ≤ xi ≤ n, 1 ≤ yi ≤ m, 0 ≤ t ≤ 1e6)，代表，在ti这个时刻，xi，yi这个位置会被摧毁

Output

Out：输出一行，代表最早时刻出现至少一个k*k的矩阵被毁坏如果永远不存在这一个时刻，输出-1

Sample Input 1

2 3 2 5

2 1 8

2 2 8

1 2 1

1 3 4

2 3 2

Sample Output 1

8

Sample Input 2

3 3 2 5

1 2 2

2 2 1

2 3 5

3 2 10

2 1 100

Sample Output 2

-1

题意：自己看。

解法：标程是二分+二维前缀和，我个人觉得双向队列写法更优。

首先每行 记录 mp[i][ j-k , j ]区间的最大值，再在得到每行每个区间最大值的条件下再次记录 每列的最大值 mp[i-k,i][j];

这中写法只要会用双向队列来维护单调队列，就很好些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 #include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back

const long long mod=998244353;
const int maxn=5e3+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n,m,k,q;
deque<int> dq;
int mp[maxn][maxn];
int mp2[maxn][maxn];  //开个mp2记录下每行一个区间的最大值

int main() {
    while(~scanf("%d%d%d%d",&n,&m,&k,&q)) {
        memset(mp,inf,sizeof(mp));
        while(q--) {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b]=min(mp[a][b],c);
        }
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(j>k&&dq.back()==mp[i][j-k]) {
                    dq.pop_back();
                }
                while(dq.size()>0&&dq.front()<mp[i][j]) {
                    dq.pop_front();
                }
                if(dq.size()==0||dq.front()>=mp[i][j]) {
                    dq.push_front(mp[i][j]);
                }
                mp2[i][j]=dq.back();
            }
            dq.clear();
        }
        for(int i=k; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(j>k&&dq.back()==mp2[j-k][i]) {
                    dq.pop_back();
                }
                while(dq.size()>0&&dq.front()<mp2[j][i]) {
                    dq.pop_front();
                }
                if(dq.size()==0||dq.front()>=mp2[j][i]) {
                    dq.push_front(mp2[j][i]);
                }
                mp[j][i]=dq.back();
            }
            dq.clear();
        }
        int res=inf;
        for(int i=k; i<=n; i++) {
            for(int j=k; j<=m; j++) {
                res=min(res,mp[i][j]);
            }
        }
        if(res>1e6+1)res=-1;
        printf("%d\n",res);
    }
    return 0;
}