noip模拟赛数颜色

分析：高级数据结构学傻了.....一眼看上去觉得是莫队，发现带修改，于是分块，由于写的常数很大，只有70分.

正解很简单，记录下颜色为c的每只兔子的位置，每次二分找这个区间有多少只这种颜色的兔子就可以了，交换操作就交换位置，颜色.可能会存不下，所以用vector.

70分分块：

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, a[][], b[], block, l[], r[], pos[], cnt, vis[];

bool flag = true;

void update(int cur)

{

    int t = b[cur], t2 = b[cur + ];

    swap(b[cur], b[cur + ]);

    int p1 = pos[cur], p2 = pos[cur + ];

    a[p1][t]--;

    a[p2][t]++;

    a[p1][t2]++;

    a[p2][t2]--;

}

int query(int ll, int rr, int c)

{

    int L = pos[ll], R = pos[rr], res = ;

    if (L >= R - )

    {

        for (int i = ll; i <= rr; i++)

            if (b[i] == c)

                res++;

        return res;

    }

    for (int i = L + ; i <= R - ; i++)

        res += a[i][c];

    for (int i = ll; i <= r[L]; i++)

        if (b[i] == c)

            res++;

    for (int i = l[R]; i <= rr; i++)

        if (b[i] == c)

            res++;

    return res;

}

int main()

{

    scanf("%d%d", &n, &m);

    block = sqrt(n);

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

        pos[i] = (i - ) / block + ;

    cnt = (n - ) / block + ;

    for (int i = ; i <= cnt; i++)

        l[i] = r[i - ] + , r[i] = min(block * i, n);

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

    {

        int t;

        scanf("%d", &t);

        a[pos[i]][t]++;

        b[i] = t;

    }

        while (m--)

        {

            int op, l, r, c;

            scanf("%d", &op);

            if (op == )

            {

                scanf("%d%d%d", &l, &r, &c);

                printf("%d\n", query(l, r, c));

            }

            else

            {

                scanf("%d", &c);

                update(c);

            }

        }

    return ;

}

正解：

#include <cmath>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = ;

int n, m, a[maxn];

vector <int>b[maxn];

int main()

{

    scanf("%d%d", &n, &m);

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

    {

        scanf("%d", &a[i]);

        b[a[i]].push_back(i);

    }

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

        sort(b[i].begin(), b[i].end());

    while (m--)

    {

        int op, l, r, c;

        scanf("%d", &op);

        if (op == )

        {

            scanf("%d%d%d", &l, &r, &c);

            printf("%d\n", (int)(upper_bound(b[c].begin(), b[c].end(), r) - lower_bound(b[c].begin(), b[c].end(), l)));

        }

        else

        {

            scanf("%d", &c);

            if (a[c] != a[c + ])

            {

                (*lower_bound(b[a[c]].begin(), b[a[c]].end(), c))++;

                (*lower_bound(b[a[c + ]].begin(), b[a[c + ]].end(), c + ))--;

                swap(a[c], a[c + ]);

            }

        }

    }

    return ;

}

巴特西

noip模拟赛数颜色

最新文章

热门文章

巴特西

noip模拟赛 数颜色

最新文章

热门文章

noip模拟赛数颜色