[Solution][DataStructure][分块法]CQOI2011 动态逆序对

【题目】

戳这里

【题意】

给定一个1~n的排列,并进行m次删除,每次删除一个数。试回答每次删除之前序列中的逆序对总数。

【思路】

树套树无力~~~果断膜拜题解分块水过。

将长度为n的原序列分为块,每块的大小为,并对每一块预先排序。

首先对原序列进行归并排序求出逆序对总数,时间复杂度.

对于删除的一个数,考虑其对整个序列的影响。

在这个数所在的块之前的块,需要减去这些块中比这个数大的数数目。同理,对于之后的块,需要减去这些块中比这个数小的数的数目。这些显然不能暴力处理,由于块内的有序性,所以二分查找。对于本块内的影响,直接暴力扫描。

对于单次更新答案复杂度:

注意:由于此时的块是被排过序的,所以需要记录一下原序列中每个数的位置,而不能直接在块内按照排序后位置计算答案。

一个数的删除更为简单,直接在块内二分位置+暴力删除即可。单次删除复杂度

总的时间复杂度:

【代码】

/**************************************************************
    Problem: 3295
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:4868 ms
    Memory:3172 kb
****************************************************************/

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define N (100050)
using namespace std;
int save[N] , t[N];
long long tot;
inline void Mergesort(int d[] , int l , int r)
{
    static int copy[N];
    if (l >= r)
        return;
    int mid = (l + r) >> 1;
    Mergesort(d , l ,mid);
    Mergesort(d , mid + 1 , r);
    int i = l , j = mid + 1 , k = l;
    while(i <= mid && j <= r)
    {
        if (d[i] <= d[j])
            copy[k++] = d[i++];
        else
        {
            tot += (mid - i + 1);
            copy[k++] = d[j++];
        }
    }
    while(i <= mid)
        copy[k++] = d[i++];
    while(j <= r)
        copy[k++] = d[j++];
    memcpy(d + l ,copy + l , (r - l + 1) * sizeof(int));
}
struct Block
{
    int d[320] , size;
    int lower_bound(int x)
    {
        int L = 1 , R = size + 1 , mid;
        while(L < R)
        {
            mid = (L + R) >> 1;
            if (d[mid] >= x)
                R = mid;
            else
                L = mid + 1;
        }
        return L;
    }
    int upper_bound(int x)
    {
        int L = 1 , R = size + 1 , mid;
        while(L < R)
        {
            mid = (L + R) >> 1;
            if (d[mid] > x)
                R = mid;
            else
                L = mid + 1;
        }
        return L;
    }
    void del(int x)
    {
        int ins = lower_bound(x);
        for(; ins < size ; ++ins)
            d[ins] = d[ins + 1];
        --size;
    }
}S[320];
int num , belong[N] , pos[N];
int calc(int x)
{
    int ret = 0 , k = belong[pos[x]];
    register int i;
    for(i = 1 ; i < k ; ++i)
        ret += S[i].size - S[i].lower_bound(x) + 1;
    for(i = k + 1 ; i <= num ; ++i)
        ret += S[i].lower_bound(x) - 1;
    for(i = 1 ; i <= S[k].size ; ++i)
    {
        if (S[k].d[i] < x && pos[S[k].d[i]] > pos[x])
            ++ret;
        if (S[k].d[i] > x && pos[S[k].d[i]] < pos[x])
            ++ret;
    }
    return ret;
}
int main()
{
    //freopen("tt.in" , "r" , stdin);
    int n , m;
    scanf("%d%d" , &n , &m);
    register int i;
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%d" , &save[i]) , t[i] = save[i];
        pos[save[i]] = i;
    }
    Mergesort(t , 1 , n);
    int per_size = int(sqrt(n) + 0.5);
    num = 1;
    for(i = 1  ; i <= n ; ++i)
    {
        S[num].d[++S[num].size] = save[i];
        belong[i] = num;
        if (S[num].size >= per_size)
            ++num;
    }
    for(i = 1 ; i <= num ; ++i)
        sort(S[i].d + 1 , S[i].d + S[i].size + 1);
    int x;
    while(m--)
    {
        printf("%lld\n" , tot);
        scanf("%d" , &x);
        tot -= calc(x);
        S[belong[pos[x]]].del(x);
    }
    return 0;
}
comments powered by Disqus