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

补充：软件开发 , C++ ,

上一个：HDU 2196 树形DP Computer
下一个：hdu1072 Nightmare (BFS)