当前位置：编程学习 > C/C++ >>

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>  
#includ
补充：软件开发 , C++ ,

上一个：HDU1009 FatMouse' Trade
下一个：Strategic Game HDU

更多图片编程知识:
更多C/C++疑问解答：
关于c++的cout输出的问题。
在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
全国计算机二级C语言笔试题
已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
c++数据结构内部排序问题，整数排序
2012九月计算机二级C语言全国题库，，急求急求
如果assert只有一个字符串作为参数，是什么意思呢?
C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
为什么用结构体编写的程序输入是，0输不出来啊~~~
将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
为什么这个程序求不出公式？
这个链表倒置的算法请大家分析下
c语言函数库调用
C语言unsigned int纠错
C语言快排求解啊
asp
php
Delphi
Matlab
JSP
Foxpro
JS
C/C++
C#/ASP.NET
VC++
JAVA
VB
汇编语言
html/css
CGI
XML/UML
wap
网站相关
网页素材
python
如果你遇到编程学习难题：
请访问www.zzzyk.com 试试
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络，