Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 索引树

Posted by xcwd1598 at 2021-06-20 14:15:54 on Problem 1990

1.按照耳背值升序排列。
2.两个索引树；第一个用来存放比之前耳背值大的牛的数量；第二个存放比比之前耳背值大的牛的位置和；其实是为了凑公式 val*(nx-sum(leftx)+sum(rightx)-nx);解释：简单推算，比当前牛耳背值小的坐标左边有几头牛，并且坐标和是多少?比当前牛耳背值小的坐标右边有几头牛，并且坐标和是多少?
package IndexTree;

import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Poj1990Wxc {

static StringTokenizer st;
static int  N;
static Cow[] cowArray;
static long[] tree;
static long[] sumTree;
static long A;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub

N=Integer.parseInt(st.nextToken());

cowArray=new Cow[N];

int maxX=0;

for(int i=0;i<N;i++)
{

int  tempValue =Integer.parseInt(st.nextToken());

int tempIndex=Integer.parseInt(st.nextToken());

maxX=Math.max(maxX, tempIndex);

Cow tmpCow=new Cow(tempIndex,tempValue);

cowArray[i]=tmpCow;

}

Arrays.sort(cowArray, new Comparator<Cow>() {

@Override
public int compare(Cow o1, Cow o2) {
// TODO Auto-generated method stub
return o1.val-o2.val;
}
});

int L=1;

while(L<maxX)
{
L=L+L;
}

tree=new long[2*L];

sumTree=new long[2*L];

for(int i=0;i<cowArray.length;i++)
{
long leftCnt=queryCnt(L,cowArray[i].index+L);

long rightCnt=queryCnt(cowArray[i].index+L,2*L-1);

long leftSum=querySum(L,cowArray[i].index+L);

long rightSum=querySum(cowArray[i].index+L,2*L-1);

A=A+cowArray[i].val*(leftCnt*cowArray[i].index-leftSum+rightSum-rightCnt*cowArray[i].index);

update(cowArray[i].index+L,1);

}
System.out.println(A);
}
static long queryCnt(int start,int end)
{
long rnt=0;

while(start<=end)
{

if(start%2==1)
{
rnt=rnt+tree[start];
}

if(end%2==0)
{
rnt=rnt+tree[end];
}

start=(start+1)>>1;

end=(end-1)>>1;

}

return rnt;
}

static long querySum(int start,int end)
{
long rnt=0;

while(start<=end)
{

if(start%2==1)
{
rnt=rnt+sumTree[start];
}

if(end%2==0)
{
rnt=rnt+sumTree[end];
}

start=(start+1)>>1;

end=(end-1)>>1;

}

return rnt;
}

static void update(int index,long val)
{
while(index>0)
{
tree[index]=tree[index]+1;

index=index>>1;
}
}

{
while(index>0)
{
sumTree[index]=sumTree[index]+val;

index=index>>1;
}
}

static class Cow{
int index;

int val;

public Cow(int index, int val) {
super();
this.index = index;
this.val = val;
}

}

}

Followed by: