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;
}