【Codeforces 627E】Orchestra | Mrsrz's blog

双指针

题目大意：

给定一个 $r\times c$ 的地图，其中有 $n$ 个格子上有棋子。给定 $k$，询问有多少子矩形包含至少 $k$ 个棋子。

题解：

枚举上边界，下边界从上往下移动。考虑计算下边界每往下移动一格，多出来的贡献。

考虑新的下边界上的一个棋子的纵坐标为 $x$，我们考虑所有包含 $x$ 的矩形，如果原来包含 $k-1$ 个棋子（现在恰好 $k$ 个），则会多出 $1$ 的贡献。

我们每加入一个棋子，把它左右各 $k$ 个棋子拿出来计算新增的矩形即可。

用 multiset 可以比较方便地维护，但效率较低，$O(r^2+rkn\log n)$。用链表可以获得非常高的效率，$O(r^2+rkn)$。

我写的是方便的 multiset 做法，实现时需要注意常数。

Code：

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<vector>
#include<set>
#include<cstring>
using namespace std;
const int N=3005;
vector<int>vec[N];
int n,m,k,p;
long long ans=0;
int xx[233],*wz=xx+50;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>p;
    for(int i=1;i<=k;++i){
        int x,y;
        cin>>x>>y;
        vec[x].push_back(y);
    }
    for(int r0=1;r0<=n;++r0){
        multiset<int>st;
        int s=0;
        for(int r=r0;r<=n;++r){
            for(int x:vec[r]){
                auto it=st.insert(x),tmp=it;
                for(int c=1;c<=p;++c)
                wz[-c]=(tmp==st.begin()?0:*--tmp);
                tmp=it;
                for(int c=0;c<=p;++c)
                wz[c]=(tmp==st.end()?m+1:*tmp++);
                for(int i=1;i<=p;++i)
                s+=(wz[i]-wz[i-1])*(wz[i-p]-wz[i-p-1]);
            }
            ans+=s;
        }
    }
    cout<<ans<<'\n';
    return 0;
}