【题意】
每次删除一个数，然后问删除前逆序对数。
【分析】
没有AC不开心。。
我的树状数组套字母树，应该是爆空间的，空间复杂度O（nlogn^2）啊。。哭。。
然后就没有然后了，别人家的树套树是树状数组套平衡树，O(nlogn)的啊。。
别人家的CDQ分治更屌。。我垃圾咯。
只是存个代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 200010
#define Maxd 31 int a[Maxn],wr[Maxn];
int n,m; struct node
{
int son[],cnt;
}tr[Maxn**];int tot; void upd(int x)
{
tr[x].son[]=tr[x].son[]=;
tr[x].cnt=;
} void add(int now,int y,int c)
{
for(int i=Maxd;i>=;i--)
{
int ind=y>>i-;
y=y%(<<i-);
if(!tr[now].son[ind])
{
tr[now].son[ind]=++tot;
upd(tot);
}
now=tr[now].son[ind];
tr[now].cnt+=c;
}
} int ffind(int now,int y)
{
int ans=;
for(int i=Maxd;i>=;i--)
{
int ind=y>>i-;
y=y%(<<i-);
if(ind==)
{
ans+=tr[tr[now].son[]].cnt;
now=tr[now].son[];
}
else now=tr[now].son[];
}
return ans;
} int sm[Maxn];
void change(int x,int y,int c)
{
for(int i=x;i<=n;i+=i&(-i))
add(i,y,c),sm[i]+=c; } int ad;
int query(int x,int y)
{
ad=;
int ans=;
for(int i=x;i>=;i-=i&(-i))
ad+=sm[i],ans+=ffind(i,y);
return ans;
} int main()
{
int ans=;
scanf("%d%d",&n,&m);
memset(sm,,sizeof(sm));
for(int i=;i<=n;i++) {scanf("%d",&a[i]);wr[a[i]]=i;}
upd();
tot=n;
for(int i=;i<=n;i++)
{
ans+=query(i-,a[i]);
change(i,a[i],);
}
int sum=n;
for(int i=;i<=m;i++)
{
int x;
scanf("%d",&x);
printf("%d\n",ans);
sum--;
change(wr[x],x,-);
int now=-query(n,x);
now+=*query(wr[x]-,x);
ans-=sum+now-ad;
}
return ; }
2016-11-08 16:42:22
学了cdq分治回来更新耶！！
用CDQ分治AC啦哈哈~~
CDQ分治比树套树省空间多了，空间是O（n）的，时间还是O（nlogn^2）
然后，简单说一下？
我自己也不是很懂，刚会。。
Solve(l,r)为求出区间l~r的答案。
然后只有编号小于它的对他有影响。
然后二分 [l,mid]和[mid+1,r],,考虑完[l,mid]对[mid+1,r]的影响之后，那两个区间就可以分开搞了。（就是分治）
问题变成快速求[l,mid]对[mid+1,r]的影响。
本题中，我们可以看成是一个三元组i->(xi,yi,zi),然后ans[i]=x<xi y<yi z>zi或者x<xi y>yi z<zi 的数量。。
x这一维是时间戳，y是编号，z是值（想一想就知道他为什么表示逆序对啦！！！）
那么，只有x<xi的对xi有影响，把x这一维作为编号。
快速求出，[l,mid]对[mid+1,r]中y<yi z>zi或者y>yi z<zi 的数量
可以用y排序，树状数组维护，求和，就知道y和z的逆序对数了。。
n元组，满足x>xi,y>yi....的个数的东东 。。【这东西叫n维偏序？？？好像是CDQ分治的经典题哦！！
啊。。。WA了好久，竟然是没有开LL！！！！好傻啊、、
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 200010
#define LL long long int a[Maxn],b[Maxn];
LL f[Maxn];
int n,m; int c[Maxn];
bool vis[Maxn]; struct node
{
int x,y,id;
}t[Maxn];int tl; int mymax(int x,int y) {return x>y?x:y;}
bool cmp(node x,node y) {return x.x>y.x;}
bool cmp2(node x,node y) {return x.x<y.x;} void add(int x,int y)
{
for(int i=x;i<=n;i+=i&(-i))
c[i]+=y;
} int query(int x)
{
int ans=;
for(int i=x;i>=;i-=i&(-i))
ans+=c[i];
return ans;
} void solve2(int l,int r)
{
tl=;
for(int i=l;i<=r;i++)
{
t[++tl].x=a[i];
t[tl].y=b[i];
t[tl].id=i;
}
sort(t+,t++tl,cmp);
for(int i=;i<=tl;i++)
{
if(vis[t[i].id]) f[t[i].id]+=query(t[i].y);
else add(t[i].y,);
}
for(int i=;i<=tl;i++) if(!vis[t[i].id]) add(t[i].y,-);
sort(t+,t++tl,cmp2);
for(int i=;i<=tl;i++)
{
if(vis[t[i].id]) f[t[i].id]+=query(n-t[i].y+);
else add(n-t[i].y+,);
}
for(int i=;i<=tl;i++) if(!vis[t[i].id]) add(n-t[i].y+,-);
} void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>;
for(int i=l;i<=mid;i++) vis[i]=;
for(int i=mid+;i<=r;i++) vis[i]=;
solve2(l,r);
solve(l,mid);solve(mid+,r);
} int wr[Maxn],d[Maxn];
void init()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
wr[x]=i;
}
for(int i=n;i>n-m;i--)
{
int x;
scanf("%d",&x);
a[i]=x;
b[i]=wr[x];
wr[x]=;
}
int now=n-m+;
for(int i=;i<=n;i++) if(wr[i]!=) a[--now]=i,b[now]=wr[i];
memset(c,,sizeof(c));
memset(f,,sizeof(f));
} int main()
{
init();
solve(,n);
LL ans=;
for(int i=;i<=n;i++) ans+=f[i];
for(int i=n;i>n-m;i--)
{
printf("%lld\n",ans);
ans-=f[i];
}
return ;
}
代码还不是很长啦，主要是CDQ分治空间真的要小很多。。
所以才知道，为什么大神说树套树粉转路人了ORZ。。。
2016-11-08 20:14:57