HDU 4638 多校第四場1007 離線詢問，樹狀數組||線段樹維護

這道題其實和前面機場出的樹狀數組和線段數題都差不多。

目測現在出這種離線處理，樹狀數組維護的題好多啊。

題意：給出一個序列，然後問，一個區間內，最多有多少人個GROUP，如果兩個人的id是連續的，那麼他們就是一個GROUP的，這個GROUP可以有很多人。

思路：其實跟前幾場的題有點像，我們先將所有的數都插入，存在線段樹裡面，那麼每次插入時候的值假設是在pos這位，那麼我們插入的值其實是根據pos + 1 ,pos - 1來確定的，如果這兩位都已經有數了，那麼這個pos插進去會是的pos - 1 , pos , pos + 1 ，連成一個GROUP,比單獨pos - 1 ,pos + 1 的時候GROUP少了一個，所以此時pos這位的值要減1。同理，如果pos - 1 ,pos + 1都沒插入，那麼pos插入GROUP就會+1。

然後每次離線詢問的時候，從前往後掃，區間求和就可以了。

這裡我用了樹狀數組和線段樹兩種方法實現，對於這道題，其實樹狀數組是占優勢的，因為是單點更新區間求和。

當然線段樹我寫的比較熟，所以也換了個姿勢來了一發。

線段樹CODE：

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 2505  
#define inf 1<<28  
#define LL(x) ( x << 1 )  
#define RR(x) ( x << 1 | 1 )  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define PII pair<int,int>  
using namespace std; 
 
 
inline void RD(int &ret) { 
    char c; 
    do { 
        c = getchar(); 
    } while(c < '0' || c > '9') ; 
    ret = c - '0'; 
    while((c=getchar()) >= '0' && c <= '9') 
        ret = ret * 10 + ( c - '0' ); 
} 
#define N 300005  
#define NN 100005  
int L[N] , R[N] , val[N] ,M[N] ; 
int d[NN] ; 
int is[NN] ,a[NN] ; 
int pos[NN] ; 
int ans[NN] ; 
void init(){ 
    mem(d, 0) ; 
    mem(is ,0) ; 
} 
struct kdq{ 
    int s , e , id ; 
}Q[N] ; 
void push_up(int u){ 
    val[u] = val[LL(u)] + val[RR(u)] ; 
} 
void build(int l ,int r ,int u){ 
    L[u] = l ; 
    R[u] = r ; 
    if(l == r){ 
        val[u] = d[l] ; 
        return ; 
    } 
    M[u] = l + r >> 1 ; 
    build(l , M[u] , LL(u)) ; 
    build(M[u] + 1 , r ,RR(u)) ; 
    push_up(u) ; 
} 
 
void update(int l , int u , int num){ 
    if(L[u] == l && R[u] == l){ 
        val[u] += num ; 
        return ; 
    } 
    if(l <= M[u])update(l ,LL(u) ,num) ; 
    else update(l, RR(u) , num) ; 
    push_up(u) ; 
} 
int query(int l ,int r ,int u){ 
    if(L[u] == l && R[u] == r){ 
        return val[u] ; 
    } 
    if(r <= M[u])return query(l ,r ,LL(u)) ; 
    else if(l > M[u])return query(l , r, RR(u)) ; 
    else return (query(l ,M[u] , LL(u)) + query(M[u] + 1 , r ,RR(u))); 
} 
bool cmp(const kdq& a ,const kdq&b){ 
    return a.s < b.s ; 
} 
int main() { 
    int T ; 
    cin >> T ; 
    while(T -- ){ 
        int n , m ; 
        cin >> n >> m ; 
        init() ; 
        for (int i = 1 ; i <= n ; i ++ ){ 
            RD(a[i]) ; 
            pos[a[i]] = i ; 
        } 
        for (int i = 0 ; i < m ; i ++ ){ 
            RD(Q[i].s) ; 
            RD(Q[i].e) ; 
            Q[i].id = i ; 
        } 
        for (int i = 1 ; i <= n ; i ++ ){ 
            int nn = 0 ; 
            if(is[a[i] + 1]) nn ++ ; 
            if(is[a[i] - 1]) nn ++ ; 
            if(nn == 2)d[i] -- ; 
            else if(nn == 0)d[i] ++ ; 
            is[a[i]] = 1 ; 
        } 
        build(1 , n , 1) ; 
        sort(Q , Q + m ,cmp) ; 
        int st = 1 ; 
        for (int i = 0 ; i < m ; i ++ ){ 
            while(Q[i].s > st){ 
                if(pos[a[st] + 1] > st && a[st] < n){ 
                    update(pos[a[st] + 1] ,1 , 1) ; 
                } 
                if(pos[a[st] - 1] > st && a[st] > 1){ 
                    update(pos[a[st] - 1] , 1, 1) ; 
                } 
                st ++ ; 
            } 
            ans[Q[i].id] = query(Q[i].s ,Q[i].e , 1) ; 
        } 
        for (int i = 0 ; i < m ; i ++ ){ 
            printf("%d\n",ans[i]) ; 
        } 
    } 
    return 0 ; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;


inline void RD(int &ret) {
    char c;
    do {
        c = getchar();
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
#define N 300005
#define NN 100005
int L[N] , R[N] , val[N] ,M[N] ;
int d[NN] ;
int is[NN] ,a[NN] ;
int pos[NN] ;
int ans[NN] ;
void init(){
    mem(d, 0) ;
    mem(is ,0) ;
}
struct kdq{
    int s , e , id ;
}Q[N] ;
void push_up(int u){
    val[u] = val[LL(u)] + val[RR(u)] ;
}
void build(int l ,int r ,int u){
    L[u] = l ;
    R[u] = r ;
    if(l == r){
        val[u] = d[l] ;
        return ;
    }
    M[u] = l + r >> 1 ;
    build(l , M[u] , LL(u)) ;
    build(M[u] + 1 , r ,RR(u)) ;
    push_up(u) ;
}

void update(int l , int u , int num){
    if(L[u] == l && R[u] == l){
        val[u] += num ;
        return ;
    }
    if(l <= M[u])update(l ,LL(u) ,num) ;
    else update(l, RR(u) , num) ;
    push_up(u) ;
}
int query(int l ,int r ,int u){
    if(L[u] == l && R[u] == r){
        return val[u] ;
    }
    if(r <= M[u])return query(l ,r ,LL(u)) ;
    else if(l > M[u])return query(l , r, RR(u)) ;
    else return (query(l ,M[u] , LL(u)) + query(M[u] + 1 , r ,RR(u)));
}
bool cmp(const kdq& a ,const kdq&b){
    return a.s < b.s ;
}
int main() {
    int T ;
    cin >> T ;
    while(T -- ){
        int n , m ;
        cin >> n >> m ;
        init() ;
        for (int i = 1 ; i <= n ; i ++ ){
            RD(a[i]) ;
            pos[a[i]] = i ;
        }
        for (int i = 0 ; i < m ; i ++ ){
            RD(Q[i].s) ;
            RD(Q[i].e) ;
            Q[i].id = i ;
        }
        for (int i = 1 ; i <= n ; i ++ ){
            int nn = 0 ;
            if(is[a[i] + 1]) nn ++ ;
            if(is[a[i] - 1]) nn ++ ;
            if(nn == 2)d[i] -- ;
            else if(nn == 0)d[i] ++ ;
            is[a[i]] = 1 ;
        }
        build(1 , n , 1) ;
        sort(Q , Q + m ,cmp) ;
        int st = 1 ;
        for (int i = 0 ; i < m ; i ++ ){
            while(Q[i].s > st){
                if(pos[a[st] + 1] > st && a[st] < n){
                    update(pos[a[st] + 1] ,1 , 1) ;
                }
                if(pos[a[st] - 1] > st && a[st] > 1){
                    update(pos[a[st] - 1] , 1, 1) ;
                }
                st ++ ;
            }
            ans[Q[i].id] = query(Q[i].s ,Q[i].e , 1) ;
        }
        for (int i = 0 ; i < m ; i ++ ){
            printf("%d\n",ans[i]) ;
        }
    }
    return 0 ;
}

樹狀數組CODE：

 #include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 2505  
#define inf 1<<28  
#define LL(x) ( x << 1 )  
#define RR(x) ( x << 1 | 1 )  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define PII pair<int,int>  
using namespace std; 
 
 
inline void RD(int &ret) { 
    char c; 
    do { 
        c = getchar(); 
    } while(c < '0' || c > '9') ; 
    ret = c - '0'; 
    while((c=getchar()) >= '0' && c <= '9') 
        ret = ret * 10 + ( c - '0' ); 
} 
inline void OT(int a){ 
    if(a >= 10)OT(a / 10) ; 
    putchar(a % 10 + '0') ; 
} 
#define N 100005  
int a[N] ; 
int n , m ; 
struct kdq{ 
    int s , e , id ; 
}ed[N] ; 
bool cmp(const kdq& a ,const kdq& b){ 
    return a.s < b.s ; 
} 
int c[N] ; 
inline void update(int pos ,int num){ 
    for (int i = pos ; i <= n ; i += i & (-i) ){ 
        c[i] += num ; 
    } 
} 
inline int sum(int pos){ 
    int ans = 0 ; 
    for (int i = pos ; i >= 1 ; i -= i & (-i)){ 
        ans += c[i] ; 
    } 
    return ans ; 
} 
int is[N] ; 
int ans[N] ; 
int pos[N] ; 
int main() { 
    int T ; 
    cin >> T ; 
    while( T -- ){ 
        cin >> n >> m ; 
        mem(c ,0) ; 
        mem(is , 0) ; 
        mem(pos , 0) ; 
        REP(i , 1 , n ){ 
            RD(a[i]) ; 
            pos[a[i]] = i ; 
        } 
        REP(i , 0 , m - 1){ 
            RD(ed[i].s) ; 
            RD(ed[i].e) ; 
            ed[i].id = i ; 
        } 
        REP(i , 1 , n){ 
            int nn = 0 ; 
            if(is[a[i] + 1])nn ++ ; 
            if(is[a[i] - 1])nn ++ ; 
            if(nn == 2)update(i , -1) ; 
            else if(nn == 0)update(i , 1) ; 
            is[a[i]] = 1 ; 
        } 
        sort(ed , ed + m ,cmp) ; 
        int st = 1 ; 
        for (int i = 0 ; i < m ; i ++ ){ 
            while(ed[i].s > st){ 
                if(pos[a[st] + 1] > st && a[st] < n){ 
                    update(pos[a[st] + 1] , 1) ; 
                } 
                if(pos[a[st] - 1] > st && a[st] > 1){ 
                    update(pos[a[st] - 1] , 1) ; 
                } 
                st ++ ; 
            } 
            ans[ed[i].id] = sum(ed[i].e) - sum(ed[i].s - 1) ; 
        } 
        for (int i = 0 ; i < m ; i ++ ){ 
            printf("%d\n",ans[i]) ; 
        } 
    } 
    return 0 ; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;


inline void RD(int &ret) {
    char c;
    do {
        c = getchar();
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
inline void OT(int a){
    if(a >= 10)OT(a / 10) ;
    putchar(a % 10 + '0') ;
}
#define N 100005
int a[N] ;
int n , m ;
struct kdq{
    int s , e , id ;
}ed[N] ;
bool cmp(const kdq& a ,const kdq& b){
    return a.s < b.s ;
}
int c[N] ;
inline void update(int pos ,int num){
    for (int i = pos ; i <= n ; i += i & (-i) ){
        c[i] += num ;
    }
}
inline int sum(int pos){
    int ans = 0 ;
    for (int i = pos ; i >= 1 ; i -= i & (-i)){
        ans += c[i] ;
    }
    return ans ;
}
int is[N] ;
int ans[N] ;
int pos[N] ;
int main() {
    int T ;
    cin >> T ;
    while( T -- ){
        cin >> n >> m ;
        mem(c ,0) ;
        mem(is , 0) ;
        mem(pos , 0) ;
        REP(i , 1 , n ){
            RD(a[i]) ;
            pos[a[i]] = i ;
        }
        REP(i , 0 , m - 1){
            RD(ed[i].s) ;
            RD(ed[i].e) ;
            ed[i].id = i ;
        }
        REP(i , 1 , n){
            int nn = 0 ;
            if(is[a[i] + 1])nn ++ ;
            if(is[a[i] - 1])nn ++ ;
            if(nn == 2)update(i , -1) ;
            else if(nn == 0)update(i , 1) ;
            is[a[i]] = 1 ;
        }
        sort(ed , ed + m ,cmp) ;
        int st = 1 ;
        for (int i = 0 ; i < m ; i ++ ){
            while(ed[i].s > st){
                if(pos[a[st] + 1] > st && a[st] < n){
                    update(pos[a[st] + 1] , 1) ;
                }
                if(pos[a[st] - 1] > st && a[st] > 1){
                    update(pos[a[st] - 1] , 1) ;
                }
                st ++ ;
            }
            ans[ed[i].id] = sum(ed[i].e) - sum(ed[i].s - 1) ;
        }
        for (int i = 0 ; i < m ; i ++ ){
            printf("%d\n",ans[i]) ;
        }
    }
    return 0 ;
}