3295: [Cqoi2011]动态逆序对
Time Limit: 10 Sec Memory Limit: 128 MB
Description
Input
Output
Sample Input
1
5
3
4
2
5
1
4
2
Sample Output
2
2
1
样例解释
(1,5,3,4,2) (1,3,4,2) (3,4,2) (3,2) (3)。
HINT
N<=100000 M<=50000
题解:
啊啊啊这道题真的是差点把自己打死
跟zyfdalao分享了一下思路然后他就按我的思路A了可是我自己却不会了
如果你是树套树玩家,请移步:http://www.cnblogs.com/TSHugh/p/7001884.html
在具体写题解之前,我要分享一个面对瓶颈很好的做法(我这样反复理了三遍,思路一遍比一遍清晰...遇到瓶颈的时候真的很推荐这样做):
思路不通了把所有已知条件再列出来一边,写清变量之间的关系和限制,并且针对每一个条件写出解决方案和打法
感觉凌乱的代码段就删掉重打一遍,用的总时间一定会比死调下去少
首先一个小优化:把val变成n-val+1,这样原来的逆序对就变成了现在的顺序对,个人感觉更加好操作.
我们考虑,我们可以利用树状数组求出一开始总的逆序对数,并且同时利用树状数组求出以每个位置为开头和结尾的逆序对个数,
我们设num数组表示这个数目,num[0][i]表示以i位置结尾的逆序对个数,num[1][i]表示以i位置开头的逆序对个数.
这样的话,每次我们先输出当前的总数,再减去num[0][i]+num[1][i],然后...
我们发现有一些不对,如果原来形成的逆序对的另外那个数已经被删除了,那么这一对就不应该被减去
所以我们考虑再计算一个delta表示这个增量:
其中delta[0][i]表示以i位置结尾,但是另外那个数比i删除的早的逆序对个数,
delta[1][i]表示以i位置开头,但是另外那个数比i删除的早的逆序对个数.
接下来我们考虑什么样的数对(i,j)会被记入delta
如果设i位置的数的删除时间是tim[i](没有被删除的数的删除时间顺次设成m+1~n即可,他们的delta不会被记入答案)
设i位置的数值是val[i](这里的val已经进行了n-val+1取反操作)
那么delta[0][i]里的数应该满足:
tim[i]>tim[j]
val[i]>val[j]
i>j
delta[1][i]里的数应该满足:
tim[i]>tim[j]
val[i]<val[j]
i<j
那么上面这两组约束条件(尤其是第一组)很像一个三维偏序的统计问题.
的确如此,我们只需要用CDQ分治统计一下符合条件的数对数即可.
拿我的思路来说,我们可以让时间有序,给下标排序,用树状数组维护权值val,
这样跑两遍CDQ统计符合条件的偏序对数,就能分别计算delta[0][i]和delta[1][i]
最后输出答案时,先输出答案ans,然后给ans减去num[0][i]+num[1][i],再加上delta[0][i]+delta[1][i],这样就能正确的维护逆序对数了,
代码实现:
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=,M=;
struct node
{
int tim,val,pos;
node (int a=,int b=,int c=){tim=a,val=b,pos=c;}
}q[N];
int cnt,n,m,a[N],match[N],step[M];
bool vis[N];
LL delta[][N],num[][N],bit[N];
inline int lowbit(int a){return a&-a;}
inline void add(int a,LL b)
{while(a<=n)bit[a]+=b,a+=lowbit(a);}
inline LL sum(int a)
{LL ret=;while(a)ret+=bit[a],a-=lowbit(a);return ret;}
inline void gsum0()
{
for(register int i=;i<=n;++i)
num[][i]=sum(a[i]),add(a[i],);
memset(bit,,sizeof(bit));
}
inline void gsum1()
{
for(register int i=n;i;--i)
num[][i]=sum(a[i]),add(,),add(a[i],-);
memset(bit,,sizeof(bit));
}
inline void readin()
{
register int i;scanf("%d%d",&n,&m);
for(i=;i<=n;++i)
scanf("%d",&a[i]),a[i]=n-a[i]+,match[a[i]]=i;
gsum0();gsum1();
for(i=;i<=m;++i)
scanf("%d",&step[i]),step[i]=n-step[i]+,vis[step[i]]=;
}
inline bool mt1(const node &a,const node &b){return a.pos<b.pos;}
inline bool mt2(const node &a,const node &b){return a.tim<b.tim;}
inline void CDQ0(int l,int r)
{
if(l==r)return;
register int mi=l+r>>,i;
CDQ0(l,mi);CDQ0(mi+,r);
sort(q+l,q+r+,mt1);
for(i=l;i<=r;++i)
if(q[i].tim<=mi)add(q[i].val,);
else delta[][q[i].tim]+=sum(q[i].val);
for(i=l;i<=r;++i)
if(q[i].tim<=mi)add(q[i].val,-);
}
inline void CDQ1(int l,int r)
{
if(l==r)return;
register int mi=l+r>>,i;
CDQ1(l,mi);CDQ1(mi+,r);
sort(q+l,q+r+,mt1);
for(i=r;i>=l;--i)
if(q[i].tim<=mi)add(,),add(q[i].val,-);
else delta[][q[i].tim]+=sum(q[i].val);
for(i=r;i>=l;--i)
if(q[i].tim<=mi)add(,-),add(q[i].val,);
}
int main()
{
register int i;readin();
for(i=;i<=m;++i)
q[++cnt]=node(cnt,step[i],match[step[i]]);
for(i=;i<=n;++i)
if(!vis[a[i]])q[++cnt]=node(cnt,a[i],i);
CDQ0(,n),sort(q+,q+n+,mt2),CDQ1(,n);
LL ans=;int pos;
for(i=;i<=n;++i)ans+=num[][i];
for(i=;i<=m;++i)
{
printf("%lld\n",ans),pos=match[step[i]],
ans-=(num[][pos]+num[][pos]),
ans+=(delta[][i]+delta[][i]);
}
}