题解 CF627E【Orchestra】

· · 题解

吐槽：为什么所有题解都说双向链表不能动态加点啊，明明可以的

首先做个容斥，求多少个连续子矩阵包含少于 K 个点。

枚举上边界和下边界（对行而言）。用链表维护每个有黑点的列。

在加入一个新行时，找到每个这个行中黑点应该在链表中插入的位置，然后把它们插入链表。具体地，可以 O(nr+n^2) 预处理出 lst(p,i) 表示第 p 个黑点 (x_p,y_p) 所在行 x_p 与行 i（i\le x_p）之间的所有满足 y'\le y_p 的黑点中，y' 最大的那一个；那么在链表中 p 就应该插入到这个黑点后面。假如 y'=y_p 就不需要新插入元素，把这个元素的权值加一即可。

总贡献只与 next 有关（next_i 表示满足链表中第 i 个点到第 next_i 个点的权值和小于 K 的最大 next），为了动态维护总贡献，只需要动态维护 next。每次插入至多会引起 O(K) 个点的贡献改变，双指针可以做到 O(K) 修改 next 并重新计算答案。

总复杂度 O(nrK+n^2)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,K,q,is[3005][3005],X[3005],Y[3005],lst[3005][3005],l[3005],r[3005],nxt[3005],w[3005],cur[3005];
ll ans=0,sum=0;
vector<int> t[3005];
int S(int l,int r){
    return (l+r)*(r-l+1)/2;
}
int Calc(int i){
    if(nxt[i]<i)return (i-l[i]-1)*(i-l[i])/2;
    return S(r[nxt[i]]-i,r[nxt[i]]-(l[i]+1));
}
void Insert(int x,int p){
    int q=r[p];
    if(q==x)w[q]++;
    else r[p]=x,l[x]=p,r[x]=q,l[q]=x,w[x]=1;
    int i=r[x],cnt=0,j=l[i],s=0;
    ans-=cur[i];
    while(s+w[r[j]]<K)j=r[j],s+=w[j];
    nxt[i]=j,ans+=(cur[i]=Calc(i));
    for(i=l[i],cnt++;i&&cnt<=K;i=l[i],cnt++){
        ans-=cur[i],s+=w[i];
        while(s>=K)s-=w[j],j=l[j];//双指针
        nxt[i]=j,ans+=(cur[i]=Calc(i));
    }
}
int main(){
    cin>>n>>m>>q>>K;
    for(int i=1,x,y;i<=q;i++)cin>>x>>y,is[x][y]=i,t[x].push_back(y),X[i]=x,Y[i]=y;
    for(int i=1;i<=n;i++)sort(t[i].begin(),t[i].end());
    for(int i=1;i<=q;i++){
        int l=0;
        for(int j=X[i];j>=1;j--){
            for(int k:t[j])if(k<Y[i])l=max(l,k);
            lst[i][j]=l;
        }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sum+=i*j;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m+1;j++)w[j]=l[j]=r[j]=nxt[j]=cur[j]=0;
        r[0]=r[m+1]=m+1,l[0]=l[m+1]=0,nxt[0]=nxt[m+1]=m+1,w[0]=0,w[m+1]=1e9,cur[m+1]=ans=m*(m+1)/2;
        for(int j=i;j<=n;j++){
            for(int k:t[j])Insert(k,lst[is[j][k]][i]);
            sum-=ans;
        }
    }
    cout<<sum;
}