ABC252 D - Distinct Trio

小灰灰 2024-03-24 15:45 59阅读 0赞

**还有一天就篮球被了，好紧脏....**

**我的世界将被摧毁，也许事与愿违**

**是时候放弃一些东西了呢**

[D - Distinct Trio (atcoder.jp)][D - Distinct Trio _atcoder.jp]

![6374dd11e10645e596136e5a1a14f853.png][]

思路：

注意到值域很小，我们可以用值域的前缀和来维护全局哈希，即用前缀和来维护多少数比x小，比x大

对于一个三元组，我们去枚举中间那个元素最好，然后比它小的元素和比它大的元素的多少都通过前缀和求出来了

其实这个用权值线段树就能维护，但是没必要

![54d4dad1264b4dfcb788efd05f27cb11.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long 
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    int n;
    int a[mxn],cnt[mxn],sum[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],cnt[a[i]]++;
        for(int i=1;i<mxn;i++) sum[i]=sum[i-1]+cnt[i];
        int ans=0;
        for(int j=1;j<=n;j++) ans+=sum[a[j]-1]*(n-sum[a[j]]);
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Distinct Trio _atcoder.jp]: https://atcoder.jp/contests/abc252/tasks/abc252_d
[6374dd11e10645e596136e5a1a14f853.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a9a106f8d53d44388141e9911e30bd52.png
[54d4dad1264b4dfcb788efd05f27cb11.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7ea7617e04a94d8fa0488394116dc260.png

发表评论取消回复

表情：

评论列表（有 0 条评论，59人围观）

还没有评论，来说两句吧...

相关阅读

相关 Atcoder ABC 139D

Atcoder ABC 139D 解法： > 等差数列求和公式，记得开 $ long long $ CODE: include<iostre...

末蓝、/ 2024年04月20日 10:31/ 0 赞/ 96 阅读

相关 ABC252 D - Distinct Trio

还有一天就篮球被了，好紧脏.... 我的世界将被摧毁，也许事与愿违是时候放弃一些东西了呢 [D - Distinct Trio (atcoder.jp)][D - Di

小灰灰/ 2024年03月24日 15:45/ 0 赞/ 60 阅读

相关 ABC292 D - Unicyclic Components

ABC刷起来好爽，我要刷爆ABC！ [D - Unicyclic Components (atcoder.jp)][D - Unicyclic Components _atc

偏执的太偏执、/ 2024年03月24日 15:12/ 0 赞/ 17 阅读

相关 ABC 238 D - AND and SUM

感觉有点难啊今天做了几道D，感觉除了DP都挺难的.... ![7977e156ab8f4d26b221ecde9ae0728a.png][] 思路：异或和加有一个性

傷城~/ 2024年03月24日 01:29/ 0 赞/ 93 阅读

相关【简单DP】ABC312 D

[D - Count Bracket Sequences][] 题意：括号匹配,需要满足以下两个性质前i个字符中,左括号的数量必须大于等于右括号最后左括号的数量要

朱雀/ 2024年03月23日 18:46/ 0 赞/ 78 阅读

相关【最短路径生成树】ABC252 E - Road Reduction

[E - Road Reduction (atcoder.jp)][E - Road Reduction _atcoder.jp] 题意： ![6800b3df7f9c46

绝地灬酷狼/ 2024年03月23日 11:12/ 0 赞/ 76 阅读

相关【多维BFS】ABC311 D

[D - Grid Ice Floor][] 题意： ![21929a903e384fb5ba0355f5a95a8438.png][] 思路：可以发现，这种魔改BF

Dear 丶/ 2024年03月22日 19:58/ 0 赞/ 86 阅读

相关【多维BFS】ABC308 D

VP的时候居然花了半小时！可恶！ [D - Snuke Maze (atcoder.jp)][D - Snuke Maze _atcoder.jp] 题意： ![79

拼搏现实的明天。/ 2024年03月17日 13:55/ 0 赞/ 59 阅读

相关【树上染色】ABC146 D

[D - Coloring Edges on Tree (atcoder.jp)][D - Coloring Edges on Tree _atcoder.jp] 题意：

灰太狼/ 2024年03月16日 14:41/ 0 赞/ 57 阅读

相关 AtCoder ABC 128D equeue

题目链接：[https://atcoder.jp/contests/abc128/tasks/abc128\_d][https_atcoder.jp_contests_abc1

ゝ一世哀愁。/ 2021年11月01日 06:18/ 0 赞/ 246 阅读