HDU 4638 Group(树状数组)

HDU 4638 Group(树状数组)

题意:给你一个n的排列,然后给你一个区间[L,R],问你区间中有多少个连续的段,比如1,2,3,5,4,6,9,10算2段,因为1,2,3,4,5,6可以组成1,2,3,4,5,6而9,10又是一段.

分析:

预处理:首先我们从第i数开始依次添加数进入排列中,我们添这个数进去可能发生3种结果:

1:减少一个段(因为a[i]-1和a[i]+1已经出现在a[i]之前了,添加a[i]进去等于合并了a[i]-1,a[i],a[i]+1),执行add(i,-1)操作

2:不变(此时只有a[i]-1或a[i]+1中的一个在a[i]之前出现).

3:增加一个段(此时a[i]-1和a[i]+1都还没有出现,a[i]是一个单独的段)

此时执行add(i,1)操作

执行完一遍从1到n的扫描后,我们如果要求任意[1,x]之间有多少段,只需要用sum(x)即可求得

现在我们要求的是[L,R]之间有多少段.现在我们知道[1,x]的段数就等于sum(x).我们从1到n依次处理a[i],且我们保证每次处理a[i]前,sum(R)的值就是[i,R]区间内所有段的数量,但是对于[L,R](其中L>i)内段的数量我们不管.处理完a[i]后,我们保证sum(R)的值就是[i+1,R]区间内所有段的数量.

比如在处理a[1]前,我们保证sum(R)是任意[1,R]区间内段的数量.

处理完a[1]可能的情况后,我们保证sum(R)是任意[2,R]区间内段的数量.

当处理a[i]的时候:(因为处理前sum(R)为[i,R]区间内段的数量)

情况一:如果a[i]+1和a[i]-1在a[i]前面的话,add(i,-1).换句话说,如果a[i]+1和a[i]-1在a[i]前面,那么sum(R)本来是[i,R]区间内段的数量,现在a[i]是孤立成段的,所以[i+1,R]内段的数量= [i,R]区间内段的数量-1,即只要执行了操作add(i,-1)之后,sum(R)就永久的从表示[i,R]的段,变成了表示[i+1,R]的段数量.

情况二:如果a[i]+1和a[i]-1在a[i]的后面的话,执行add(i,-1) add(pos[a[i]-1],1)  add(pos[a[i]+1],1)

情况三:如果a[i]+1(假设它在前)和a[i]-1一个在a[i]前面,一个在a[i]后面的话,那么add(i,-1), add(pos[a[i]-1],1)

以上就是分析,其中最重要的一点是体会到:我们保证每次处理a[i]前,sum(R)的值就是[i,R]区间内所有段的数量,但是对于[L,R](其中L>i)内段的数量我们不管.处理完a[i]后,我们保证sum(R)的值就是[i+1,R]区间内所有段的数量.

所以最终需要离线处理,把所有待处理的区间按L从小到大排序即可.

代码实现有个小细节,由于1和n是没有0和n+1的,所以我们认为的令pos[0]=pos[n+1]=n+10;这样既不会影响预处理,也不会影响后面求sum(R)

AC代码:453ms

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100000+100;
int c[MAXN];
int a[MAXN];
int pos[MAXN];
int ans[MAXN];
int lowbit(int x){return x&(-x);}
int sum(int x)
{
    int res=0;
    while(x)
    {
        res +=c[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)
{
    while(x<MAXN)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
struct node
{
    int l,r;
    int index;
    bool operator <(const node&b)const
    {
        return l<b.l;
    }
}nodes[MAXN];
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        pos[0]=pos[n+1]=n+10;//特殊处理,保证a[i]=1或n的时候可以也可以正常处理
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&nodes[i].l,&nodes[i].r);
            nodes[i].index = i;
        }
        sort(nodes+1,nodes+m+1);

        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)//这个循环结束后,sum(R)为[1,R]区间的段数
        {
            if(i>pos[a[i]-1] && i>pos[a[i]+1]) add(i,-1);
            else if(i<pos[a[i]-1] && i<pos[a[i]+1]) add(i,1);
        }

        int i=1;//i表当前处理a[i]
        int j=1;//j表当前第j条查询命令待处理
        while(j<=m)
        {
            while(nodes[j].l==i)
            {
                ans[ nodes[j].index ] = sum( nodes[j].r );
                j++;
            }
            if(i<=n)
            {
                if(i>pos[a[i]-1] && i>pos[a[i]+1])
                {
                    add(i,-1);
                }
                else if(i<pos[a[i]-1] && i<pos[a[i]+1])
                {
                    add(i,-1);
                    add(pos[a[i]-1],1);
                    add(pos[a[i]+1],1);
                }
                else if(i<pos[a[i]-1])
                {
                    add(i,-1);
                    add(pos[a[i]-1],1);
                }
                else if(i<pos[a[i]+1])
                {
                    add(i,-1);
                    add(pos[a[i]+1],1);
                }
                i++;
            }
        }
        for(int i=1;i<=m;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}