本文共 2066 字，大约阅读时间需要 6 分钟。
这就是我声明中说的那道CDQ题目...
在经过一番重写之后,我A了.
至于题解,网上的题解写的都不错.
#include #include #include #include #include #include #include #include #include #include using namespace std;#define LL long long#define FILE "dealing"#define up(i,j,n) for(int i=j;i<=n;++i)#define db double#define ull unsigned long long#define eps 1e-10#define pii pair int read(){ int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f*x;}const int maxn=200010,maxm=20000,limit=1e6,inf=(int)(2e9),mod=(int)(7+1e9+0.1);template bool cmax(T& a,T b){return a bool cmin(T& a,T b){return a>b?a=b,true:false;}template T min(T& a,T& b){return a T max(T& a,T& b){return a>b?a:b;}int n,m;struct node{ int v,t,id; LL ans;}a[maxn],w[maxn];int id[maxn],c[maxn];int lowbit(int x){return x&-x;}int getsum(int x){ int ans=0; while(x){ ans+=c[x]; x-=lowbit(x); } return ans;}void add(int x,int d){ while(x<=n){ c[x]+=d; x+=lowbit(x); }}void init(){ n=read(),m=read();int top=n; up(i,1,n)a[i].v=read(),id[a[i].v]=i,a[i].id=i; up(i,1,m){ int v=read(); a[id[v]].t=top--; } up(i,1,n)if(!a[i].t)a[i].t=top--;}bool cmp3(node a,node b){return a.id >1; cdq(l,mid); cdq(mid+1,r); int pos1=l,pos2=mid+1; while(pos1<=mid||pos2<=r){ if((a[pos1].id <=mid)||pos2>r){ add(n-a[pos1].v+1,1); q[++top]=n-a[pos1].v+1; pos1++; continue; } if((a[pos1].id>a[pos2].id&&pos2<=r)||pos1>mid){ a[pos2].ans+=getsum(n-a[pos2].v+1); pos2++; } } while(top)add(q[top--],-1); pos1=mid,pos2=r; while(pos1>=l||pos2>=mid+1){ if((a[pos1].id>a[pos2].id&&pos1>=l)||(pos2 =mid+1)||(pos1 r){ w[++u]=a[pos1]; pos1++; continue; } if((a[pos1].id>a[pos2].id&&pos2<=r)||pos1>mid){ w[++u]=a[pos2]; pos2++; } } up(i,l,r)a[i]=w[i];}bool cmp(node a,node b){return a.t =n-m+1;i--)printf("%lld\n",ans[i]);}int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); init(); solve(); return 0;}
转载于:https://www.cnblogs.com/chadinblog/p/6539416.html