https://www.luogu.com.cn/problem/P1908
https://www.luogu.com.cn/problem/P1774
同样的代码可交两题
虽然不太想写博客，但这题比较巧妙，单独拿出来总结一下。一共三个知识点：
1.树状数组的基本应用。
2.离散化的处理：在不改变数据大小的情况下，对数据进行相应的处理，防止RE。一句话就是哦那个过下标记录数据大小的相对位置。
（树状数组的应用和离散化都是降低复杂度的有力工具）
3.最关键的是，数据是有可能出现数值相同的情况，要进行特殊处理，不能以快排结束，破坏了相对位置。
最难理解的是这两条语句：
for(register ll i=1;i<=n;i++) { add(b[i],1); ans+=i-sum(b[i]); }
b[i]记录的是原数据从小到大排序后的下标情况，数值是从小到大加入，但加入的位置是原数据的位置。
sum(b[i])表示1到b[i]总共有多少个数，然后读入循环走几轮就理解离散化原理了，太妙了，我现在只知道怎么做，但具体提为什么还不清楚。
#include using namespace std;typedef long long ll;const int maxn=5e5+5; //数据要用到离散化struct node{ ll val,order;}e[maxn];bool cmp(node e1,node e2){ return e1.val0) { ret+=d[x];x-=x&-x; } return ret;}int main(){ ll ans=0; scanf("%lld",&n); for(register ll i=1;i<=n;i++) { scanf("%lld",&e[i].val); e[i].order=i; } sort(e+1,e+n+1,cmp); b[e[1].order]=1; for(register ll i=2,ct=1;i<=n;i++) { if(e[i].val==e[i-1].val) b[e[i].order]=ct; else b[e[i].order]=++ct; } for(register ll i=1;i<=n;i++) { add(b[i],1); ans+=i-sum(b[i]); } printf("%lld",ans); return 0;}