「BZOJ3295」[CQOI2011] 动态逆序对

2014年6月17日8,2624

Description

对于序列A，它的逆序对数定义为满足i<j，且A_i>A_j的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

Output

输出包含m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

5 4
1
5
3
4
2
5
1
4
2

Sample Output

5
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

题解

树状数组套线段树

删除某个数，只要统计它之前还存在的比它大的数的个数，和之后还存在的比它小的数的个数

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define inf 0x7fffffff
#define ll long long
#define N 100005
#define M 5000005
using namespace std;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n,m,sz;
int A[30],B[30];
int num[N],pos[N],a1[N],a2[N];
int t[N],root[N];
int ls[M],rs[M],sum[M];
inline int lowbit(int x){return x&(-x);}
inline int getans(int x)
{
	int tmp=0;
	for(int i=x;i;i-=lowbit(i))
	    tmp+=t[i];
	return tmp;
}
void update(int &y,int l,int r,int x)
{
    if(!y)y=++sz;
    sum[y]++;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(x<=mid)update(ls[y],l,mid,x);
    else update(rs[y],mid+1,r,x);
}
int askmore(int x,int y,int num)
{
	A[0]=B[0]=0;int tmp=0;x--;
	for(int i=x;i;i-=lowbit(i))A[++A[0]]=root[i];
	for(int i=y;i;i-=lowbit(i))B[++B[0]]=root[i];
	int l=1,r=n;
	while(l!=r)
	{
		int mid=(l+r)>>1;
        if(num<=mid)
        {
            for(int i=1;i<=A[0];i++)tmp-=sum[rs[A[i]]];
            for(int i=1;i<=B[0];i++)tmp+=sum[rs[B[i]]];
            for(int i=1;i<=A[0];i++)A[i]=ls[A[i]];
            for(int i=1;i<=B[0];i++)B[i]=ls[B[i]];
            r=mid;
        }
		else
        {
            for(int i=1;i<=A[0];i++)A[i]=rs[A[i]];
            for(int i=1;i<=B[0];i++)B[i]=rs[B[i]];
            l=mid+1;
        }
	}
	return tmp;
}
int askless(int x,int y,int num)
{
	A[0]=B[0]=0;int tmp=0;x--;
	for(int i=x;i;i-=lowbit(i))A[++A[0]]=root[i];
	for(int i=y;i;i-=lowbit(i))B[++B[0]]=root[i];
	int l=1,r=n;
	while(l!=r)
	{
		int mid=(l+r)>>1;
        if(num>mid)
        {
            for(int i=1;i<=A[0];i++)tmp-=sum[ls[A[i]]];
            for(int i=1;i<=B[0];i++)tmp+=sum[ls[B[i]]];
            for(int i=1;i<=A[0];i++)A[i]=rs[A[i]];
            for(int i=1;i<=B[0];i++)B[i]=rs[B[i]];
            l=mid+1;
        }
		else
        {
            for(int i=1;i<=A[0];i++)A[i]=ls[A[i]];
            for(int i=1;i<=B[0];i++)B[i]=ls[B[i]];
            r=mid;
        }
	}
	return tmp;
}
int main()
{
	n=read();m=read();
    for(int i=1;i<=n;i++)
    {
    	num[i]=read();pos[num[i]]=i;
    	a1[i]=getans(n)-getans(num[i]);
    	ans+=a1[i];
    	for(int j=num[i];j<=n;j+=lowbit(j))
    	    t[j]++;
    }
    memset(t,0,sizeof(t));
    for(int i=n;i>=1;i--)
    {
    	a2[i]=getans(num[i]-1);
    	for(int j=num[i];j<=n;j+=lowbit(j))
    	    t[j]++;
    }
    for(int i=1;i<=m;i++)
    {
    	printf("%lld\n",ans);
    	int x=read();x=pos[x];
    	ans-=(a1[x]+a2[x]-askmore(1,x-1,num[x])-askless(x+1,n,num[x]));
        for(int j=x;j<=n;j+=lowbit(j))update(root[j],1,n,num[x]);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#define inf 0x7fffffff

#define ll long long

#define N 100005

#define M 5000005

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans;

int n,m,sz;

int A[30],B[30];

int num[N],pos[N],a1[N],a2[N];

int t[N],root[N];

int ls[M],rs[M],sum[M];

inline int lowbit(int x){return x&(-x);}

inline int getans(int x)

{

int tmp=0;

for(int i=x;i;i-=lowbit(i))

tmp+=t[i];

return tmp;

}

void update(int &y,int l,int r,int x)

{

if(!y)y=++sz;

sum[y]++;

if(l==r)return;

int mid=(l+r)>>1;

if(x<=mid)update(ls[y],l,mid,x);

else update(rs[y],mid+1,r,x);

}

int askmore(int x,int y,int num)

{

A[0]=B[0]=0;int tmp=0;x--;

for(int i=x;i;i-=lowbit(i))A[++A[0]]=root[i];

for(int i=y;i;i-=lowbit(i))B[++B[0]]=root[i];

int l=1,r=n;

while(l!=r)

{

int mid=(l+r)>>1;

if(num<=mid)

{

for(int i=1;i<=A[0];i++)tmp-=sum[rs[A[i]]];

for(int i=1;i<=B[0];i++)tmp+=sum[rs[B[i]]];

for(int i=1;i<=A[0];i++)A[i]=ls[A[i]];

for(int i=1;i<=B[0];i++)B[i]=ls[B[i]];

r=mid;

}

else

{

for(int i=1;i<=A[0];i++)A[i]=rs[A[i]];

for(int i=1;i<=B[0];i++)B[i]=rs[B[i]];

l=mid+1;

}

return tmp;

}

int askless(int x,int y,int num)

{

A[0]=B[0]=0;int tmp=0;x--;

for(int i=x;i;i-=lowbit(i))A[++A[0]]=root[i];

for(int i=y;i;i-=lowbit(i))B[++B[0]]=root[i];

int l=1,r=n;

while(l!=r)

{

int mid=(l+r)>>1;

if(num>mid)

{

for(int i=1;i<=A[0];i++)tmp-=sum[ls[A[i]]];

for(int i=1;i<=B[0];i++)tmp+=sum[ls[B[i]]];

for(int i=1;i<=A[0];i++)A[i]=rs[A[i]];

for(int i=1;i<=B[0];i++)B[i]=rs[B[i]];

l=mid+1;

}

else

{

for(int i=1;i<=A[0];i++)A[i]=ls[A[i]];

for(int i=1;i<=B[0];i++)B[i]=ls[B[i]];

r=mid;

}

return tmp;

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

{

num[i]=read();pos[num[i]]=i;

a1[i]=getans(n)-getans(num[i]);

ans+=a1[i];

for(int j=num[i];j<=n;j+=lowbit(j))

t[j]++;

}

memset(t,0,sizeof(t));

for(int i=n;i>=1;i--)

{

a2[i]=getans(num[i]-1);

for(int j=num[i];j<=n;j+=lowbit(j))

t[j]++;

}

for(int i=1;i<=m;i++)

{

printf("%lld\n",ans);

int x=read();x=pos[x];

ans-=(a1[x]+a2[x]-askmore(1,x-1,num[x])-askless(x+1,n,num[x]));

for(int j=x;j<=n;j+=lowbit(j))update(root[j],1,n,num[x]);

}

return 0;

}

« 「BZOJ1103」[POI2007] 大都市meg 「CODEVS3044」矩形面积求并 »

zld3794955

Orzhzwer学长= =我原来写树状数组套主席树一直爆内存只好用CDQ分治水了T T

hzwer

orz北大爷。。。CDQ分治水…我不会CDQ分治

zld3794955

OrzHZWER学长。。直接把本弱CDQ分治给D成水了T T

hzwer

我只是在复述你的话

hzwer.com _ Home | http://hzwer.com

「BZOJ3295」[CQOI2011] 动态逆序对

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论