首页 > 其他分享 >权值树状数组例题——逆序对

权值树状数组例题——逆序对

时间:2024-01-28 23:12:33浏览次数:27  
标签:const int first 数组 权值 逆序 例题 define

目录

问题引入

(洛谷P1908)[https://www.luogu.com.cn/problem/P1908],简单来说就是给一个数列,求出逆序对的数量

思路一览

  1. BF做法:遍历数组中的每一个数,对于每一个数,再次遍历前面的数,时间复杂度是n2
  2. 归并排序:这个...,不太了解,以后明白了再填坑
  3. 权值树状数组:由第一个的BF可以得出结论,对于每一个数,只需要求出它的前面有多少个数大于他即可,我们将数组进行从小到大的排序,并对原下标做处理,这样就是只需要求前缀和即可,求前缀和就是基本的树状数组题目了

具体情况

按照上面的说法其实还是有点模糊,下面简单扯几句(不然这篇博客太短了emmm)。对于一个已经排好序的序列(降序),毫无疑问,在前面的就是大于在后面的,假如这个时候我们要求一个位置i上的数前面有多少个大于它的数,那么就是i-1,i-1从和而来,不就是前面的i-1个数吗,假如我们把前面i-1个数中的一个移到i的后面去,这时候就会变成i-2,也就是说前面少了1;因此,我们对原数组进行降序排列,先加入数组的一定是更大的,将其加入到原数组的原索引位置上,对其求前缀和,那么得到的就是比他大的且索引比他小的数,观察数据范围,数列中的数的大小是1e9,采用离散化的方法处理

code部分

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 1e6+7;
int n, tmp, t[N];
int lowbit(int x) {return x&-x;}
pii a[N];
bool cmp(pii a, pii b) {
    if(a.first != b.first) return a.first > b.first;
    //假如两个数数值相同,要让索引小的后排在后面,否则这两个相同的也会计算成逆序对
    return a.second > b.second;
}
void modify(int i, int x) {
    //插入过后,对于该位置++, 表示这里多了一个数
    for(; i <= n; i += lowbit(i)) t[i] += x;
}
int query(int i) {
    int res = 0;
    for(; i; i -= lowbit(i)) res += t[i];
    return res;
}

void solve() {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i].first, a[i].second = i;
    sort(a+1, a+1+n, cmp);
    ll ans = 0;
    for(int i=1; i<=n; i++) {
        ans += query(a[i].second-1);
        modify(a[i].second, 1);
    }
    cout << ans << endl;
}
int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    ios;
    int t = 1;
    //cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

补充

补充,其实没有补充,今天是摸鱼的一天,苏福(bushi)

标签:const,int,first,数组,权值,逆序,例题,define
From: https://www.cnblogs.com/notalking569/p/17990692

相关文章

  • 线性基详解+例题
    线性基线性基是一个能够在每次时间复杂度\(O(\log_2d)\),d是数字的位数内处理异或最大最小的数据结构。问题:请你维护一个数据结构,支持插入一个数,求这些数任意异或得到的结果是否可能为某一个数、最大值、最小值、第k小值。做法:开一个数组a[MAXN],MAXN是数字最高位数。a[i]表示......
  • 题解 NOIP2014 提高组-联合权值
    题解NOIP2014提高组-联合权值基本思路:以每个点为中转点,则与之相邻的点组成的点对都可产生联合权值,并且全覆盖。主要总结一下两种求权值和的思路:思路1(容斥):记与\(u\)相邻的点的集合为\(A\),则点\(u\)产生的贡献为\[ans_u=(\sum_{v\inA}w_i)^2-\sum_{v\inA}w_v\times......
  • 逆序对/归并排序
    逆序对定义:对于给定的一段正整数序列,逆序对就是序列中$a_i>a_j$且$i<j$的有序对。P1908逆序对-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=2e6+10;intn,m,a[N],c[N],res,num;void......
  • 逆序句子,但单词顺序不变
    如,输入:Ilikecoding!输出:coding!likeI#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<assert.h>#include<string.h>voidReverse_arr(char*left,char*right){ assert(left); assert(right); chartem=0; while(le......
  • 浅更道动角例题讲解练练手
    写在之前在上上上上一篇博客中,我们讲解了一道动角问题,也总结了一个公式,但是没有说做题的基本步骤以及注意事项动角问题做题步骤:最重要的当然是读题辣!读完题之后就是我们动角问题最核心的部分:画图\(P.S\)在画图时,不必苛求与原题完全一致,可以只将与题目有关的部分画出来,这......
  • 【学习笔记】权值线段树
    一.权值线段树权值线段树即一种线段树,以序列的数值为下标。节点里所统计的值为节点所对应的区间\([l,r]\)中,\([l,r]\)这个值域中所有数的出现次数。举个例子,有一个长度为\(10\)的序列\(\{1,5,2,3,4,1,3,4,4,4\}\)。那么统计每个数出现的次数。易知\(1\)出现了\(2\)......
  • 一道逆序对题
    CF1915Fhttps://codeforces.com/contest/1915/problem/F先了解什么是逆序对https://www.luogu.com.cn/problem/P1908即i<j但a[i]>a[j]的数对。求解的方法:树状数组求解。树状数组维护的其实就是一个区间内比他大并且比他先出现的值,每次查询的范围就是在原数组的下标之前......
  • 对于 EI K 逆序对排列计数的另一种自然求和方法的理解
    有一个简单的\(O(n^3)\)DP,考虑\(f_{x+1,k}=\sum_{j=0}^{x}f_{x,k-j}\),利用前缀和优化即可。考虑这实际上是\(f_{x+1}(k)=f_x(k)*\frac{1-k^{x+1}}{1-k}\),于是答案实际上为:\[[x^k]f(x)=\prod_{i=1}^n\frac{1-x^i}{1-x}\]接下来的方法来自......
  • 输入一个整数,将这个整数以字符串的形式逆序输出 程序不考虑负数的情况,若数字含有0,则逆
    描述输入一个整数,将这个整数以字符串的形式逆序输出程序不考虑负数的情况,若数字含有0,则逆序形式也含有0,如输入为100,则输出为001数据范围:0\len\le2^{30}-1\0≤n≤230−1输入描述:输入一个int整数输出描述:将这个整数以字符串的形式逆序输出点击查看代码#include<i......
  • list,迭代器例题
    //1#include<bits/stdc++.h>usingnamespacestd;intmain(){ list<int>a={1,2,3,4,5}; list<int>b={6,7,8,9,10}; a.splice(a.end(),b); list<int>::iteratori; for(i=a.begin();i!=a.end();++i){ cout<<*i<<""......