当前位置：首页 > 范文大全 > 实用文>POJ 3067 Japan（树状数组/求逆序数）

POJ 3067 Japan（树状数组/求逆序数）

2023-03-17 08:29:18 收藏本文下载本文

“今天也不早睡”通过精心收集，向本站投稿了2篇POJ 3067 Japan（树状数组/求逆序数），以下是小编收集整理后的POJ 3067 Japan（树状数组/求逆序数），仅供参考，欢迎大家阅读。

篇1：NYOJ117&& 树状数组求逆序数

树状数组可以用来求逆序数，当然一般用归并求，如果数据不是很大，可以一个个插入到树状数组中，每插入一个数，统计比他小的数的个数，对应的逆序为 i- getsum( da

ta[i] ),其中 i 为当前已经插入的数的个数， getsum( da

ta[i] ）为比 da

ta[i] 小的数的个数i- sum( da

ta[i] ) 即比 da

ta[i] 大的个数，即逆序的个数但如果数据比较大，就必须采用离散化方法。一关键字的离散化方法：所谓离散化也就是建立一个一对一的映射。因为求逆序时只须要求数据的相应

大小关系不变。如： 10 30 20 40 50 与 1 3 2 4 5 的逆序数是相同的定义一个结构体 struct Node{ int data; // 对应数据 int pos; // 数据的输入顺序 };

先对 da

ta 升序排序，排序后，pos 值对应于排序前 da

ta 在数组中的位置。再定义一个数组 p[N]，这个数组为原数组的映射。以下语句将按大小关系把原数组与 1到 N 建立一一映射。

题目链接：click here

预备函数

定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.

例如,Lowbit(34)的返回值将是2；而Lowbit(12)返回4；Lowbit(8)返回8。

将34转为二进制,为0010 0010,这里的“最后一个1”指的是从2^0位往前数,见到的第一个1,也就是2^1位上的1.

程序上，((Not I)+1) And I表明了最后一位1的值,

仍然以34为例,Not 0010 0010的结果是 1101 1101(221),加一后为 1101 1110(222), 把 0010 0010与1101 1110作AND,得0000 0010(2).

Lowbit的一个简便求法:（C++）

int lowbit(int x){ return x&(-x);}

新建

定义一个数组 BIT，用以维护A的前缀和，则:

具体能用以下方式实现：（C++）

void build{ for (int i=1;i<=MAX_N;i++) { BIT[i]=A[i]; for (int j=i-1; j>i-lowbit(i);j-=lowbit(j))BIT[i]+=BIT[j]; }}

修改

假设现在要将A[I]的值增加delta,

那么,需要将BTI[I]覆盖的区间包含A[I]的值都加上K.

这个过程可以写成递归,或者普通的循环.

需要计算的次数与数据规模N的二进制位数有关,即这部分的时间复杂度是O(LogN)

修改函数的C++写法

void edit(int i, int delta){ for (int j = i; j<= MAX_N; j += lowbit(j)) BIT[j] += delta;}

求和

首先,将ans初始化为0，将i计为k.将ans的值加上BIT[P]将i的值减去lowbit(i)重复步骤2～3，直到i的值变为0

求和函数的C/C++写法

int sum (int k){ int ans = 0; for (int i = k; i >0; i -= lowbit(i)) ans += BIT[i]; return ans;}

复杂度

初始化复杂度最优为O(N)

单次询问复杂度O(LOG(N))其中N为数组大小

单次修改复杂度O(LONG(N))其中N为数组大小

空间复杂度O(N);

代码：

#include#include#include#include#include#include using namespace std;const int maxn=1000001;const double eps=1e-6;const double pi=acos(-1.0);#define lowbit(x) ((x)&(-x))struct node{ int data,pos;} doo[maxn];int n;int coo[maxn],poo[maxn];int cmp(const void *a,const void *b){ node *ta=(node *)a; node *tb=(node*)b; return ta->data-tb->data;}int cmp1(node aa,node bb){ return aa.data-bb.data;}void updata(int pos,int value){ int x=pos; while(x<=n) { coo[x]+=value; x+=lowbit(x); }}int getsum(int pos){ int x=pos,sum=0; while(x) { sum+=coo[x]; x-=lowbit(x); }}int main(){ int T; scanf(“%d”,&T); while(T--) { scanf(“%d”,&n); for(int i=1; i<=n; i++) {scanf(“%d”,&doo[i].data);doo[i].pos=i; } qsort(doo+1,n,sizeof(doo[0]),cmp); // sort(doo,doo+n,cmp1); int id=1; poo[doo[1].pos]=1; for(int i=2; i<=n; i++)if(doo[i].data==doo[i-1].data) poo[doo[i].pos]=id;else poo[doo[i].pos]=++id; memset(coo,0,sizeof(coo)); long long ans=0; for(int i=1; i<=n; i++) {updata(poo[i],1);ans+=(long long )(i-getsum(poo[i])); } printf(“%lld\n”,ans);// int n,s=0;;//暴力// int a[100];// scanf(“%d”,&n);// for(int i=0; i

归并排序合并算法

#include#include#define“ i=”i,“ if=”if“ ilt=”i<“ iltn=”i

篇2：POJ 3067 Japan（树状数组/求逆序数）

JapanTime Limit:1000MSMemory Limit:65536KTotal Submissions:22258Accepted:5995

Description

Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on the East coast and M cities on the West coast (M <= 1000, N <= 1000). K superhighways will be build. Cities on each coast are numbered 1, 2, ... from North to South. Each superhighway is straight line and connects city on the East coast with city of the West coast. The funding for the construction is guaranteed by ACM. A major portion of the sum is determined by the number of crossings between superhighways. At most two superhighways cross at one location. Write a program that calculates the number of the crossings between superhighways.

Input

The input file starts with T - the number of test cases. Each test case starts with three numbers – N, M, K. Each of the next K lines contains two numbers – the numbers of cities connected by the superhighway. The first one is the number of the city on the East coast and second one is the number of the city of the West coast.

Output

For each test case write one line on the standard output:

Test case (case number): (number of crossings)

Sample Input

13 4 41 42 33 23 1

Sample Output

Test case 1: 5

Source

Southeastern Europe 2006

#include#include#include#include#includeusing namespace std;int n,m,k;__int64 c[1000100];struct node{ int x; int y;} q[1000500];bool cmp(node a,node b){ if(a.x==b.x) { return a.y<=b.y; } else { return a.x0) { sum += c[i]; i = i - lowbit(i); } return sum;}int main(){ int T; int p = 0; scanf(”%d“,&T); while(T--) { scanf(”%d%d%d“,&n,&m,&k); memset(c,0,sizeof(c)); for(int i=0; i

【POJ 3067 Japan（树状数组/求逆序数）】相关文章：

10.求范文