`
Simone_chou
  • 浏览: 192724 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

Enemy is weak(树状数组 + 离散化)

    博客分类:
  • CF
 
阅读更多
E. Enemy is weak
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Romans have attacked again. This time they are much more than the Persians but Shapur is ready to defeat them. He says: "A lion is never afraid of a hundred sheep".

Nevertheless Shapur has to find weaknesses in the Roman army to defeat them. So he gives the army a weakness number.

In Shapur's opinion the weakness of an army is equal to the number of triplets i, j, k such that i < j < k and ai > aj > ak where ax is the power of man standing at position x. The Roman army has one special trait — powers of all the people in it are distinct.

Help Shapur find out how weak the Romans are.

Input

The first line of input contains a single number n (3 ≤ n ≤ 106) — the number of men in Roman army. Next line contains n different positive integers ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 109) — powers of men in the Roman army.

Output

A single integer number, the weakness of the Roman army.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Sample test(s)
input
3
3 2 1
output
1
input
3
2 3 1
output
0
input
4
10 8 3 1
output
4
input
4
1 5 4 3
output
1

 

       题意:

       给出 N (3 ~ 10 ^ 6)代表有 N 个数(1 ~ 10 ^ 9),求出能组成 i < j < k 且 num [ i ] > num [ j ] > num [ k ] 的序列一共有多少种。

 

       思路:

       树状数组 + 离散化。数最大是 10 ^ 9,而一共只可能出现 10 ^ 6 个数,故可以离散化,给每个数一个对应的编号大小。对于数列中的每一个数,都可能是中间值,如果是中间值的话,则寻找左边大于这个中间值的个数 big [ i ]  和 右边小于这个中间值的个数 small [ i ],最后将所有的 big * small 相加即为答案。维护 small 和 big 的时候,用树状数组维护即可。

 

        AC:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MAX = 1000005;

map<int, int> m;
int num[MAX], New[MAX];
int small[MAX], big[MAX];
int bit[MAX];
int nn;

int sum(int i) {
        int s = 0;

        while (i > 0) {
                s += bit[i];
                i -= i & -i;
        }

        return s;
}

void add(int i, int x) {
        while (i <= nn) {
                bit[i] += x;
                i += i & -i;
        }
}

int main() {
        int n;
        scanf("%d", &n);

        for (int i = 1; i <= n; ++i) {
                scanf("%d", &num[i]);
                New[i] = num[i];

        }

        nn = 0;
        sort(New + 1, New + 1 + n);
        for (int i = 1; i <= n; ++i) {
                if (!m[New[i]]) m[New[i]] = ++nn;
        }

        memset(bit, 0, sizeof(bit));
        for (int i = 1; i <= n; ++i) {
                big[i] = sum(nn) - sum(m[ num[i] ]);
                add(m[ num[i] ], 1);
        }

        memset(bit, 0, sizeof(bit));
        for (int i = n; i >= 1; --i) {
                small[i] = sum(m[ num[i] ] - 1);
                add(m[ num[i] ], 1);
        }

        ll res = 0;
        for (int i = 1; i <= n; ++i) {
                res += (ll)small[i] * (ll)big[i];
        }

        printf("%I64d\n", res);

        return 0;
}

 

 

分享到:
评论

相关推荐

    Ego Is the Enemy - Ryan Holiday

    Ego Is the Enemy is the fourth book by author Ryan Holiday,

    数据结构例题选讲PPT学习教案.pptx

    例如,在“Enemy is weak”问题中,树状数组被用来统计满足特定条件的三元组数量,通过前向和后向扫描数组,利用树状数组更新和查询来降低时间复杂度至nlog(n)。 最后,字典树,又称Trie,是处理字符串查询的一种...

    Enemy.java

    本页代码是敌机类的代码,写了敌机属性下标值,不同类型敌机的初始位置,敌机飞行路径设定数组,初始化敌机,绘制敌机,移动方法等多种方法

    Enemy(1).cs

    Enemy(1).cs

    unity角色头顶血条系统Enemy + NPC Healt.zip

    "unity角色头顶血条系统Enemy + NPC Health"是一个专门针对Unity开发的解决方案,它简化了这一过程,使得开发者可以快速地在游戏项目中实现这一功能。 首先,"unity角色头顶血条系统Enemy + NPC Health Bars 1.04-...

    unity敌人血条系统源码X-Bars Enemy Heal.zip

    "X-Bars Enemy Heal" 是一个专为Unity设计的敌人血条系统源码,它旨在简化游戏开发过程中血条显示的实现。 这个源码的特点在于其便捷性和美观性。开发者只需将源码导入到Unity项目中,就可以直接使用,无需复杂的...

    Know your enemy

    诸葛建伟 Know your enemy 第三代蜜网关键技术的部署与实现 基于Vmware的第三代Honeynet部署以及攻击实例

    街头霸王html5游戏

    this.master.enemy.left + this.effect_position[ 0 ] : this.master.enemy.left + this.master.enemy.width + this.effect_position[ 0 ] , this.master.enemy.top + this.effect_position[ 1 ] ); var attack...

    Enemy.cs

    Enemy.cs

    1984 AI Enemy Line of Sight v0.1.unitypackage

    EnemyLineOfSightChecker.cs attached to each Enemy (worst performance, most likely this is what you’d start with) EnemyLineOfSightManager.

    Public-Enemy

    "Public-Enemy" 是一款字体相关的资源,可能指的是一个特定的字体库或设计风格。在IT行业中,字体扮演着至关重要的角色,它不仅影响着文本的可读性,还对用户界面(UI)的设计和品牌视觉识别有显著影响。下面我们将...

    An Enemy Called Average_Called_ebook_

    Book enemy called average

    Enemy of the State

    ### Enemy of the State:为什么应减少使用状态及如何实现 #### 核心概念与理论背景 在编程领域,“状态”通常指的是程序运行过程中所持有的数据值。这些值随着时间的变化而变化,例如变量的值更新、对象的状态...

    enemy-aim-ai-unity

    7. **行为树(Behavior Trees)**:为了使敌人的行为更复杂且多样化,可以使用行为树工具。行为树允许定义一系列条件和动作,让敌人根据当前状态选择最佳行为。 8. **AI控制器**:一个统一的AI控制器类可以管理所有...

    Space Arcade - Enemy Ships.rar

    "Space Arcade - Enemy Ships.rar"是一个与Unity相关的项目,很可能是一个太空射击游戏的资源包,包含了敌机设计和相关的编程元素。在这个项目中,我们可以深入探讨Unity在开发网络多人游戏时所涉及的关键技术。 ...

    20663_Enemy Spawner_1.13_payday_

    "20663_Enemy Spawner_1.13_payday_" 提供了一个独特的 Lua 敌人生成器模式,为游戏增添了更多变数和挑战性。Lua 是一种轻量级的脚本语言,它在游戏开发中被广泛用于创建自定义逻辑和动态内容,Payday 2 的社区...

Global site tag (gtag.js) - Google Analytics