P3157 [CQOI2011] 动态逆序对
题目描述
对于序列 \(A\), 它的逆序对数定义为满足 \(i<j\), 且 \(A_i>A_j\) 的数对 \((i,j)\) 的个数. 给 \(1\) 到 \(n\) 的一个排列, 按照某种顺序依次删除 \(m\) 个元素, 你的任务是在每次删除一个元素之前统计整个序列的逆序对数.
输入输出格式
输入格式:
输入第一行包含两个整数 \(n\) 和 \(m\), 即初始元素的个数和删除的元素个数. 以下 \(n\) 行每行包含一个 \(1\) 到 \(n\) 之间的正整数, 即初始排列. 以下 \(m\) 行每行一个正整数, 依次为每次删除的元素.
输出格式:
输出包含 \(m\) 行, 依次为删除每个元素之前, 逆序对的个数.
说明
\(N\le 100000,M\le 50000\)
万年以前树套树怎么都是 60pts, 今天终于决定进行 CDQ 分治水过去.
每个元素安排三个属性为 \(P_i,A_i,D_i\) 分别代表在原序列的位置, 元素值和被删时间.
然后我们统计一下 \(P_i <P_j,A_i>A_j,D_i<D_j\) 的个数.
然后我调了半个多小时...
终于弄明白 \(P_i> P_j,A_i<A_j,D_i<D_j\) 也要统计...
- Code:
- #include <cstdio>
- #include <algorithm>
- #define ll long long
- const int N=1e5+10;
- struct node{int a,b,p;}sq[N];
- int n,m,s[N];
- ll ans[N];
- void add(int x,int d){while(x<=m)s[x]+=d,x+=x&-x;}
- int ask(int x){int sum=0;while(x)sum+=s[x],x-=x&-x;return sum;}
- bool cmp1(node n1,node n2){return n1.a>n2.a;}
- bool cmp2(node n1,node n2){return n1.a<n2.a;}
- void CDQ(int l,int r)
- {
- if(l==r) return;
- int mid=l+r>>1;
- CDQ(l,mid),CDQ(mid+1,r);
- std::sort(sq+l,sq+r+1,cmp1);
- for(int i=l;i<=r;i++)
- {
- if(sq[i].p<=mid) add(sq[i].b,1);
- else ans[sq[i].b]+=1ll*(ask(m)-ask(sq[i].b-1));
- }
- for(int i=l;i<=r;i++) if(sq[i].p<=mid) add(sq[i].b,-1);
- std::sort(sq+l,sq+r+1,cmp2);
- for(int i=l;i<=r;i++)
- {
- if(sq[i].p>mid) add(sq[i].b,1);
- else ans[sq[i].b]+=1ll*(ask(m)-ask(sq[i].b-1));
- }
- for(int i=l;i<=r;i++) if(sq[i].p>mid) add(sq[i].b,-1);
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int a,i=1;i<=n;i++)
- {
- scanf("%d",&a);
- sq[a].a=i;
- sq[a].b=m;
- sq[a].p=a;
- }
- for(int a,i=1;i<=m;i++)
- {
- scanf("%d",&a);
- sq[a].b=i;
- }
- CDQ(1,n);
- ans[m]>>=1;
- for(int i=m-1;i;i--) ans[i]+=ans[i+1];
- for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
- return 0;
- }
- 2018.11.27
来源: http://www.bubuko.com/infodetail-2862782.html