CCO2021 Swap Swap Sort

题意

给定长度为 的值域为 的序列 ，每次交换两种数的大小关系，求逆序对。

思路

这题非常套路，操作是交换两种数的大小关系，所以我们只需要求出这两种数的顺序对就可以了（因为顺序对好写，逆序对用总对数减即可）。

然后非常经典的对值域分块，设 表示出现次数大于 的为大数，那么对于大数暴力求出它跟所有数的顺序对（使用前缀和，然后拿其他块查前缀和总和），时空复杂度 。

询问时两个都是小数的则双指针扫一遍，时间复杂度 。

于是有 时最优，可能需要看评测机心情。

吗？

但是我不想看评测机的心情，或者我甚至想要拿个最优解玩玩那就不能取 了。

我们先考虑怎么样比较好的卡常数首先我们发现当双指针的时候小块的大小若小于 则可以直接二分。

然后把重复的询问丢进哈希表里。

我们发现 相比于 来说实在是大得不像话，那这样有没有进一步地（至少看起来地）分摊复杂度呢？

以下假定询问非常聪明全部查小块。

然后我们分析一下：

我们设微块（一定二分）的大小为 ，数量为 ，那么有： 实际上我们会把 设得再小一些，那么 很小，可以忽略不记。

考虑左边，如果 要较大的话，则 就不可能接近 （因为接近的话则左边的 是两个根号相乘 的）。

于是至少常数除二了（可能认真分析能到一个类似于 的东西）。

那么实际怎么样呢？

实际上数据里塞了很多 的块，块长调到 以上，那么 里面的东西只有 多，于是我们不开 O2 都可以顶着 unordered_map 的巨大常数轻松通过此题！

二分有一点优化作用，但不多。

第一名老哥跑得好快啊！打不过啊！用 emhash 黑科技打过了 QwQ。

CODE

实际代码为以下代码中的 emhash.h 替换成自用的魔改版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include "emhash.h"

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
using ll=long long;
constexpr int N=100010,B=700,LB=10,FSIZE=1<<16;
int n,k,q,a[N],b[N],pre[N],num[N],big;
ll ans,to[N/B][N];
vector<int> v[N];
// unordered_map<ll,ll> old;
emhash7::HashMap<ll,ll> old;
struct FT{
    int a[N];
    void modify(int x){for(;x;x-=x&-x) ++a[x];}
    void query(int x){for(;x<=n;x+=x&-x) ans+=a[x];}
}ini;
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF,ST[20],*STC=ST;
inline char nxtc(){
    if(BuF+FSIZE==InF) fread(InF=BuF,1,FSIZE,stdin);
    return(*InF++);
}
inline void putc(char c){
    if(WuF+FSIZE==OnF) fwrite(OnF=WuF,1,FSIZE,stdout);
    *OnF++=c;
}
template<typename T>inline void read(T &x){
    char c=nxtc();
    while(c<33) c=nxtc();
    for(x=0;32<c;c=nxtc()) x=x*10+(c^48);
}
void write(ll x){
    if(!x) putc(48);
    for(;x;x/=10) *++STC=x%10^48;
    for(;STC!=ST;putc(*STC--));
    putc('\n');
}
void calc(int num,int is){
    for(int i:v[is]) to[num][is]+=pre[i];
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);read(k);read(q);
    for(int i=1;i<=n;++i){
        read(a[i]);
        ini.query(a[i]+1);
        ini.modify(a[i]);
        v[a[i]].push_back(i);
    }
    for(int i=1;i<=k;++i){
        int s=v[i].size();
        if(s>B){
         
            num[i]=++big;
            for(int j=1,k=0;j<=n;++j){
                for(;k<s&&v[i][k]<j;++k);
                pre[j]=k;
            }
            for(int j=1;j<i;++j) calc(big,j);
            for(int j=n;j>i;--j) calc(big,j);
        }
    }
    for(int i=1;i<=n;++i) b[i]=i;
    for(int p;q--;){
        read(p);
        int x=b[p],y=b[p+1],sx=v[x].size(),sy=v[y].size();
        auto add=[&](ll s){
            if(x==b[p]) ans+=s+s-(ll)sx*sy;
            else ans+=(ll)sx*sy-s-s;
        };
        if(sx<sy){
            swap(x,y);
            swap(sx,sy);
        }
        if(sx<=B){
            ll tmp=x*n+y;
            auto p=old.insert(make_pair(tmp,0));
            ll &sum=p.first->second;
            if(p.second)
                for(int i=0,j=0;j<sy;++j){
                    for(;i<sx&&v[x][i]<v[y][j];++i);
                    sum+=i;
                }
            add(sum);
        }else add(to[num[x]][y]);
        swap(b[p],b[p+1]);
        write(ans);
    }
    fwrite(WuF,1,OnF-WuF,stdout);
    return(0);
}
≡