摘要：
4201楼兰图腾0x40「数据结构进阶」例题描述在完成了分配任务之后，西部314来到了楼兰古城的西部。相传很久以前这片土地上生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。
4201 楼兰图腾 0x40「数据结构进阶」例题
描述
在完成了分配任务之后，西部314来到了楼兰古城的西部。相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。
西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。西部314认为这幅壁画所包含的信息与这N个点的相对位置有关，因此不妨设坐标分别为(1,y1),(2,y2),…,(n,yn),其中y1~yn是1到n的一个排列。
西部314打算研究这幅壁画中包含着多少个图腾，其中V图腾的定义如下（注意：图腾的形式只和这三个纵坐标的相对大小排列顺序有关）1<=i<j<k<=n且yi>yj,yj<yk;
而崇拜∧的部落的图腾被定义为1<=i<j<k<=n且yi<yj,yj>yk;
西部314想知道，这n个点中两个部落图腾的数目。因此，你需要编写一个程序来求出V的个数和∧的个数。
输入格式
第一行一个数n
第二行是n个数，分别代表y1，y2……yn
输出格式
两个数
中间用空格隔开
依次为V的个数和∧的个数
样例输入
5 1 5 3 2 4
样例输出
3 4
数据范围与约定
- 10%的数据 n<=600
40%的数据 n<=5000
100%的数据 n<=200000，答案不超过int64
线段树逆序对做法；
首先不线段树初始化成0；
然后每读入一个数字就求一次【x,n】的和，即为所有下表小于x的数且值大于x的和，也即逆序对个数
#include<cstdio>#include<algorithm>#include<cstring> using namespacestd; const int maxn=200000+10; int sum[maxn<<2]; void get(intx){ sum[x]=sum[x<<1]+sum[x<<1|1]; } void update(int l,int r,int rt,intc){ if(l==r){ sum[rt]++; return; } int mid=(l+r)>>1; if(c<=mid) update(l,mid,rt<<1,c); else update(mid+1,r,rt<<1|1,c); get(rt); } long long ask(int l,int r,int rt,int L,intR){ if(l>=L&&r<=R) returnsum[rt]; long long ans=0; int mid=(l+r)>>1; if(L<=mid) ans+=ask(l,mid,rt<<1,L,R); if(R>mid) ans+=ask(mid+1,r,rt<<1|1,L,R); returnans; } intmain(){ intn,x; scanf("%d",&n); long long ans1=0,ans2=0; for (int i=1;i<=n;i++){ scanf("%d",&x); long long temp1=ask(1,n,1,1,x);//求比x小的数 long long temp2=ask(1,n,1,x,n);//求比x大的数 ans1+=temp2*(n-x-temp2); ans2+=temp1*(x-1-temp1); update(1,n,1,x); } printf("%lld %lld ",ans1,ans2); return 0; }