de<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,q;
int h[100005],t[100005];
void add(int *a,int x){
for(;x<=n;x+=(x&-x)) a[x]+=1;
return;
}
int sum(int *a,int x){
int cnt=0;
for(;x;x-=(x&-x)) cnt+=a[x];
return cnt;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&q);
int l,r;
if(q==1){
scanf("%d%d",&l,&r);
add(h,l);
add(t,r);
}
else{
scanf("%d%d",&l,&r);
cout<<sum(h,r)-sum(t,l-1)<<endl;
}
}
return 0;
}
求逆序对
本质上也是通过树状数组单点增加和区间求和的操作进行计算。作为一个专题单独列出来。
桶排+树状数组：
1.桶排部分：
对于一个序列 \(a\) , 我们建立一个 \(cnt\) 数组，\(cnt[x]\) 表示 \(x\) 在序列 \(a\) 中出现过的次数。当 \(a_i=val\) 时，\(cnt[val]++\)。
2.树状数组部分：
倒序扫描序列 \(a\)，对于新加入的数 \(a_i\)，查询 \(cnt[1~a_i-1]\) 的前缀和，并将返回的前缀和加入答案。前缀和部分就可以用树状数组来维护。
操作简单粗暴，但相当好用。
点击查看代码
for ( int i = n; i; i --) {
ans += ask (a[i] - 1);
add (a[i] , 1 );
}
【例题】
接下来通过三道题进一步了解一下逆序对的考法。（不做一下真没想到还能这样考。）
【题意简述】
看到题目显而易见是求逆序对个数。
【思路分析】
看到数据范围 \(x_i,y_i \le 2^{31}-1\)，\(k \le 10^5\)。数据值域大但是个数少，且与数据之间的大小关系有关，因此考虑离散化。
离散化简单介绍
离散化实际就是一种映射，当数据值域过大而个数有限时，可以尝试离散化。
具体过程以此题为例。假设给出这么一组数据
2
123456789 123456
987654321 123456
首先将所有出现过的数收集起来，存进 \(a\) 数组，并进行排序，然后再去重保存进 \(pos\) 数组当中。
接下来就可以建立映射关系。将数值大的数在 \(num\) 数组中用数值小的数代替，但各个数之间的大小关系不变，接下来交换操作先用二分答案在 \(pos\) 数组中检索，然后通过映射在 \(num\) 数组中进行交换。
最终被交换过的数之间的逆序对在 \(num\) 数组中求即可。
被交换的数与未被交换的数之间的逆序对
考虑每个被交换的数对答案的贡献。
设 \(x<y\),当 \(x\) 和 \(y\) 交换后。
对于 \(x\) 来说, \(x \sim y\) 之间所有未被交换的数都比 \(x\) 大，形成逆序对。
对于 \(y\) 来说，\(x \sim y\) 之间所有未被交换的数都比 \(y\) 小，形成逆序对。
逆序对个数都为\(x \sim y\) 之间所有未被交换的数。
温馨提示：以下主要为代码实现讲解，本质思想同上。
对于交换过后的 \(num\) 数组，\(num_i\) 表示的是位置 \(pos_i\) 上当前所在的数在 \(num\) 数组中对应的数。记数 \(x\) 为位置 \(pos_i\) 上当前所在的数。
\(pos_{num_i}\) 表示数 \(x\) 现在所在的位置。
\(pos_i\) 表示数 \(x\) 原来在的位置。
\(\left\vert pos_i-pos_{num_i}-1\right\vert\) 表示两个位置间所有的数。
\(\left\vert num_i-i-1\right\vert\) 表示两个位置间所有被交换过的数。
因此所有未被交换的数就为 \(\left\vert pos_i-pos_{num_i}-1\right\vert - \left\vert num_i-i-1\right\vert\)。
【code】
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct A{
int x,y;
}a[100005];
int k,pos[200005],num[200005],cnt,len;
int t[100005];
void add(int x){
for(;x<=len;x+=(x&-x)) t[x]+=1;
}
long long sum(int x){
long long ans=0;
for(;x;x-=(x&-x)) ans+=t[x];
return ans;
}
int find(int x){
int l=1,r=len;
while(l<r){
int mid=(l+r)>>1;
if(pos[mid]<x) l=mid+1;
else if(pos[mid]>x) r=mid-1;
else return mid;
}
}
int main(){
scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d%d",&a[i].x,&a[i].y);
num[++cnt]=a[i].x;
num[++cnt]=a[i].y;
}
sort(num+1,num+cnt+1);
for(int i=1;i<=cnt;i++){
if(num[i]==num[i-1]) continue;
pos[++len]=num[i];
}
for(int i=1;i<=len;i++) num[i]=i;
for(int i=1;i<=k;i++){
int pos1=find(a[i].x);
int pos2=find(a[i].y);
swap(num[pos1],num[pos2]);
}
long long ans=0;
for(int i=len;i>=1;i--){
add(num[i]);
ans+=sum(num[i]-1);
ans+=abs(pos[num[i]]-pos[i]-1)-abs(num[i]-i-1);
}
cout<<ans<<en