baritone 上低音号（链表 卡矩阵）

baritone

上低音号
【题目描述】
黄前久美子是一名上低音号手。这天，一共有n名上低音号手参加演出。演出的场地是一个r行c列的矩阵，每名上低音号手都在其中一个方格内，且没有两个人在同一个方格。
摄影师为这次演出拍摄了许许多多的照片，每张照片都是一个边框平行于坐标轴的矩形。久美子希望照片中能出现尽量多的上低音号手——具体地，如果一张照片出现了超过k名上低音号手，那么久美子会很喜欢这张照片。
那么，究竟能拍出多少张不同的久美子喜爱的照片呢？
【输入格式】
第一行四个整数r,c,n,k。
接下来n行，每行两个数x,y，表示一名在第x行第y列的上低音号手。保证数对(x,y)不重复出现。
【输出格式】
输出一行一个整数，表示可以拍出的久美子喜爱的照片数量。
【样例数据】
baritone1.in
2 2 1 1
1 2
baritone1.out
4
baritone2.in
3 2 3 3
1 1
3 1
2 2
baritone2.out
1
baritone3.in
3 2 3 2
1 1
3 1
2 2
baritone3.out
4
baritone4.in
1 1 1 1
1 1
baritone4.out
1
【数据范围】
对于30%的数据，n,r,c≤500。
对于另30%的数据，k≤3。
对于100%的数据，1≤n,r,c≤3000，1≤k≤10。

思路：
从上往下枚举上边界，从下往上枚举下边界。
考虑已经统计出上下边界为枚举的包含至少k 个点的矩形数，当下边界往上移动时，可能会删除某些点。
用按横坐标排序的有序表维护当前上下边界间的点，只有删除点的前k 个点和后k个点会影响答案，其它矩形区域依然可行。
这样每次只需要从有序表中删除一个点并统计答案，使用链表即可。
复杂度O( n^2*k )。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <queue>
#include <cmath>
using namespace std;

const int N = 4000;
int r, c, n, k, idc;
int nxt[N], pre[N], val[N], id[N];
int pointx[N], finded[N], pointy[N];
long long ans, sum;
vector <int> ve[N];

struct AA{
    int x, y;
}aa[N];

bool cmp(int x, int y) {
    if (pointx[x] != pointx[y]) return pointx[x] < pointx[y];
    else return pointy[x] < pointy[y];
}

void del(int t) {
    nxt[pre[t]] = nxt[t];
    pre[nxt[t]] = pre[t];//从链表中删除 
    sum -= val[t];//已t.x为左边界的矩形要减去 
    int x = nxt[t], y = nxt[t];
    for (int i=1; i<k; i++) y = nxt[y];//找到恰好在t之后的k个点 
    for (int i=1; i<=k; i++) {//一直到刚好包含t的k个点（都会被影响） 
        int v = (pointx[x] - pointx[pre[x]]) * (r - pointx[y] + 1);
        sum += v - val[x];
        val[x] = v;
        x = pre[x]; y = pre[y];
    }
}

int main() {
    //freopen("baritone.in", "r", stdin);
    //freopen("baritone.out", "w", stdout);
    scanf("%d%d%d%d", &r, &c, &n, &k);
    ans = 0;
    for (int i=1; i<=n; i++)
        scanf("%d%d", &aa[i].x, &aa[i].y), ve[aa[i].y].push_back(i);//保存每一列有那些点 
    for (int i=1; i<=c; i++) {//矩形上边界为i 
        sum = 0; idc = 0;
        for (int j=0; j<=10; j++)
            pointx[++idc] = 0, pointx[++idc] = r + 1;//防止跳k-1步越界 
        for (int j=1; j<=n; j++)//可能在当前矩阵里的点 
            if (aa[j].y >= i) {
                pointx[++idc] = aa[j].x;
                pointy[idc] = aa[j].y;
                finded[j] = idc;
            }
        for (int j=1; j<=idc; j++) id[j] = j;
        sort(id+1, id+idc+1, cmp);//x为第一关键字，y为第二关键字排序 
        for (int j=1; j<idc; j++)//
            nxt[id[j]] = id[j+1], pre[id[j+1]] = id[j];
        nxt[id[idc]] = id[idc];
        pre[id[1]] = id[1];//建立链表维护前驱后继 
        for (int j=1; j<=idc; j++) {
            int now = j;//枚举矩形左边界j.x 
            for (int p=1; p<k; p++) now = nxt[now];//now为矩形右边界 
            val[j] = (pointx[j] - pointx[pre[j]]) * (r - pointx[now] + 1);//左边界在j与pre[j]之间，右边界在now与r之间都满足条件 
            sum += val[j];//val[j]表示在当前上下界是，左边界在j.x且满足条件的矩形有多少个 
        }
        for (int j=c; j>=i; j--) {//枚举下边界 
            ans += sum;
            for (int p=0; p<(int)ve[j].size(); p++)//原来下边界上的所有点都要被delete 
                del(finded[ve[j][p]]);//finded[i]是第i个点在链表中的序号 
        }
    }
    cout << ans << endl;
    return 0;
}