Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Определить количество инверсий в массиве (таких пар элементов, в которых большее значение находится слева от меньшего). - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Сдвинуть элементы массива циклически на n позиций вправо. http://www.cyberforum.ru/cpp-beginners/thread86401.html
спасибо
C++ Определить количество отрицательных элементов, расположенных вы-ше главной диагонали матрицы. спасибо заранее http://www.cyberforum.ru/cpp-beginners/thread86396.html
C++ Указатель на констансное значение
Я в указателях не особо шарю Вот инициализирую *mas и заполняю его числами компилятор почему то выдает ошибку Помогите разобраться Заранее спасибо int main() { int* mas={1,6,4,9}; }...
Ввести матрицу размером NxM. C++
12. Найти в каждом столбце матрицы минимальный элемент. #include <iostream.h> #include <iomanip.h> #include <math.h> int main()
C++ Найти и поменять местами элементы, имеющие минимальное и максимальное значения в массиве http://www.cyberforum.ru/cpp-beginners/thread86384.html
#include <iostream.h> #include <math.h> int main() { int
C++ Ввести одномерный статический массив из k чисел Ввести одномерный статический массив из k чисел. Расположить элементы массива в обратном порядке. подробнее

Показать сообщение отдельно
guestonearth
3 / 3 / 2
Регистрация: 18.03.2010
Сообщений: 12
27.03.2010, 23:50
хехе)
Это веселенькая задача
за квадрат до тысячи элементов - это ясно а вот мой код для 50000 тысяч
C++
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
 
typedef long long i64;
using namespace std;
 
class FenwickTree{
 
    public:
 
        vector<int> data;
 
        FenwickTree(int n) : data(n+1 , 0)
        {
        }
 
        inline void add(int numb,int val){
 
            for(int i = numb;i<data.size(); i+=i&(-i)){
                data[i]+=val;
            }
        }
 
        inline int sum_p(int end){
            int res=0;
 
            for(int i = end;i>0;i-=i&(-i)){
                res+=data[i];
            }
 
            return res;
        }
 
        inline int sum_d(int l, int r){
            return sum_p(r)-sum_p(l-1);
        }
 
 
};
 
//int numb[200000],inv[200000];
 
int main(){
    int t;
    scanf("%d",&t);
    
    for(int co=0;co<t;co++){ // количество тестов
 
        int numb_t,cur;
        i64 res=0;
        scanf("%d",&numb_t);// количество элементов в перестановке
        vector<int> numbs(numb_t);
 
        for (int i=0;i<numb_t;i++){
            scanf("%d",&numbs[i]);
        }
 
        vector<int> numb_s=numbs;
 
        sort(numb_s.begin(),numb_s.end());
 
        map<int,int> rev;
 
        for (int i=0;i<numb_t;i++)  rev[numb_s[i]] = i+1;
        
        for (int i=0;i<numb_t;i++) numbs[i] = rev[numbs[i]];
 
        FenwickTree x(numb_t);
 
        for (int i=0;i<numb_t;i++){
            
            int cur = numb_t + 1 - numbs[i];
            res+=x.sum_p(cur - 1);
            x.add(cur,1);
        }
 
        printf("%lld\n", res);
 
    }
 
    return 0;
}
класс реализующий дерево фенвика + масштабирование

Enjoy.....
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru