题面
给出 \(n\) 个数 \(a_i\),求出 \(a_i+a_j\geq s\) 的 \(i,j\) 总数。
赛时想法
从前往后考虑所有在 \(i\) 之前的,大于 \(s-i\) 的数,\(i\) 可以与这些数配对。自然而然就想到用pbds里的平衡树维护。
预估复杂度 \(\mathcal{O}(n \log n)\),\(n\leq2\times10^5\) 完全没有问题。
7min就敲完了。
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
int n,s,x,ans,v;
using T=tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>;
T tr;
int main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> s;while(n--){cin >> x;T t1;tr.split({s-x,998244353},t1);ans+=t1.size();tr.join(t1);tr.insert({x,++v});}cout << ans;
}
结果:炸了,30pts。
赛后回顾
仔细研究了一下自己原来的代码,想起来split好像不是 \(\mathcal{O}(\log n)\) 的,改成了order_of_key。改后测得70pts。
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
int n,s,x,ans,v;
using T=tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>;
T tr;
int main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> s;while(n--){cin >> x;ans+=tr.size()-tr.order_of_key({s-x,998244353});tr.insert({x,++v});}cout << ans;
}
检查了一下,发现方案数可能达到 \(n^2\) 级别,需要开long long。测得100pts。
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define int long long
int n,s,x,ans,v;
using T=tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>;
T tr;
int32_t main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> s;while(n--){cin >> x;ans+=tr.size()-tr.order_of_key({s-x,998244353});tr.insert({x,++v});}cout << ans;
}
反思
- tree的split操作复杂度不对,容易变 \(\mathcal{O}(n^2)\)。
- 再也不删
#define int long long
了,删了不知道下次哪道题就炸了。