注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3295][Cqoi2011]动态逆序对(CDQ分治)  

2014-07-22 21:10:06|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3295: [Cqoi2011]动态逆序对

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1655  Solved: 536
[Submit][Status][Discuss]

Description

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

Input

输入第一行包含两个整数nm,即初始元素的个数和删除的元素个数。以下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

Solution

首先,暴力的话只要找出每个被删掉的点在剩下的序列中左边比它数大的个数和右边比它小的数的个数,因为是逆序对嘛= =

还有这题是删点,我们可以倒过来看,把它当成在一个序列中加点得到。

一看到逆序对,就要想到归并排序,然而归并排序的本质是cdq分治。于是我们可以考虑添加一个点对于后面的点的答案造成的贡献。

可以这样想,先把这段序列弄成点坐标的形式,正常的逆序对是

x:1   2   3   4   5   6   7   8   9    10 ...

y:a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 ...

用树状数组的话,按x坐标从大到小排序插入,每次查询时只要知道比、它小的个数有多少个就是该点对答案的贡献

现在的话变成这样,加了一维时间维:

n:1 2 3 4 5

x:3 5 4 1 2

y:3 2 4 1 5

(此为样例)

其中n为时间(按输入顺序逆序考虑),x为这个值在原序列中的位置,y为添加的顺序(不足补齐)。

这样转化的话,这道题变成了一个标准的三维偏序的问题,用cdq搞一搞即可。注意要搞两次,一次为左上方,一次为右下方。就是把当前点的(x,y)坐标弄到平面上去,询问之前在这个点左上方和右下方的点的个数。

 

其实这题有很多解法,归并+树状数组最快,还有分块、主席树、树套树、。。。。。。貌似都可A

但是log^2的做法卡时,需要常数优化

Code

/**************************************************************
    Problem: 3295
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2492 ms
    Memory:5108 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cstring>
const int MAXN=100010;
struct D{int x,y;long long f;}a[MAXN];
struct T{int x,y,n;}t[MAXN];
bool cmpx(const T&i,const T&j){return i.x>j.x;}
bool cmpy(const T&i,const T&j){return i.y>j.y;}
int n,m,z[MAXN],w[MAXN],x[MAXN],u[MAXN];char c;
void add(int x){for(;x<=n;x+=x&-x)z[x]++;}
int gs(int x){int f=0;for(;x;x-=x&-x)f+=z[x];return f;}
void clear(int x){for(;x<=n;x+=x&-x)z[x]=0;}
void solve1(int l,int r)
{
    if(l>=r)return;int i,mid=(l+r)>>1;solve1(l,mid);
    for(i=l;i<=r;i++)t[i]=(T){a[i].x,a[i].y,i};
    std::sort(t+l,t+r+1,cmpx);
    for(i=l;i<=r;i++)
        if(t[i].n<=mid)add(t[i].y);
        else a[t[i].n].f+=gs(t[i].y);
    for(i=l;i<=mid;i++)clear(a[i].y);
    solve1(mid+1,r);
}
void solve2(int l,int r)
{
    if(l>=r)return;int i,mid=(l+r)>>1;solve2(l,mid);
    for(i=l;i<=r;i++)t[i]=(T){a[i].x,a[i].y,i};
    std::sort(t+l,t+r+1,cmpy);
    for(i=l;i<=r;i++)
        if(t[i].n<=mid)add(t[i].x);
        else a[t[i].n].f+=gs(t[i].x);
    for(i=l;i<=mid;i++)clear(a[i].x);
    solve2(mid+1,r);
}
void F(int&aa){
    while(c=getchar())if(c>='0'&&c<='9')break;
    do{aa=aa*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
}
int main()
{
    int i,j,y,M;F(n);F(m);M=m;
    for(i=1;i<=n;i++){F(y);w[y]=i;}
    for(i=1;i<=m;i++){F(x[i]);u[x[i]]=1;}
    for(i=1;i<=n;i++)if(!u[i])x[++m]=i;
    m=0;for(i=n;i;i--)a[++m]=(D){w[x[i]],x[i]};
    solve1(1,n);solve2(1,n);m=M;
    for(i=1;i<=n;i++)a[i].f+=a[i-1].f;
    for(i=n;i>=n-m+1;i--)printf("%lld\n",a[i].f);
}
事实证明一年前的我还是逗比,连这种cdq都写成log^2的。。。
upd-20150228
/**************************************************************
    Problem: 3295
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1240 ms
    Memory:6548 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
#define int unsigned
int n,m,k,f[N],i,j,cnt,w[N],u[N],x[N],z[N],ans[N];
struct P{int x,y,z;}a[N],b[N];
void add(int t){for(;t<=n;t+=t&-t)z[t]++;}
int gs(int t,int f=0){for(;t;t-=t&-t)f+=z[t];return f;}
void clr(int t){for(;t<=n;t+=t&-t)z[t]=0;}
void sol(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,i,j,p=l,q=mid+1;
    sol(l,mid),sol(mid+1,r);
    for(i=l;i<=r;i++)b[i]=a[(q==r+1||(p<=mid&&a[p].y<a[q].y))?p++:q++];
    for(i=l;i<=r;i++){
        a[i]=b[i];
        if(a[i].x<=mid)add(a[i].z);
        else f[a[i].x]+=gs(a[i].z);
    }
    for(i=l;i<=r;i++)if(a[i].x<=mid)clr(a[i].z);
}
char B[1<<15],*S=B,*T=B;char getc(){
    return S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++;
}
int aa,ts;char ch,buf[1<<20],*O=buf,stk[20];void Pr(int x){
    if(!x)*O++=48;else{
        for(ts=0;x;x/=10)stk[++ts]=x%10;
        for(;ts;*O++=48+stk[ts--]);
    }
    *O++='\n';
}
int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
main(){
    for(n=F(),k=m=F(),i=1;i<=n;i++)w[F()]=i;
    for(i=1;i<=m;i++)u[x[i]=F()]=1;
    for(i=1;i<=n;i++)if(!u[i])x[++k]=i;
    for(k=0,i=n;i;i--)a[++k]=(P){n-i+1,n-x[i]+1,w[x[i]]};sol(1,n);
    for(k=0,i=n;i;i--)a[++k]=(P){n-i+1,x[i],n-w[x[i]]+1};sol(1,n);
    for(i=1;i<=n;i++)ans[i]=ans[i-1]+f[i];
    for(i=1,k=n;i<=m;i++)Pr(ans[k--]);*--O=0,puts(buf);
}
可以不用写两个函数,只要在最开始把坐标换一下,就变成了x'<x,y'<y,z'<z这类的问题。
  评论这张
 
阅读(1750)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018