根據題目意思，很容易得出，一個區間里面連續的段數即為最少的group數。

題解上面給的是用樹狀數組維護的。

詢問一個區間的時候，可以一個一個的向里面添加，只需要判斷a[i]-1 和 a[i]+1是否已經添加在內，如果兩個都在，則總段數減1，如果兩個都不在，總段數加1，其他情況總段數不變了。這里有一個需要深入理解的就是其實無論是按順序添加還是隨便添加，統計結果是不變的，但是要看怎么維護了。

每加入一個點，都會有一個改變量v[i]，那么此時總段數就是sum{ v[i] } (1 <= i <= x) ,因此用樹狀數組維護前綴和即可。

樹狀數組實現：

?

    #include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 101000

bool vis[N];

int n, s[N], m, ans[N], a[N], p[N];

struct node {

    int l, r, id;

    bool operator<(const node &x) const {

        return r > x.r;

    }

} q[N];

inline int lowbit(int x) {

    return x&(-x);

}

void add(int x, int v) {

    while (x <= n) {

        s[x] += v;

        x += lowbit(x);

    }

}

int sum(int x) {

    int ret = 0;

    while (x) {

        ret += s[x];

        x -= lowbit(x);

    }

    return ret;

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) {

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

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

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

            p[a[i]] = i;

        }

        memset(s, 0, sizeof(s));

        memset(vis, false, sizeof(vis));

        for (int i=n; i>0; i--) {

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

            if (!vis[a[i]-1] && !vis[a[i]+1]) add(i, 1);

            vis[a[i]] = true;

        }



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

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

            q[i].id = i;

        }



        sort(q, q+m);

        int j = n;

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

            while (j > q[i].r) {

                if (a[j]>1 && p[a[j]-1] < j) add(p[a[j]-1], 1);

                if (a[j]<n && p[a[j]+1] < j) add(p[a[j]+1], 1);

                j--;

            }

            ans[q[i].id] = sum(q[i].r) - sum(q[i].l-1);

        }



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

    }



    return 0;

}


  

?

比賽時候，我用的分塊的思想，想到復雜度是O(n*sqrt(n))的，可能有點懸，結果TLE了，以為真的是卡時間了，其實是自己的代碼寫殘了（一個小細節害死人啊），調試了很長時間，直接用原題的大數據debug是要命啊?？偹阏业絙ug了。其實也是可以過的么……呵呵……數據水？

這 種解法和 CF 86D Powerful array ?的解法是一樣的。

?

    #include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define N 100100

bool vis[N];

int a[N], n, m, all, L, R, ans[N];



struct node {

    int l, r, b, id;

    bool operator<(const node &x)const{

        if (b == x.b) return r < x.r;

        return b < x.b;

    }

} q[N];



void query(int x, int y, int flag) {

    if (flag != 0) {

        for (int i=x; i<L; i++) {

            vis[a[i]] = true;

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

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

        }

        for (int i=R+1; i<=y; i++) {

            vis[a[i]] = true;

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

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

        }

        for (int i=L; i<x; i++) {

            vis[a[i]] = false;

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

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

        }

        for (int i=y+1; i<=R; i++) {

            vis[a[i]] = false;

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

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

        }

    } else {

        all = 0;

        for (int i=x; i<=y; i++) {

            vis[a[i]] = true;

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

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

        }

    }

    L = x, R = y;

}

int main() {

    int T;

    scanf("%d", &T);



    while (T--) {

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

        int block_size = 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].b = q[i].l / block_size;

            q[i].id = i;

        }

        sort(q, q+m);

        memset(vis, false, sizeof(vis));



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

            query(q[i].l, q[i].r, i);

            ans[q[i].id] = all;

        }

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

    }



    return 0;

}


  

?

?

HDU 4638 Group 【樹狀數組，分塊亂搞（莫隊算法？）】