CF 627E

제목
R * 8727 ° C 의 행렬 을 지정 합 니 다. 처음에는 모든 위치 가 0 이 었 습 니 다.그리고 N 개의 특별한 위치 가 있 습 니 다. xi, yi, 그 가중치 는 1 입 니 다.이 행렬 에서 몇 개의 키 행렬 을 골 라 서 이 행렬 에 적어도 K 개의 1 이 있다 는 것 을 만족 시 킬 수 있 느 냐 고 물 었 다.
데이터 범위
1≤R,C,N≤3000 K≤min(N,10)
해제
먼저, 하나의 행렬 은 두 개의 이원 조 (x, x1), (y, y1) 는 x 의 범위 와 y 의 범 위 를 나 타 낼 수 있다.만약 우리 가 이미 매 거 했다 면 (x, x1) 다음 문 제 는 얼마나 합 법 적 인 (y, y1) 이 있 는 지 를 어떻게 신속하게 통계 하 느 냐 하 는 것 이다.비교적 폭력 적 인 방법 을 고려 하여 현재 (x, x1) 에 대해 이 범위 내 에 있 는 모든 1 을 추출 하고 그들 을 y 좌표 에 따라 정렬 합 니 다.모두 m 개의 1 이 있 으 면 전체 y 구간 은 우리 에 의 해 m + 1 단 으로 나 뉘 는데 당연히 어떤 구간 은 비어 있 을 수 있다.이 어 우 리 는 각 1 뒤로 K 개 에서 어느 1 까지 유지 할 수 있다. 그러면 모두 가능 한 (y, y1) 은 ∑ i (Si - Si - 1) ∗ (C - Ski + 1) 이 고, Si 는 i 번 째 1 의 좌 표를 나타 내 며, ki 는 K 개 를 뒤로 뛰 어 어디 까지 갔 는 지 를 나타 낸다.이런 방법 은 모든 (x, x1) 에 대한 복잡 도 는 O (N) 이다.다음 에 우 리 는 이 방법 을 최적화 시 켜 야 한다.우 리 는 먼저 (x, R) 에 대해 이 알고리즘 을 만 든 후에 우 리 는 ki 와 모든 1 의 전구 와 후 구 를 얻 을 수 있다.이 어 R - 1 부터 x 매 거 x1 까지 각 줄 을 매 거 할 때 이전 줄 의 1 을 삭제 하 는 것 과 같다.우리 의 ki 가 유지 하 는 것 은 K 걸음 이 어느 1 까지 갔 는 지 알 기 때문에 우 리 는 1 개 를 지 울 때마다 K 개의 위치 에 만 영향 을 줄 수 있 는 ki 입 니 다. 우 리 는 수정 하 는 김 에 ＞ i (Si - Si - 1) * 8727 ° (C - Ski + 1) 를 지 키 면 됩 니 다.드라이버 를 수정 할 때 도 이 값 을 유지 해 야 합 니 다.마지막 으로 전체적인 복잡 도 는 O (R2 + R ∗ N ∗ K) 다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 3005;
typedef long long LL;

struct Node
{
    int x,y;
}Po[MAXN];

vector<int> All[MAXN],Lk[MAXN];
int R,C,N,K;
int Pre[MAXN],Next[MAXN];

int main()
{
    //freopen("data.in","r",stdin),freopen("data.out","w",stdout);
    scanf("%d%d%d%d", &R, &C, &N, &K);
    for(int i = 1;i <= N;i ++)
    {
        scanf("%d%d", &Po[i].x, &Po[i].y);
        All[Po[i].x].push_back(i);
        Lk[Po[i].y].push_back(i);
    }
    Po[N + 1].y = C + 1;
    LL ans = 0;
    for(int i = 1;i <= R;i ++)
    {
        static int Cur[MAXN],S[MAXN];
        int tot = 0;
        for(int j = 1;j <= C;j ++)
            for(int k = 0;k < Lk[j].size();k ++)
                if (Po[Lk[j][k]].x >= i) Cur[++ tot] = Lk[j][k];
        Cur[tot + 1] = N + 1;
        LL cur = 0;
        for(int j = 1;j <= tot;j ++)
        {
            Pre[Cur[j]] = Cur[j - 1],Next[Cur[j]] = Cur[j + 1];
            if (j + K - 1 <= tot) S[Cur[j]] = Cur[j + K - 1]; else
                S[Cur[j]] = Cur[tot + 1];
            cur += (C - Po[S[Cur[j]]].y + 1) * 1ll * (Po[Cur[j]].y - Po[Cur[j - 1]].y);
        }
        ans += cur;
        for(int j = R;j >= i;j --)
        {
            for(int k = 0;k < All[j].size();k ++)
            {
                int ref = All[j][k];
                int p = Next[ref];
                if (p != N + 1) cur -= (C - Po[S[p]].y + 1) * 1ll * (Po[p].y - Po[Pre[p]].y);
                Pre[Next[ref]] = Pre[ref],Next[Pre[ref]] = Next[ref];
                if (p != N + 1) cur += (C - Po[S[p]].y + 1) * 1ll * (Po[p].y - Po[Pre[p]].y);
                if (S[ref] != N + 1)
                {
                    cur -= (C - Po[S[ref]].y + 1) * 1ll * (Po[ref].y - Po[Pre[ref]].y);
                    for(int p = Pre[ref],c = K - 1;p && c;p = Pre[p],c --)
                    {
                        cur -= (C - Po[S[p]].y + 1) * 1ll * (Po[p].y - Po[Pre[p]].y);
                        S[p] = Next[S[p]];
                        cur += (C - Po[S[p]].y + 1) * 1ll * (Po[p].y - Po[Pre[p]].y);
                    }
                } else
                {
                    tot = 0;
                    for(int p = Next[ref];p;p = Next[p]) Cur[++ tot] = p;
                    reverse(Cur + 1,Cur + tot + 1);
                    for(int p = Pre[ref],c = K - 1;p && c;p = Pre[p],c --)
                    {
                        cur -= (C - Po[S[p]].y + 1) * 1ll * (Po[p].y - Po[Pre[p]].y);
                        Cur[++ tot] = p;
                        if (tot - K + 1 > 0) S[p] = Cur[tot - K + 1]; else S[p] = N + 1;
                        cur += (C - Po[S[p]].y + 1) * 1ll * (Po[p].y - Po[Pre[p]].y);
                    }   
                }
            }
            ans += cur;
        }
    }
    printf("%I64d
", ans);
    return 0;
}