文档章节

模板 权值线段树

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 607
阅读 92
收藏 0

安利一个好东西:权值线段树233333
为什么说是好东西呢。因为这是一个黑科技!
首先我们来上一个例题

题目描述 Description
给定一个序列a1,a2,…,an,如果存在i小于j并且ai大于aj,那么我们称之为逆序对,求逆序对的数目

数据范围
N<=10^5。Ai<=10^5。时间限制为1s。

输入描述 Input Description
第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。

输出描述 Output Description
所有逆序对总数.

样例输入 Sample Input
4

3

2

3

2

样例输出 Sample Output
3

这是一道归并排序的题对不对。。显然是一眼题。但是我们偏偏不用归并排序来做,哼。为什么?任性!
我们可以利用线段树来解决做这道题。什么?不懂?慢慢看!
首先我们更改线段树叶子节点处存储的内容,将其更改为权值,并且记录对于一个权值x的个数。那么我们首先构建一棵空树,对于每次插入的数字x,我们查找x+1到max区间的数字存在的个数,并将这个个数加入答案,然后插入这个数字。最后输出答案就可以了。。

#include <iostream>
#include <cstdio>

using namespace  std;

const int maxn = 100010;

struct Node{
    int l,r;
    long long tot;
} tree[maxn*3];

void build(int l,int r,int o)
{
    tree[o].l=l;
    tree[o].r=r;
    if(tree[o].l==tree[o].r) return ;
    int mid=(tree[o].l+tree[o].r)>>1;
    build(l,mid,o<<1);
    build(mid+1,r,o<<1|1);
}

void push_up(int o)
{
    tree[o].tot=tree[o<<1].tot+tree[o<<1|1].tot;
}

void update(int o,int x)
{
    if(tree[o].l==x && tree[o].l==tree[o].r)
    {
        tree[o].tot++;
        return ;
    }
    int mid=(tree[o].l+tree[o].r)>>1;
    if(x<=mid) update(o<<1,x);
    if(x>mid) update(o<<1|1,x);
    push_up(o);
}

long long getans(int o,int l,int r)
{
    if(tree[o].l>r || tree[o].r<l) return 0;
    if(tree[o].l==l && tree[o].r==r) return tree[o].tot;
    int mid=(tree[o].l+tree[o].r)>>1;
    if(r<=mid) return getans(o<<1,l,r);
    if(l>mid) return getans(o<<1|1,l,r);
    return getans(o<<1,l,mid)+getans(o<<1|1,mid+1,r);
}

int main()
{
    int n;
    scanf("%d",&n);
    build(1,maxn,1);
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        ans+=getans(1,x+1,maxn);
        update(1,x);
    }
    printf("%lld",ans);
}

练习题
提示:这个题或许需要用到离散化

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/49449375

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
P2633 Count on a tree

题目描述 给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案,初始为0,即第一个询问的u是明...

ZUTTER☮
2018/08/07
0
0
[ZJOI2013]K大数查询

Description 有 个位置, 个操作。操作有两种,每次操作如果是 的形式表示在第 个位置到第 个位置,每个位置加入一个数 ; 如果是 形式,表示询问从第 个位置到第 个位置,第 大的数是多少。...

wang3312362136
2018/01/08
0
0
BZOJ3196 二逼平衡树(线段树套线段树)

题目大意 一种数据结构,维护一个有序数列,其中需要提供以下操作: 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x,且最大...

qq_35880977
2017/12/19
0
0
12.2 省选训练总结2(2) LCT/可持久化

目录 LCT 可持久化数据结构 LCT Splay对LCT就好像线段树对链剖。LCT是动态的! Access操作,最重要的操作:把某点到根路径上的所有边设为Prefered Path,也就是挼(rua)到同一个Splay里面,而...

OwenOwl
2017/12/02
0
0
BZOJ 5461 [PKUWC2018]Minimax

版权声明:本文为博主原创文章,未经博主允许可以转载,但要注明出处 https://blog.csdn.net/wang3312362136/article/details/85319984 题目链接 https://www.lydsy.com/JudgeOnline/proble...

wang3312362136
2018/12/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

编程作业20190210900169

1编写一个程序,提示用户输入名和姓,然后以“名,姓”的格式打印出来。 #include <stdio.h>#include <stdlib.h> int main(){ char firstName[20]; char lastName[20]; print......

1李嘉焘1
28分钟前
6
0
补码的优点及原理分析

只讨论整数 1.计算机内部为什么没有减法器? 减法运算本身其实就是加法,如x - y即x +(-y),所以只需要将负数成功表示出来并可以参加加法运算,那加法器就可同时实现“+”和“-”的运算。这...

清自以敬
44分钟前
68
0
Docker 可视化管理 portainer

官网安装指南: https://portainer.readthedocs.io/en/latest/deployment.html docker-compose.yml 位置,下载地址:https://downloads.portainer.io/docker-compose.yml...

Moks角木
今天
7
0
Spring Security 实战干货:必须掌握的一些内置 Filter

1. 前言 上一文我们使用 Spring Security 实现了各种登录聚合的场面。其中我们是通过在 UsernamePasswordAuthenticationFilter 之前一个自定义的过滤器实现的。我怎么知道自定义过滤器要加在...

码农小胖哥
今天
9
0
常见分布式事务解决方案

1 微服务的发展 微服务倡导将复杂的单体应用拆分为若干个功能简单、松耦合的服务,这样可以降低开发难度、增强扩展性、便于敏捷开发。当前被越来越多的开发者推崇,很多互联网行业巨头、开源...

asdf08442a
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部