洛谷 P1975 [国家集训队]排队 Lebal:块内排序+树状数组

题目描述

排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。

红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足i<j且hi>hj的(i,j)数量。

幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。

输入输出格式

输入格式：

第一行为一个正整数n，表示小朋友的数量；

第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；

第三行为一个正整数m，表示交换操作的次数；

以下m行每行包含两个正整数ai和bi，表示交换位置ai与位置bi的小朋友。

输出格式：

输出文件共m+1行，第i行一个正整数表示交换操作i结束后，序列的杂乱程度。

输入输出样例

输入样例#1： 复制

3

130 150 140

2

2 3

1 3

输出样例#1： 复制

说明

【样例说明】

未进行任何操作时，(2,3)满足条件；

操作1结束后，序列为130 140 150，不存在满足i<j且hi>hj的(i,j)对；

操作2结束后，序列为150 140 130,(1,2)，(1,3)，(2,3)共3对满足条件的(i,j)。

对于15%的数据， n,m \le 15n,m≤15 ；

对于30%的数据， n,m \le 200n,m≤200 ；

在剩下的70%数据中：

存在15%的数据， h_ihi 各不相同；

存在15%的数据， 1^{10} \le h_i \le 1^{60}110≤hi≤160 ；

以上两类数据不存在交集。

对于100%的数据， 1 \le m \le 2\times 10^31≤m≤2×103 ， 1 \le n \le 2 \times 10^41≤n≤2×104 ， 1 \le h_i \le 10^91≤hi≤109 ， a_i \ne b_iai≠bi ， 1 \le a_i,b_i \le n1≤ai,bi≤n。

代码

直接暴力分块，然后在每一个块内排序。

查询时可以在每一个块内二分。

#include <cmath>

#include <cstdio>

#include <iostream>

#include <algorithm>

#define M 210

#define N 20101

using namespace std;

int n, m, t, S, C, ans;

int a[N], b[N], c[N], st[M], ed[M], belong[N], sorted[M][M], len[M];

inline int read()

{

    int x = 0, f = 1;

    char ch = getchar();

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

    for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

    return x * f;

}

inline int query(int x)

{

    int ret = 0;

    for(; x; x -= x & -x) ret += c[x];

    return ret;

}

inline void add(int x)

{

    for(; x <= m; x += x & -x) c[x]++;

}

inline void init()

{

    int i, j;

    S = sqrt(n);

    for(i = 1; i <= n; i += S)

    {

        st[++C] = i;

        ed[C] = min(i + S - 1, n);

        len[C] = ed[C] - st[C] + 1;

    }

    for(i = 1; i <= C; i++)

    {

        for(j = st[i]; j <= ed[i]; j++)

            belong[j] = i, sorted[i][j - st[i] + 1] = a[j];

        sort(sorted[i] + 1, sorted[i] + len[i] + 1);

    }

}

inline void solve(int x, int y)

{

    if(x > y) swap(x, y);

    int i, l = belong[x], r = belong[y], tmp;

    if(l == r)

        for(i = x + 1; i < y; i++)

        {

            ans -= (a[i] < a[x]);

            ans += (a[i] > a[x]);

            ans -= (a[i] > a[y]);

            ans += (a[i] < a[y]);

        }

    else

    {

        for(i = l + 1; i < r; i++)

        {

            ans -= lower_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[x]) - sorted[i] - 1;

            ans += len[i] - (upper_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[x]) - sorted[i]) + 1;

            ans -= len[i] - (upper_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[y]) - sorted[i]) + 1;

            ans += lower_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[y]) - sorted[i] - 1;

        }

        for(i = x + 1; i <= ed[l]; i++)

        {

            ans -= (a[i] < a[x]);

            ans += (a[i] > a[x]);

            ans -= (a[i] > a[y]);

            ans += (a[i] < a[y]);

        }

        for(i = st[r]; i < y; i++)

        {

            ans -= (a[i] < a[x]);

            ans += (a[i] > a[x]);

            ans -= (a[i] > a[y]);

            ans += (a[i] < a[y]);

        }

    }

    if(a[x] > a[y]) ans--;

    if(a[x] < a[y]) ans++;

    swap(a[x], a[y]);

    for(i = st[l]; i <= ed[l]; i++) sorted[l][i - st[l] + 1] = a[i];

    for(i = st[r]; i <= ed[r]; i++) sorted[r][i - st[r] + 1] = a[i];

    sort(sorted[l] + 1, sorted[l] + len[l] + 1);

    sort(sorted[r] + 1, sorted[r] + len[r] + 1);

}

int main()

{

    int i, x, y;

    n = read();

    for(i = 1; i <= n; i++) a[i] = b[i] = read();

    sort(b + 1, b + n + 1);

    m = unique(b + 1, b + n + 1) - b - 1;

    for(i = 1; i <= n; i++)

    {

        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;

        ans += i - query(a[i]) - 1, add(a[i]);

    }

    printf("%d\n", ans);

    init();

    t = read();

    while(t--)

    {

        x = read();

        y = read();

        solve(x, y);

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

洛谷 P1975 [国家集训队]排队 Lebal:块内排序+树状数组

题目描述

输入输出格式

输入输出样例

说明

代码

最新文章

热门文章