
题目链接:https://nanti.jisuanke.com/t/16443
题意:
给你一个由1~n构成的正整数序列,有m组询问,每组询问要求输出[l , r]区间内的逆序对个数。
数据范围:
对于100%的数据,满足1 <= n,m <= 30000,l < r,∑ | l[i] - l[i-1] | + ∑ | r[i] - r[i-1] | <= 7 * 10^6。
题解:
如果知道区间[l , r]中的逆序对个数,那么也可以快速求出区间[l-1 , r],[l+1 , r],[l , r-1],[l , r+1]的逆序对个数。
① [l-1 , r]的个数 = [l , r]的个数 + [l , r]中比a[l-1]小的元素的个数
② [l+1 , r]的个数 = [l , r]的个数 - [l+1 , r]中比a[l]小的元素的个数
③ [l , r-1]的个数 = [l , r]的个数 - [l , r-1]中比a[r]大的元素的个数
④ [l , r+1]的个数 = [l , r]的个数 + [l , r]中比a[r+1]大的元素的个数
查询区间内比x大(小)的元素的个数用树状数组实现。
比x大的元素个数 = query(x - 1)
比x小的元素个数 = query(n) - query(x) (区间内元素总个数减去大于等于x的元素个数)
先假定现在的区间为[1 , 1],逆序对总个数为0。对于每一组询问,只要不断移动当前区间的左右端点,并同时更新答案,直至当前区间与询问区间相同即可,输出sum值。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 30005 using namespace std; int n,m;
int a[MAX_N];
int dat[MAX_N]; void update(int k,int a)
{
while(k<=n)
{
dat[k]+=a;
k+=k&-k;
}
} int query(int k)
{
int sum=;
while(k>)
{
sum+=dat[k];
k-=k&-k;
}
return sum;
} void read()
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>a[i];
}
} void solve()
{
memset(dat,,sizeof(dat));
cin>>m;
int sum=;
int lef=,rig=;
update(a[],);
for(int i=;i<m;i++)
{
int l,r;
cin>>l>>r;
while(lef<l)
{
update(a[lef],-);
sum-=query(a[lef]-);
lef++;
}
while(lef>l)
{
lef--;
sum+=query(a[lef]-);
update(a[lef],);
}
while(rig<r)
{
rig++;
sum+=query(n)-query(a[rig]);
update(a[rig],);
}
while(rig>r)
{
update(a[rig],-);
sum-=query(n)-query(a[rig]);
rig--;
}
cout<<sum<<endl;
}
} int main()
{
read();
solve();
}