[bzoj 3295] [Cqoi 2011] 동적 역순 트 리 배열 주석 트 리

Description
시퀀스 A 에 대한 역순 대 수 는 만족 i 로 정의 합 니 다.
Input
첫 줄 에 두 개의 정수 n 과 m, 즉 초기 요소 의 개수 와 삭 제 된 요소 의 개 수 를 입력 하 십시오.다음 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
Source
고전 문제...
한 개 씩 삭제 할 때마다 그것 의 앞 이 그 보다 큰 뒤 가 그 보다 작은 공헌 을 줄인다.
이 는... 의장 트 리 자체 기능 을 잘 실현 합 니 다...............................................
주의해 야 할 것 은 이 문 제 는 아버지 께 서 매번 수정 할 때마다 지속 가능 한 방법 으로 삽입 하신 다 는 것 입 니 다. 즉, 새 노드 를 만 들 면 공간 적 으로 감당 할 수 없습니다. 현재 노드 의 역사 버 전 을 방문 하지 않 기 때문에 공간 을 절약 하기 위해 매번 새로 만 들 지 마 세 요. 의장 트 리 의 공간 수요 가 너무 무 섭 습 니 다.

#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int INF = 1000000010;
const int SZ = 100010;

int n,m;

int num[SZ];

namespace first{
    int tmp[SZ];
    int a[SZ];
    LL ans = 0;

    void mergesort(int l,int r)
    {
        if(l == r) return ;
        int mid = (l + r) >> 1;
        mergesort(l,mid);   mergesort(mid + 1,r);
        int pl = l,pr = mid + 1,p = l;
        while(pl <= mid || pr <= r)
        {
            if(pr > r || (pl <= mid && a[pl] <= a[pr]))
                tmp[p ++] = a[pl ++];
            else
                tmp[p ++] = a[pr ++],ans += mid - pl + 1;
        }
        for(int i = l;i <= r;i ++)
            a[i] = tmp[i];
    }

    LL get_ans()
    {
        for(int i = 1;i <= n;i ++)
            a[i] = num[i];
        mergesort(1,n);
        return ans;
    }
}

int pos[SZ];

struct segment{
    int l,r;
    int cnt;
}tree[10000000];

int Tcnt = 0;

int rt[SZ];


void insert(int l,int r,int last,int &now,int x,int d)
{
    if(!now) now = ++ Tcnt;
    tree[now] = tree[last];
    tree[now].cnt += d;
    if(l == r) return ;
    int mid = l + r >> 1;
    if(x <= mid) insert(l,mid,tree[last].l,tree[now].l,x,d);
    else insert(mid + 1,r,tree[last].r,tree[now].r,x,d);
}

void change(int pos,int x,int d)
{
    for(int i = pos;i <= n;i += i & -i)
        insert(1,n,rt[i],rt[i],x,d);
}

int tl,tr;
int tml[SZ],tmr[SZ];

int query_min(int l,int r,int x)
{
    int L = 1,R = n;
    int ans = 0;
    while(L != R)
    {
        int mid = (L + R) >> 1;
        if(mid + 1 <= x)
        {
            int suml = 0,sumr = 0;
            for(int i = 1;i <= tl;i ++)  suml += tree[tree[tml[i]].l].cnt;
            for(int i = 1;i <= tr;i ++)  sumr += tree[tree[tmr[i]].l].cnt;
            ans += sumr - suml;
            for(int i = 1;i <= tl;i ++)  tml[i] = tree[tml[i]].r;
            for(int i = 1;i <= tr;i ++)  tmr[i] = tree[tmr[i]].r;
            L = mid + 1;
        }
        else
        {
            for(int i = 1;i <= tl;i ++)  tml[i] = tree[tml[i]].l;
            for(int i = 1;i <= tr;i ++)  tmr[i] = tree[tmr[i]].l;
            R = mid;            
        }
    }
    return ans;
}

int query_max(int l,int r,int x)
{
    int L = 1,R = n;
    int ans = 0;
    while(L != R)
    {
        int mid = (L + R) >> 1;
        if(mid >= x)
        {
            int suml = 0,sumr = 0;
            for(int i = 1;i <= tl;i ++)  suml += tree[tree[tml[i]].r].cnt;
            for(int i = 1;i <= tr;i ++)  sumr += tree[tree[tmr[i]].r].cnt;
            ans += sumr - suml;
            for(int i = 1;i <= tl;i ++)  tml[i] = tree[tml[i]].l;
            for(int i = 1;i <= tr;i ++)  tmr[i] = tree[tmr[i]].l;
            R = mid;
        }
        else
        {
            for(int i = 1;i <= tl;i ++)  tml[i] = tree[tml[i]].r;
            for(int i = 1;i <= tr;i ++)  tmr[i] = tree[tmr[i]].r;
            L = mid + 1;            
        }
    }
    return ans;
}


int ask_min(int l,int r,int x)
{
    tl = 0; tr = 0;
    l --;
    for(int i = l;i > 0;i -= i & -i)
        tml[++ tl] = rt[i];
    for(int i = r;i > 0;i -= i & -i)
        tmr[++ tr] = rt[i];
    return query_min(l,r,x);
}

int ask_max(int l,int r,int x)
{
    tl = 0; tr = 0;
    l --;
    for(int i = l;i > 0;i -= i & -i)
        tml[++ tl] = rt[i];
    for(int i = r;i > 0;i -= i & -i)
        tmr[++ tr] = rt[i];
    return query_max(l,r,x);
}

void scanf(int &n)
{
    n = 0;
    char a = getchar();
    bool flag = 0;
    while(a < '0'|| a > '9') { if(a == '-') flag = 1; a = getchar(); }
    while('0' <= a && a <= '9') { n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
}

int main()
{
    scanf(n); scanf(m);
    for(int i = 1;i <= n;i ++)
    {
        scanf(num[i]);
        pos[num[i]] = i;
        change(i,num[i],1);
    }
    LL ans = first :: get_ans();
    for(int i = 1;i <= m;i ++)
    {
        printf("%lld
",ans);
        int x;
        scanf(x);
        change(pos[x],x,-1);
        int tmp1 = ask_min(pos[x] + 1,n,x),tmp2 = ask_max(1,pos[x] - 1,x);
        ans -= tmp1 + tmp2;
    }
    return 0;
}