hdu4638

题意

给定一个序列，序列由1-N个元素全排列而成，求任意区间可组成的连续的段数，比如[1,2,4]两段{[1,2],[4]}，[1,2,4,3]一段{[1,2,3,4]}。

对于查询的区间询问的是可组成的连续的数的段数最小值。

分析

分块排好序，O(1)的维护就是每新添加一个元素 t 查看 t-1 与 t+1 是否都在区间内，如是则段数-1，如果都不在，则段数+1。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 1e5 + 10;

int a[MAXN];

int vis[MAXN];

int ans[MAXN];

struct node

{

    int l, r, bid, id;

    bool operator < (const node &other) const

    {

        if(bid == other.bid) return r < other.r;

        return bid < other.bid;

    }

}q[MAXN];

int L, R, res;

void query(int l, int r, int is)

{

    if(is)

    {

        for(int i = l; i < L; i++)

        {

            if(vis[a[i] - 1] && vis[a[i] + 1]) res--;

            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) res++;

            vis[a[i]] = 1;

        }

        for(int i = R + 1; i <= r; i++)

        {

            if(vis[a[i] - 1] && vis[a[i] + 1]) res--;

            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) res++;

            vis[a[i]] = 1;

        }

        for(int i = L; i < l; i++)

        {

            if(vis[a[i] - 1] && vis[a[i] + 1]) res++;

            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) res--;

            vis[a[i]] = 0;

        }

        for(int i = r + 1; i <= R; i++)

        {

            if(vis[a[i] - 1] && vis[a[i] + 1]) res++;

            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) res--;

            vis[a[i]] = 0;

        }

    }

    else

    {

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

        {

            if(vis[a[i] - 1] && vis[a[i] + 1]) res--;

            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) res++;

            vis[a[i]] = 1;

        }

    }

    L = l; R = r;

    ans[q[is].id] = res;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int n, m;

        memset(vis, 0, sizeof vis);

        res = 0;

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

        int bsize = sqrt(n);

        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

        for(int i = 0; i < m; i++)

        {

            scanf("%d%d", &q[i].l, &q[i].r);

            q[i].id = i;

            q[i].bid = q[i].l / bsize;

        }

        sort(q, q + m);

        for(int i = 0; i < m; i++) query(q[i].l, q[i].r, i);

        for(int i = 0; i < m; i++) printf("%d\n", ans[i]);

    }

    return 0;

}

巴特西

hdu4638

hdu4638

题意

分析

code

最新文章

热门文章