51Nod 1019 逆序数(线段树)
2024-08-30 21:40:30
题目链接:逆序数
模板题。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define lson i << 1, L, mid
#define rson i << 1 | 1, mid + 1, R const int N = 100010; long long ans = 0; struct node{
int x, y;
friend bool operator < (const node &a, const node &b){
return a.x < b.x;
}
} a[N]; int tree[N << 2];
int c[N];
int n; inline void pushup(int i){
tree[i] = tree[i << 1] + tree[i << 1 | 1];
} void build(int i, int L, int R){
tree[i] = 0;
if (L == R) return ;
int mid = (L + R) >> 1;
build(lson);
build(rson);
} void update(int i, int L, int R, int pos, int val){
if (L == R && L == pos){
tree[i] += val;
return;
} int mid = (L + R) >> 1;
if (pos <= mid) update(lson, pos, val);
else update(rson, pos, val); pushup(i);
} int query(int i, int L, int R, int l, int r){
if (L == l && R == r) return tree[i];
int mid = (L + R) >> 1;
if (r <= mid) return query(lson, l, r);
else if (l > mid) return query(rson, l, r);
else return query(lson, l, mid) + query(rson, mid + 1, r);
} int main(){ scanf("%d", &n); rep(i, 1, n){
scanf("%d", &a[i].x);
a[i].y = i;
} sort(a + 1, a + n + 1);
c[a[1].y] = 1; rep(i, 2, n) c[a[i].y] = a[i].x == a[i - 1].x ? c[a[i - 1].y] : c[a[i - 1].y] + 1; build(1, 1, n); ans = 0; rep(i, 1, n){
ans += (long long)query(1, 1, n, min(c[i] + 1, n), n);
update(1, 1, n, c[i], 1);
} printf("%lld\n", ans); return 0;
}
最新文章
- ajax前后端数据交互简析
- IOS开发之—— 各种加密的使用(MD5,base64,DES,AES)
- 说说oracle分页的sql语句
- Windows Azure存储容器私有,公共容器,公共Blob的区别
- URL是什么?
- utils object doesn,t exists中毒后,就删除了.JS文件后台就出现了前面的英文。请问怎么解决
- WinForm 小程序 NotePad
- 第13章 Swing程序设计----JDialog窗体
- hdu 3746 Cyclic Nacklace(kmp最小循环节)
- Elasticsearch 5.4.3实战--Java API调用:搜索
- python调用c的方法
- JS库汇总[重要]
- JavaScriptDOM操作那些事儿
- Vue 动态组件渲染问题分析
- protobuf标准消息方法
- linux RPM包安装、更新、删除等操作命令简明总结, 如何查看yum安装的软件路径 ?
- Ext 弹出窗体显示到iframe之外
- SQL学习笔记:高级教程
- 【BZOJ】3527: [Zjoi2014]力 FFT
- SDUT 3928