题解：P11615 【模板】哈希表

· · 题解

P11615 【模板】哈希表

暴力思路

第一眼看到题面，立刻使用了 STL 中的 map 按题意进行映射。代码实现非常简单。时间复杂度约为 O(N\log N)，有较大常数。

#include<iostream>
#include<unordered_map>
#define ll unsigned long long
using namespace std;
unordered_map<ll,ll>m;
int n;
ll x,y,ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%llu%llu",&x,&y);
        ans+=i*m[x];
        m[x]=y;
    }
    printf("%llu\n",ans);
    return 0;
}

结果也一样简洁明了：鲜艳的 TLE。

优化

可以使用另一种映射 unordered_map，可以减小常数。

但是结果一样，仍然超时。

正解：在线哈希表

哈希表，就是对于上述思路的优化。题目中给定的 x 在 [0,2^{64}) 内，范围非常大。哈希就像离散化，将 [0,2^{64}) 范围的数通过哈希函数 H(x)=x \bmod P 映射到一个较小的范围内，比如 10^6。其中 P 是一个相对较小的质数，我们取 10^6+3。

所以我们需要开 10^6+10 个 unorderedmap，对于每次询问，直接输出 $m{x\bmod P,x}$ 的值，然后对其进行更改。可这样以大幅度节省时间。如果只是使用映射，会被出题人卡掉一个点。各位可以去看出题人题解中的详细 hack 方法。

这样的时间复杂度是 O(N\log N)，但是常数较小，有时可以达到 O(1) 复杂度。

注意 P 不要开太大，容易 MLE。

#include<iostream>
#include<unordered_map>
#define ll unsigned long long
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,1<<20,stdin),ss==tt)?EOF:*ss++)
using namespace std;
char In[1<<20],*ss=In,*tt=In;
const int N=1e6+10;
const int P=1e6+3;
ll read(void){ll f=1,res=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){res=res*10+(ch-'0');ch=getchar();}return res*f;}
void write(ll x){if(x<0){putchar('-');x=-x;}if(x>=10) write(x/10);putchar((x%10)+'0');return;}
unordered_map<ll,ll>m[N];
ll a,b,r,ans;
int n;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a=read(),b=read();
        r=a%P;
        ans+=i*m[r][a];
        m[r][a]=b;
    }
    write(ans),putchar('\n');
    return 0;
}

离线做法

非常简单且跑得飞快。

先读入所有询问，然后以 x 为第一关键字，以读入顺序为第二关键字排序。依次处理后再以读入顺序排序，就可以直接得到答案。该做法的瓶颈在于 sort 排序，所以时间复杂度是 O(N\log N)。但是 sort 比较优秀，常数远远小于映射，可以跑到一秒以内。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#define pb push_back
#define ll unsigned long long
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,1<<20,stdin),ss==tt)?EOF:*ss++)
using namespace std;
char In[1<<20],*ss=In,*tt=In;
const int N=5e6+10;
struct Node1{
    ll x;
    ll y;
    int id;
    friend bool operator <(const Node1 a,const Node1 b){
        if(a.x!=b.x) return a.x<b.x;
        return a.id<b.id;
    }
}a[N];
struct Node2{
    ll ans;
    int id;
    friend bool operator <(const Node2 a,const Node2 b){
        return a.id<b.id;
    }
}b[N];
int n;
ll res;
ll read(void){ll f=1,res=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){res=res*10+(ch-'0');ch=getchar();}return res*f;}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i].x=read();
        a[i].y=read();
        a[i].id=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;){
        int l=i,r=i;
        while(i<=n&&a[r].x==a[l].x) r=++i;
        r--;
        for(int j=l;j<=r;j++) b[j]={(j-1<l?0ll:a[j-1].y),a[j].id};
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        res+=i*b[i].ans;
    }
    printf("%llu\n",res);
    return 0;
}