hdu 4638 Group 樹狀數組

題意：

給你一個1~n的排列，問區間[l, r] 之間有多少段連續的數，比如排列5 1 3 2 4，詢問[1, 3]結果為3，詢問[2, 4]結果為1

這題也是挺不錯的。解題思路:

首先應該想到要對所有詢問離線處理，先預處理好[1, i]的結果，對所有詢問按照L從小到大排個序，然後講左邊一個點一個點删除，每删除一個點，必然對後面的結果産生影響，假設要删除的點的初始值為x，如果x-1和x+1在後面，可以很容易知道删除x并不會對x-1和x+1之間的詢問值造成影響，而對于左邊的應該是少了1，對于後邊的多了1。

如果x-1和x+1都在x左邊，那x就沒有相鄰的數在右邊了，那原來的情況x就算是一個連續塊了，那麼删除x後，右邊的詢問值應該全部少了1。

如果x-1和x+1有一個在右邊，那麼對于這個位置的右邊是不影響的，左邊都少了1。

具體見代碼。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define lowbit(x) ((x)&(-x))

const int maxn = 100005;
struct PP{
    int l , r, id;
    bool operator < (const PP &a) const {
        return l < a.l;
    }
}q[maxn];

int n, a[maxn], d[maxn], node[maxn], pos[maxn], print[maxn];
bool vis[maxn];

void add(int x, int val) {
    while(x <= n) {
        node[x] += val;
        x += lowbit(x);
    }
}

int get_sum(int x) {
    int ret = 0;
    while(x > 0) {
        ret += node[x];
        x -= lowbit(x);
    }
    return ret;
}

int main() {
    int i, t, m;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        vis[0] = vis[n+1] = 0;
        for(i = 1;i <= n; i++) {
            scanf("%d", &a[i]);
            vis[i] = node[i] = 0;
            pos[a[i]] = i;
        }
        d[1] = 1;
        vis[a[1]] = 1;
        for(i = 2;i <= n; i++) {
            d[i] = d[i-1];
            if(vis[a[i]-1] && vis[a[i]+1])  d[i] --;
            else if(!vis[a[i]-1] && !vis[a[i]+1])   d[i]++;
            vis[a[i]] = 1;
        }
    //    for(i = 1;i <= n ;i++)  printf("%d ", d[i]);    puts("");
        for(i = 1;i <= n ;i++) {
            add(i, d[i]);
            add(i+1, -d[i]);
        }
        for(i = 0;i < m; i++)
            scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
        sort(q, q+m);
        int cur = 1;
        for(i = 0;i < m; i++) {
            while(cur < q[i].l) {
                int now = a[cur];
                if(pos[now-1] > cur && pos[now+1] > cur) {
                    int mx = max(pos[now-1], pos[now+1]);
                    int mi = min(pos[now-1], pos[now+1]);
                    add(cur, -1);
                    add(mi, 1);
                    add(mx, 1);
                }
                else {
                    int mx = max(pos[now-1], pos[now+1]);
                    if(mx > cur) {
                        add(cur+1, -1);
                        add(mx, 1);
                    }
                    else

                        add(cur+1, -1);
                }
                cur++;
            }
            print[q[i].id] = get_sum(q[i].r);
        }
        for(i = 0;i < m; i++)
            printf("%d\n", print[i]);
    }
    return 0;
}