树状数组的简单应用求逆序数
需要离线树状数组,正反2次求
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int c[100100],a[50010];
int l[50010],r[50010]; //记录每一个改变位置的改变对于此位置以左和以右的逆序数的影响
int maxl;
int n,m;
struct point{
int p,q,pos;
}num[50010];
int max(int u,int v){
return u>v?u:v;
}
int cmp(const void*u,const void*v){
struct point*uu=(struct point*)u;
struct point*vv=(struct point*)v;
return uu->p>vv->p;
}
int lowbit(int x){
return x&(x^(x-1));
}
int sum(int x){
int ss=0;
while(x>0){
ss+=c[x];
x-=lowbit(x);
}
return ss;
}
void update(int x,int val){
while(x<=maxl){
c[x]+=val;
x+=lowbit(x);
}
}
int main(){
int i,j,res,tem;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]++;
maxl=max(maxl,a[i]);
}
for(i=1;i<=m;i++){
scanf("%d %d",&num[i].p,&num[i].q);
num[i].q++;
num[i].pos=i;
maxl=max(maxl,num[i].q);
}
qsort(&num[1],m,sizeof(num[1]),cmp);
memset(c,0,sizeof(c));
res=0;
j=1;
for(i=1;i<=n;i++){
tem=i-1-sum(a[i]);
res+=tem;
while(j<=m && num[j].p==i){
l[num[j].pos]=i-1-sum(num[j].q)-tem;
j++;
}
update(a[i],1);
}
j=m;
memset(c,0,sizeof(c));
for(i=n;i>=1;i--){
tem=sum(a[i]-1);
while(j>=1 && num[j].p==i){
r[num[j].pos]=sum(num[j].q-1)-tem;
j--;
}
update(a[i],1);
}
printf("%d\n",res);
for(i=1;i<=m;i++){
printf("%d\n",res+l[i]+r[i]);
}
}
分享到:
相关推荐
LISY300AL单轴MEMS陀螺仪数据手册 单轴 MEMS 陀螺仪 300度量程
是一款仿微信水果忍者的游戏,游戏代码简单易懂易学。
意法半导体(ST)推出新款MEMS单轴航向陀螺仪LISY300AL,这款产品采用7 x 7 x 1.5mm的表面贴装封装,角速度测量性能高达每秒300度(全量程)。新产品的主要特性包括:高灵敏度,电源电压范围扩大,从2.7V到3.6V,...
意法半导体(ST)推出新款MEMS单轴航向陀螺仪LISY300AL,这款产品采用7 x 7 x 1.5mm的表面贴装封装,角速度测量性能高达每秒300度(全量程)。新产品的主要特性包括:高灵敏度,电源电压范围扩大,从2.7V到3.6V,...
相关文章http://blog.csdn.net/lisy14/article/details/68062091
相关文章http://blog.csdn.net/lisy14/article/details/70141301
相关文章:http://blog.csdn.net/lisy14/article/details/68062091
详细介绍了OPENGL的入门知识和开发流程
用java写的一个日历,可以记录当天的事件。
红绿截图工具,随时随地截图,方便快捷,还可以录屏,还具有标尺功能。
光伏发电作为新兴的前沿科技已经逐步技术成熟。现在将光伏发电系统与屋顶集合到一起。建设家用屋顶分布式系统,实现发电自用,余量上网方式,已经成为大势所趋。