HDU 4638 Groub 线段树离线，莫队，分块法

admin 管理员组

文章数量: 887021

题意：找到区间里有多少组连续数字串。
PS:由于网上关于这个题的解法非常多，不懂自己去看，我自己写了3种解法，主要比较效率。
解法1： 询问离线，右端点排序，树状数组(线段树维护)
//7876kb, 795ms, 1331kb

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int T, n, m, a[maxn], p[maxn], ans[maxn];
struct node{
    int l, r, id;
    node(){}
    node(int l, int r, int id) : l(l), r(r), id(id){}
    bool operator < (const node &rhs) const{
        return r < rhs.r;
    }
}q[maxn];

namespace BIT{
    int c[maxn];
    void init(){memset(c, 0, sizeof(c));}
    inline int lowbit(int x){return x&-x;}
    inline void add(int i, int v){for(; i<= n; i += lowbit(i)) c[i] += v;}
    inline query(int i){int res = 0; for(; i; i -= lowbit(i)) res += c[i]; return res;}
}

using namespace BIT;
int main(){
    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;
        }
        for(int i = 1; i <= m; i++){scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i;}
        sort(q + 1, q + m + 1);
        init();
        int j = 1;
        for(int i = 1; i <= n; i++){
            add(i, 1);
            if(a[i] > 1 && p[a[i] - 1] < i) add(p[a[i] - 1], -1);
            if(a[i] < n && p[a[i] + 1] < i) add(p[a[i] + 1], -1);
            while(j <= m && q[j].r == i){
                ans[q[j].id] = query(q[j].r) - query(q[j].l - 1); j++;
            }
        }
        for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    }
    return 0;
}

解法2：莫队 O(n^1.5)
//4944 kb, 1060ms, 1287b

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int T, n, m, a[maxn], pos[maxn], Ans[maxn], ans;

struct node{
    int l, r, id;
    node(){}
    node(int l, int r, int id) : l(l), r(r), id(id){}
}q[maxn];

bool vis[maxn];

bool cmp(node a, node b){
    if(pos[a.l] == pos[b.l]) return a.r < b.r;
    return pos[a.l] < pos[b.l];
}

void update(int x, int d){
    vis[x] = d;
    if(d) ans += 1 - vis[x + 1] - vis[x - 1];
    else ans += vis[x + 1] + vis[x - 1] - 1;
}

int main(){
    scanf("%d", &T); while(T--){
        scanf("%d%d", &n, &m);
        memset(vis, 0, sizeof(vis));
        int block = sqrt(n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]); pos[i] = (i - 1) / block;
        }
        for(int i = 1; i <= m; i++){scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i;}
        sort(q + 1, q + m + 1, cmp);
        int L = 1, R = 0; ans = 0;
        for(int i = 1; i <= m; i++){
            int id = q[i].id;
            while(R < q[i].r) R++, update(a[R], 1);
            while(R > q[i].r) update(a[R], 0), R--;
            while(L < q[i].l) update(a[L], 0), L++;
            while(L > q[i].l) L--, update(a[L], 1);
            Ans[id] = ans;
        }
        for(int i = 1; i <= m; i++) printf("%d\n", Ans[i]);
    }
    return 0;
}

解法3：分块 (话说这个分块真的不是莫队？？？毛啊，这就是瞎暴力吧？？？) O(n^1.5)
//951ms 920kb 2085b

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int T, n, m, L, R, a[maxn], Ans[maxn], ans;
bool vis[maxn];

struct node{
    int l, r, id, belong;
    node(){}
    node(int l, int r, int id, int belong) : l(l), r(r), id(id), belong(belong) {}
    bool operator < (const node &rhs) const{
        if(belong == rhs.belong) return r < rhs.r;
        return belong < rhs.belong;
    }
}q[maxn];

void query(int x, int y, int type){
    if(type == 1){
        ans = 0;
        for(int i = x; i <= y; i++){
            vis[a[i]] = 1;
            if(vis[a[i] - 1] && vis[a[i] + 1]) ans--;
            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) ans++;
        }
    }
    else{
        for(int i = x; i < L; i++){
            vis[a[i]] = 1;
            if(vis[a[i] - 1] && vis[a[i] + 1]) ans--;
            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) ans++;
        }
        for(int i = R + 1; i <= y; i++){
            vis[a[i]] = 1;
            if(vis[a[i] - 1] && vis[a[i] + 1]) ans--;
            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) ans++;
        }
        for(int i = L; i < x; i++){
            vis[a[i]] = 0;
            if(vis[a[i] - 1] && vis[a[i] + 1]) ans++;
            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) ans--;
        }
        for(int i = y + 1; i <= R; i++){
            vis[a[i]] = 0;
            if(vis[a[i] - 1] && vis[a[i] + 1]) ans++;
            else if(!vis[a[i] - 1] && !vis[a[i] + 1]) ans--;
        }
    }
    L = x, R = y;
}

int main(){
    scanf("%d", &T); while(T--){
        scanf("%d%d", &n, &m);
        int block = sqrt(n);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i = 1; i <= m; i++){
            scanf("%d%d", &q[i].l, &q[i].r); q[i].belong = q[i].l / block; q[i].id = i;
        }
        sort(q + 1, q + m + 1);
        memset(vis, 0, sizeof(vis));
        ans = 0;
        for(int i = 1; i <= m; i++){
            query(q[i].l, q[i].r, i);
            Ans[q[i].id] = ans;
        }
        for(int i = 1; i <= m; i++){
            printf("%d\n", Ans[i]);
        }
    }
    return 0;
}

本文标签： 离线 线段 HDU 莫队 Groub