HDU 4638 多校第四场1007 离线询问，树状数组||线段树维护 - c++编程基础

TOP

HDU 4638 多校第四场1007 离线询问，树状数组||线段树维护 (一)

2014-11-23 21:34:28 来源: 作者: 【大中小】浏览:6次

这道题其实和前面机场出的树状数组和线段数题都差不多。

目测现在出这种离线处理，树状数组维护的题好多啊。

题意：给出一个序列，然后问，一个区间内，最多有多少人个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   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#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  
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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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
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   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#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  
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 +

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU--杭电--1195--Open the Lock-..	下一篇：Strategic Game HDU

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: