Codeforces846D(二分+树状数组)

题意：每次对矩阵进行更新，有一个时刻。然后问什么时候使得矩阵中有k * k的矩阵被更新了。

思路：二分时间，然后判断每一个时间是否复合，注意这里的时间不一定是连续的，所以需要离散化。每次判断的时候需要对进行重新操作，判断是否符合，用到了二维树状数组。

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define clr(x,y) memset(x,y,sizeof x)
#define PI acos(-1.0)
#define ITER set<int>::iterator
const int Mod = 1e9 + 7;
const int maxn = 1000 + 10;
const int N = 2;

struct Node
{
    bool operator <(const Node & t)const{return z < t.z;}
    int x,y,z;
}a[maxn * maxn];
int b[maxn * maxn];

int tree[maxn][maxn];
inline lowbit(int x){return x & (-x);}
void update(int x,int y,int val){for(int i = x; i < maxn;i += lowbit(i))for(int j = y;j < maxn; j += lowbit(j))tree[i][j] += val;}
int get(int x,int y){int ret = 0;for(int i = x; i > 0; i -= lowbit(i))for(int j = y; j > 0; j -= lowbit(j))ret += tree[i][j];return ret;}

int n,m,k,q;
bool check(int ti)
{
    int t = b[ti];clr(tree,0);
    for(int i = 1; i <= q; i ++)
    {
        if(a[i].z > t)break;
//        if(t == 8)cout << a[i].x << " -> " << a[i].y << " " << a[i].z << endl;
        update(a[i].x,a[i].y,1);
    }
    for(int i = k; i <= n;i ++)
    {
        for(int j = k; j <= m; j ++)
        {
            int temp = get(i,j) - get(i - k,j) - get(i,j - k) + get(i - k,j - k);
//            if(t == 8)cout << t << " " << i << " " << j << " " << temp << endl;
            if(temp >= k * k)return true;
        }
    }
    return false;
}
int main()
{
    while( ~ scanf("%d%d%d%d",&n,&m,&k,&q))
    {
        for(int i = 1; i <= q; i ++)
        {
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);b[i] = a[i].z;
        }
        sort(a + 1,a + q + 1);
        sort(b + 1,b + q + 1);int len = unique(b + 1,b + q + 1) - b - 1;
//        for(int i = 1; i <= len;i ++)cout << b[i] << " ";puts("");
        int l = 1,r = len;int ans = -1;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(mid))ans = mid,r = mid - 1;else l = mid + 1;

        }
        printf("%d\n",ans == -1 ? -1 : b[ans]);
    }
    return 0;
}