首页 > 代码库 > 火柴排队（NOIP2013）（附树状数组专题讲解（其实只是粗略。。。））
火柴排队（NOIP2013）（附树状数组专题讲解（其实只是粗略。。。））
原题传送门。。（9018上不去。明天再来搞。）
首先，这道题目是一道神奇的题。
看到这道题，第一眼就觉得2个数组排个序，然后一一对应的时候一定差值最小。
由于我们可以将这2个数列同时进行调换。
所以我们先把2个数列排个序。
第二个序列中的数组的下标都指向第一个数组中的数的原来位置（其实就是离散化（真是啰嗦。。））
离散化之后，我们就变成了一个混乱的数列变成升序数列的操作次数是多少。
然后自然就会想到逆序对。每次变换之后逆序对的个数最多只能-1；
所以答案就是数列中逆序对的个数。
然后就是求逆序对啦。
逆序对有很多种做法：
TOP1：暴力O（N^2）时间TLE BOOM。。。！
TOP2：归并排序
TOP3：线段树
TOP4:树状数组（就是我写的）（又短又好写233~（PS：其实是其他的不会。。））
好吧。
其实我树状数组写的时候也不会，现学的。。
顺便讲讲树状数组的几个基本操作；
NUM1： update
代码如下：
void update(int x) { while(x<=n) { d[x]++; x+=lowbit(x); } }
这就相当于给树状数组赋值/（+/-一个值）
在此lowbit就是x在二进制下的第一个1的位置。
实在看不懂可以找规律： 比如x=1时，n=8时，我们要赋值的数组为d[1],d[2],d[4],d[8];
当x=3时，我们要赋值的数组为d[3],d[4],d[8];
x=5:d[5],d[6],d[8];
恩，就是这样。
NUM2：getsum(相当于查询)
下面贴代码
int getsum(int x) { int ans=0; while(x>0) { ans+=d[x]; x-=lowbit(x); } return ans; }
相当于上一个查询顺序反过来（好像语序有问题。。。）
然后呢，这题就用这2个函数来求逆序对的个数。
在本代码中getsum(x)求的是x之前<=x的数的数量。
这样i-getsum(x)就是x之前>x的数的数量
即对于x的逆序对个数
最后累加一下，就是答案啦！
注意！在本代码中，c数组用于离散化，防止爆栈，同时也加快效率。
d[i]表示在c[i-lowbit(i)]到c[i]中<=c[i]的数出现的总次数！（重点！这个点我理解了很久，要多多消化。也许是因为我蒟蒻。。。）
好吧，下面贴代码
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int c[100001]; struct lisan{ int value,opt; }a[100001],b[100001]; int cmp(lisan a,lisan b){return a.value<b.value;} int d[100001]; int n; int lowbit(int x){return x&(-x);} void update(int x) { while(x<=n) { d[x]++; x+=lowbit(x); } } int getsum(int x) { int ans=0; while(x>0) { ans+=d[x]; x-=lowbit(x); } return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i].value); a[i].opt=i; } for(int i=1;i<=n;i++) { scanf("%d",&b[i].value); b[i].opt=i; } sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); for(int i=1;i<=n;i++) c[b[i].opt]=a[i].opt; int ans=0; for(int i=1;i<=n;i++) { update(c[i]); ans+=i-getsum(c[i]); ans=ans%99999997; } printf("%d\n",ans); }
祝大家编程愉快啦233~（反正我理解了1个多小时。。）
然后狠狠的被CLZ,QRC等一群学弟和zxyerD了一顿。。
火柴排队（NOIP2013）（附树状数组专题讲解（其实只是粗略。。。））