天天艹综合,午夜男人在线观看,日本一道aⅴ不卡免费播放

bzoj3295 [Cqoi2011]動態(tài)逆序?qū)?/h1>

2019-11-10 20:26:25

字體：大中小

供稿：網(wǎng)友

Description

對于序列A，它的逆序?qū)?shù)定義為滿足i<j，且A_i>A_j的數(shù)對(i,j)的個數(shù)。給1到n的一個排列，按照某種順序依次刪除m個元素，你的任務(wù)是在每次刪除一個元素之前統(tǒng)計整個序列的逆序?qū)?shù)。

Input

輸入第一行包含兩個整數(shù)n和m，即初始元素的個數(shù)和刪除的元素個數(shù)。以下n行每行包含一個1到n之間的正整數(shù)，即初始排列。以下m行每行一個正整數(shù)，依次為每次刪除的元素。

Output

輸出包含m行，依次為刪除每個元素之前，逆序?qū)Φ膫€數(shù)。

Sample Input

5 4153425142

Sample Output

5221樣例解釋(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

正解：CDQ分治。

這題用來考試，一堆50分暴力，一人寫出正解但是沒開long long。。

考慮把刪除變成插入，那么每次插入是按照時間排序的。那么只要滿足i<j，ai>aj，ti<tj，那么這就是一個逆序?qū)?。于是這題就變成裸的三維偏序了。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1<<30)#define il inline#define RG register#define ll long long#define lb(x) (x & -x)#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;struct node{ int x,y,t; }q[100010],qu[100010];ll c[100010],ans[100010],Ans;int match[100010],n,m;il int gi(){    RG int x=0,q=0; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q ? -x : x;}il int cmp(const node &a,const node &b){ return a.x<b.x || (a.x==b.x && a.y<b.y) || (a.x==b.x && a.y==b.y && a.t<b.t); }il void add(RG int x,RG int v){ for (RG int i=x;i<=n;i+=lb(i)) c[i]+=(ll)v; return; }il ll query(RG int x){ RG ll res=0; for (RG int i=x;i;i-=lb(i)) res+=c[i]; return res; }il void solve(RG int l,RG int r){    if (l>=r) return; RG int mid=(l+r)>>1,t1=l-1,t2=mid;    for (RG int i=l;i<=r;++i) if (q[i].t<=mid) add(q[i].y,1); else ans[q[i].t]+=query(n)-query(q[i].y);    for (RG int i=l;i<=r;++i) if (q[i].t<=mid) add(q[i].y,-1);    for (RG int i=r;i>=l;--i) if (q[i].t<=mid) add(q[i].y,1); else ans[q[i].t]+=query(q[i].y);    for (RG int i=r;i>=l;--i) if (q[i].t<=mid) add(q[i].y,-1);    for (RG int i=l;i<=r;++i) if (q[i].t<=mid) qu[++t1]=q[i]; else qu[++t2]=q[i];    for (RG int i=l;i<=r;++i) q[i]=qu[i]; solve(l,mid),solve(mid+1,r); return;}il void work(){    n=gi(),m=gi(); for (RG int i=1;i<=n;++i) q[i].x=i,q[i].y=gi(),match[q[i].y]=i; RG int ti=n,v;    for (RG int i=1;i<=m;++i) v=gi(),q[match[v]].t=ti--; for (RG int i=1;i<=n;++i) if (!q[i].t) q[i].t=ti--;    sort(q+1,q+n+1,cmp); solve(1,n); for (RG int i=1;i<=n;++i) Ans+=ans[i];    for (RG int i=n;i>n-m;--i){ PRintf("%lld/n",Ans); Ans-=ans[i]; } return;}int main(){    File("dynamic");    work();    return 0;}

上一篇：程序或-內(nèi)存區(qū)域分配（五個段）

下一篇：機(jī)器學(xué)習(xí)基礎(chǔ)—— 模擬退火（Simulated Annealing）