题解 CF627E【Orchestra】

tzc_wk · 2021-03-13 00:07:17 · 题解

Codeforces 题目传送门 & 洛谷题目传送门

下设 n,m 同阶。

首先有一个傻子都会的暴力做法，枚举矩形的上、下边界 l,r，考虑集合多重集 S=\{y|x\in[l,r],(x,y)\text{为标记点}\}，也就是所有在第 l 行与第 r 行之间所有标记点的列坐标的集合，考虑进一步枚举矩形的左端点 x，那么对于右端点 y，以 (l,x) 为左上角，(r,y) 为右下角的矩形中至少有 k 个标记点当前仅当 S 中有至少 k 个元素 \in[x,y]，故考虑用 two pointers 求出这个 y，时间复杂度 n^3。

考虑优化这个过程，注意到 k 最多只有 10，因此考虑从此下手。我们将 S 中的元素从小到大排个序，记作 x_1,x_2,\cdots,x_{|S|}，记 nxt_x 为当矩形的左边界为 x 时候最小的右边界 y 使得 S 中至少有 k 个元素 \in[x,y]，那么显然 \forall v\in(x_{i-1},x_i],nxt_v=x_{i+k-1}，因此 i 会对答案产生 (x_i-x_{i-1})\times(m-x_{i+k-1}) 的贡献，我们再记 f_i=(x_i-x_{i-1})\times(m-x_{i+k-1})，那么显然矩形矩形的上、下边界分别为 l,r 时的答案就是 \sum\limits_{i=1}^{|S|}f_i。

我们考虑还是枚举矩形的上边界、下边界，并在枚举的过程中动态维护 f_i 的变化。注意到你每加入/删除一个点，最多会影响 k+1 个 f_i。因此每次加入/删除时暴力修改 f_i 都没问题。那么现在问题就来了，怎么修改 f_i 呢？一个很显然的思路是 std::multiset<int>，不过非常抱歉，std::multiset<int> 会平白多一个 \log，复杂度 n^2k\log n，再加上 set 的大常数，无法通过此题。注意到每次修改我们只用找出前驱、后继，因此考虑使用擅长 \mathcal O(1) 求出前驱、后继的双向链表，这样就可以把 set 的 \log 去掉了。还有一点，就是双向链表不支持随机访问，因此使用双向链表动态加点是实现不了了。故考虑换个思路，既然双向链表不支持动态加点，我们就考虑动态删点，首先将横坐标 \ge l 的点按照纵坐标从小到大的顺序加入双向链表，然后每扫过一行就将这一行中的标记点从双向链表中删除即可。复杂度 n^2k。

细节有亿点点多，大约也就调了 2h 罢（（（

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
    #define FILE_SIZE 1<<23
    char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
    inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
    inline void putc(char x){(*p3++=x);}
    template<typename T> void read(T &x){
        x=0;char c=getchar();T neg=0;
        while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
        while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
        if(neg) x=(~x)+1;
    }
    template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
    template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
    void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=3e3; 
int R,C,n,k,x[MAXN+5],y[MAXN+5];
vector<int> vr[MAXN+5],vc[MAXN+5];
int l[MAXN+5],r[MAXN+5];ll ans=0;
int main(){
    scanf("%d%d%d%d",&R,&C,&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y[i]);
        vr[x[i]].pb(i);vc[y[i]].pb(i);
    }
    for(int i=1;i<=MAXN;i++) sort(vr[i].begin(),vr[i].end(),[](int lhs,int rhs){return y[lhs]>y[rhs];});
    for(int i=1;i<=MAXN;i++) sort(vc[i].begin(),vc[i].end(),[](int lhs,int rhs){return x[lhs]<x[rhs];});
    for(int i=1;i<=R;i++){
        memset(l,0,sizeof(l));memset(r,0,sizeof(r));
        int pre=0;
        for(int j=1;j<=C;j++) for(int t=0;t<vc[j].size();t++)
            if(x[vc[j][t]]>=i){
                int id=vc[j][t];l[id]=pre;
                if(pre) r[pre]=id;pre=id;
            }
        ll ret=0;
        for(int j=1;j<=C;j++) for(int t=0;t<vc[j].size();t++)
            if(x[vc[j][t]]>=i){
                int id=vc[j][t],cur=id;
                for(int stp=1;stp<k;stp++) cur=r[cur];
//              printf("%d %d\n",id,cur);
                if(cur) ret+=1ll*(C-y[cur]+1)*(y[id]-y[l[id]]);
            }
//      printf("%d %d %lld\n",i,R,ret);
        ans+=ret;
        for(int j=R;j>=i;j--){
            for(int t=0;t<vr[j].size();t++){
                int id=vr[j][t];
                if(!r[id]){
                    int cur=id;
                    for(int stp=1;stp<k;stp++) cur=l[cur];
                    if(cur) ret-=1ll*(y[cur]-y[l[cur]])*(C-y[id]+1);
                    if(r[id]) l[r[id]]=l[id];
                    if(l[id]) r[l[id]]=r[id];
                    continue;
                }
                int cr=r[id],cl=r[id],stp=0;
                while(stp<k-1){if(!r[cr]) break;cr=r[cr];++stp;}
                for(int o=1;o<=k-1-stp;o++) cl=l[cl];
                if(cl) ret-=1ll*(C-y[cr]+1)*(y[cl]-y[l[cl]]);
                for(int o=1;o<=stp+1;o++){
                    cr=l[cr];cl=l[cl];
                    if(cl) ret-=1ll*(C-y[cr]+1)*(y[cl]-y[l[cl]]);
                }
                if(r[id]) l[r[id]]=l[id];
                if(l[id]) r[l[id]]=r[id];
                if(!r[id]) continue;
                cr=r[id],cl=r[id],stp=0;
                while(stp<k-1){if(!r[cr]) break;cr=r[cr];++stp;}
                for(int o=1;o<=k-1-stp;o++) cl=l[cl];
                if(cl) ret+=1ll*(C-y[cr]+1)*(y[cl]-y[l[cl]]);
                for(int o=1;o<=stp;o++){
                    cr=l[cr];cl=l[cl];
                    if(cl) ret+=1ll*(C-y[cr]+1)*(y[cl]-y[l[cl]]);
                }
            } ans+=ret;
//          printf("%d %d %lld\n",i,j-1,ret);
        }
    } printf("%lld\n",ans);
    return 0;
}
/*
10 10 10 4
7 9
8 1
5 7
6 8
6 4
5 8
4 3
1 3
5 1
6 9

4 4 3 1
1 3
2 2
3 4

5 5 5 2
1 2
1 5
3 4
4 3
5 2
*/