洛谷P3157 动态逆序对 [CQOI2011] cdq分治
正解:cdq分治
解题报告:
这题首先想到的就直接做逆序对,然后记录每个点的贡献,删去就减掉就好
但是仔细一想会发现布星啊,如果有一对逆序对的两个点都被删了岂不是就减重了嘛
那就再加上一个值
这个值是什么呢,就是满足逆序对且逆序对的另一个数的删除时间小于这个数的数对的个数(,,,有点绕口,,,但应该能get,,,?
然后就做完了,就是个cdq分治
但是这么想484有点复杂,,,?主要是实现起来想想它要实现哪些东西就jio得代码估计会比较长,就不想打嘛
那就再转化一下题意
把删去操作想成插入操作
那就是从后往前操作,每次会插入一些数,那这个数的贡献就是满足插入时间小于它且满足逆序对的数对的个数
这样就只要做一遍cdq就好了(其实核心思想是一样的,,,只是私信jio得这个方法的代码应该好打一些w
然后等下放代码QAQ!
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define rg register
#define gc getchar()
#define lowbit(x) (x&(-x))
#define rp(i,x,y) for(rg int i=x;i<=y;++i)
#define my(i,x,y) for(rg ll i=x;i>=y;--i)
const ll N=1e5+10;
struct ques{ll pos,tim,num,as;}q[N],t[N];
bool is_del[N];
ll n,m,sum,q_cnt,del[N],p[N],tr[N];
il ll read()
{
rg char ch=gc;rg int x=0;rg bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il void updat(ll x,ll y){while(x<=n)tr[x]+=y,x+=lowbit(x);}
il ll query(ll x){ll tmp=0;while(x)tmp+=tr[x],x-=lowbit(x);return tmp;}
il bool cmp(ques gd,ques gs){return gd.tim<gs.tim;}
il bool cmq(ques gd,ques gs){return gd.pos<gs.pos;}
il void solv(ll l,ll r)
{
if(l>=r)return;ll mid=(l+r)>>1,num=0;solv(l,mid);solv(mid+1,r);sort(q+l,q+r+1,cmq);
rp(i,l,r)if(q[i].tim<=mid)updat(q[i].num,1),++num;else q[i].as+=num-query(q[i].num);
rp(i,l,r)if(q[i].tim<=mid)updat(q[i].num,-1);
my(i,r,l)if(q[i].tim<=mid)updat(q[i].num,1);else q[i].as+=query(q[i].num);
rp(i,l,r)if(q[i].tim<=mid)updat(q[i].num,-1);
}
int main()
{
n=read();m=read();rp(i,1,n)p[read()]=i;rp(i,1,m)is_del[del[i]=read()]=1;rp(i,1,n)if(!is_del[i])q[++q_cnt]=(ques){p[i],q_cnt,i,0};
my(i,m,1)q[++q_cnt]=(ques){p[del[i]],q_cnt,del[i],0};
solv(1,n);sort(q+1,q+1+n,cmp);rp(i,1,n)q[i].as+=q[i-1].as;my(i,n,n-m+1)printf("%lld\n",q[i].as);
return 0;
}