hdu5196 DZY Loves Inversions 思路，计数

本文主要是介绍hdu5196 DZY Loves Inversions 思路，计数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：一个数列，给出一些区间，计算这个区间有多少子区间逆序对数为k。

分析：直接计算k不好算，把问题转化为<=k的子区间数减去<k的子区间数。首先由两个指针可以求出每一个点的满足<=k或<k的最右边界。得到r1和r2数组。

   最后所求即为sum(min(r1i,r)-l+1) (i>=l&&i<=r)，r数组单调递增，二分即可。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<ostream>
#include<istream>
#include<algorithm>
#include<queue>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<vector>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define inf (1<<30)
#define eps 1e-8
#define pb push_back
#define debug puts("=====")
using namespace std;
const int maxn=100005;
int n,q;
ll k;
int l,r;
int d[maxn];
int dis[maxn];
int r1[maxn],r2[maxn];
ll s1[maxn],s2[maxn];
int tree[maxn];
int lowbit(int x)
{return x&-x;
}
int Sum(int a)
{int sum=0;while(a>0) {sum+=tree[a];a-=lowbit(a);}return sum;
}
void update(int x,int c)
{while(x<=n) {tree[x]+=c;x+=lowbit(x);}
}
void pre()
{memset(tree,0,sizeof(tree));int i=1,j=0;ll sum=0;while(i<=n) {while(sum<=k && j<=n) {j++;if(j==n+1) break;sum+=Sum(n)-Sum(d[j]);update(d[j],1);}r1[i]=j-1;update(d[i],-1);sum-=Sum(d[i]-1);i++;}memset(tree,0,sizeof(tree));i=1,j=0,sum=0;while(i<=n) {while(sum<=k-1 && j<=n) {j++;if(j==n+1) break;sum+=Sum(n)-Sum(d[j]);update(d[j],1);}r2[i]=j-1;update(d[i],-1);sum-=Sum(d[i]-1);i++;}s1[0]=s2[0]=0;for(int i=1;i<=n;i++) {s1[i]=s1[i-1]+r1[i];s2[i]=s2[i-1]+r2[i];}
}
int main()
{while(~scanf("%d%d%I64d",&n,&q,&k)) {for(int i=1;i<=n;i++) {scanf("%d",&d[i]);dis[i-1]=d[i];}sort(dis,dis+n);int tot=unique(dis,dis+n)-dis;for(int i=1;i<=n;i++) {d[i]=lower_bound(dis,dis+tot,d[i])-dis+1;}pre();ll ans;while(q--) {ans=0;scanf("%d%d",&l,&r);int kk=upper_bound(r1+l,r1+r+1,r)-r1;kk--;ans+=s1[kk]-s1[l-1];ans+=(ll)(r-kk)*r;if(k==0) {ans+=(ll)(r-l+1)*(2-l-r)/2;printf("%I64d\n",ans);continue;}kk=upper_bound(r2+l,r2+r+1,r)-r2;kk--;ans-=s2[kk]-s2[l-1];ans-=(ll)(r-kk)*r;printf("%I64d\n",ans);}}return 0;
}

这篇关于hdu5196 DZY Loves Inversions 思路，计数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---