BZOJ 3333 排队计划 树状数组+线段树

题目大意：给定一个序列。每次选择一个位置，把这个位置之后全部小于等于这个数的数抽出来，排序，再插回去，求每次操作后的逆序对数

首先我们每一次操作 对于这个位置前面的数 因为排序的数与前面的数位置关系不变 所以这些数的逆序对不会变化

对于这个位置后面比这个数大的数 因为改变位置的数都比这些数小 所以这些数的逆序对不会变化

说究竟就是排序的数的逆序对数改变了 以这些数開始的逆序对没有了

于是就好办了 我们用树状数组统计出以每一个数開始的逆序对数 然后以原数的大小为keyword建立线段树 维护区间最小值

对于每一个询问p,我们取出[p,n]中的最小值a[x]。将a[x]清为正无穷。把以a[x]开头的逆序对减掉，继续找，直到a[p]为正无穷为止

每一个数仅仅会被找到1次 所以均摊复杂度O(nlogn)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 500500
#define ls tree[p].lson
#define rs tree[p].rson
using namespace std;
struct abcd{
int lson,rson;
int *num;
}tree[M<<1];int tree_tot;
int n,m,tot,a[M];
pair<int,int>b[M];
int c[M],f[M];
long long ans;
int* _min(int *x,int *y)
{
return *x>=*y?y:x;
}
void Build_Tree(int p,int x,int y)
{
int mid=x+y>>1;
if(x==y)
{
tree[p].num=a+mid;
return ;
}
ls=++tree_tot;rs=++tree_tot;
Build_Tree(ls,x,mid);
Build_Tree(rs,mid+1,y);
tree[p].num=_min(tree[ls].num,tree[rs].num);
}
int* Get_Ans(int p,int x,int y,int l,int r)
{
int mid=x+y>>1;
if(x==l&&y==r)
return tree[p].num;
if(r<=mid)
return Get_Ans(ls,x,mid,l,r);
if(l>mid)
return Get_Ans(rs,mid+1,y,l,r);
return _min( Get_Ans(ls,x,mid,l,mid) , Get_Ans(rs,mid+1,y,mid+1,r) );
}
inline void Modify(int p,int x,int y,int pos)
{
int mid=x+y>>1;
if(x==y)
return ;
if(pos<=mid)
Modify(ls,x,mid,pos);
else
Modify(rs,mid+1,y,pos);
tree[p].num=_min(tree[ls].num,tree[rs].num);
}
inline void Update(int x)
{
for(;x<=tot;x+=x&-x)
c[x]++;
}
inline int Get_Ans(int x)
{
int re=0;
for(;x;x-=x&-x)
re+=c[x];
return re;
}
int main()
{
int i,p;
cin>>n>>m;
for(i=1;i<=n;i++)
scanf("%d",&b[i].first),b[i].second=i;
sort(b+1,b+n+1);
for(i=1;i<=n;i++)
{
if(i==1||b[i].first!=b[i-1].first)
++tot;
a[b[i].second]=tot;
}
for(i=n;i;i--)
Update(a[i]),ans+=f[i]=Get_Ans(a[i]-1);
Build_Tree(0,1,n);
printf("%lld\n",ans);
for(i=1;i<=m;i++)
{
int *temp;
scanf("%d",&p);
if(a[p]!=0x3f3f3f3f)
do{
temp=Get_Ans(0,1,n,p,n);
ans-=f[temp-a];
*temp=0x3f3f3f3f;
Modify(0,1,n,temp-a);
}while(temp!=a+p);
printf("%lld\n",ans);
}
}