链接:

题意:

给出一个长为的数列，以及个操作，操作涉及区间询问等于一个数的元素，并将这个区间的所有元素改为。

思路:

维护一个分块是否全部等于一个值,不等于时跑暴力即可.

查询一段时先把对应的分块更新再查询和更改.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#include <assert.h>

#include <iomanip>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int MAXN = 1e5+10;

const int MOD = 10007;

int a[MAXN], Tag[MAXN];

int Belong[MAXN];

int n, part, last;

void Reset(int pos)

{

    if (Tag[pos] == -1)

        return;

    for (int i = (pos-1)*part+1;i <= pos*part;i++)

        a[i] = Tag[pos];

    Tag[pos] = -1;

}

int Solve(int l, int r, int c)

{

    int cnt = 0;

    Reset(Belong[l]);

    for (int i = l;i <= min(Belong[l]*part, r);i++)

    {

        if (a[i] == c)

            cnt++;

        a[i] = c;

    }

    if (Belong[l] != Belong[r])

    {

        Reset(Belong[r]);

        for (int i = max((Belong[r]-1)*part+1, l);i <= r;i++)

        {

            if (a[i] == c)

                cnt++;

            a[i] = c;

        }

    }

    for (int i = Belong[l]+1;i <= Belong[r]-1;i++)

    {

        if (Tag[i] != -1)

        {

            if (Tag[i] == c)

                cnt += part;

            Tag[i] = c;

        }

        else

        {

            for (int j = (i-1)*part+1;j <= i*part;j++)

            {

                if (a[j] == c)

                    cnt++;

                a[j] = c;

            }

            Tag[i] = c;

        }

    }

    return cnt;

}

int main()

{

    scanf("%d", &n);

    part = sqrt(n);

    memset(Tag, -1, sizeof(Tag));

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

    {

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

        Belong[i] = (i-1)/part+1;

    }

    int op, l, r, c;

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

    {

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

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

    }

    return 0;

}

巴特西

LOJ-6284-数列分块入门8

链接:

题意:

思路:

代码:

最新文章

热门文章