hdu 4638 Group(离线线段树) - c++编程基础

TOP

hdu 4638 Group(离线线段树)

2014-11-23 20:25:33 来源: 作者: 【大中小】浏览:10次

搞了这么久，终于做了一个离线线段树。。。。个人觉得，如果询问间会相互影响到的话，就用所谓“离线”来搞。。。

这个题，考虑从左到右一个一个地加数，加到a[i]时，如果a[i]-1或a[i]+1有一个加过，总段数不变，都加过，合并两端，段数减一；如果都没加过，加入a[i]相当于新加了一段。

将所有询问按右端点从小到大处理（一个大的区间，增加的元素会对小的区间造成影响）；边处理边加数。

include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define FF(i, a, b) for(int i=a; i=b; i--)  
#define REP(i, n) for(int i=0; i 0) 
    { 
        ret += c[x]; 
        x -= low(x); 
    } 
    return ret; 
} 
 
int main() 
{ 
    int T; scanf("%d", &T); 
    while(T--) 
    { 
        scanf("%d%d", &n, &m); 
        FF(i, 1, n+1) scanf("%d", &a[i]), pos[a[i]] = i, c[i] = 0; 
        REP(i, m) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i; 
        sort(q, q+m); 
        int j = 1; 
        for(int i=0; i 1 && pos[a[j]-1] < j) add(pos[a[j]-1], -1); 
                if(a[j] < n && pos[a[j]+1] < j) add(pos[a[j]+1], -1); 
                j++; 
            } 
        } 
        REP(i, m) printf("%d\n", ans[i]); 
    } 
    return 0; 
} 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FF(i, a, b) for(int i=a; i=b; i--)
#define REP(i, n) for(int i=0; i 0)
    {
        ret += c[x];
        x -= low(x);
    }
    return ret;
}

int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        FF(i, 1, n+1) scanf("%d", &a[i]), pos[a[i]] = i, c[i] = 0;
        REP(i, m) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
        sort(q, q+m);
        int j = 1;
        for(int i=0; i 1 && pos[a[j]-1] < j) add(pos[a[j]-1], -1);
                if(a[j] < n && pos[a[j]+1] < j) add(pos[a[j]+1], -1);
                j++;
            }
        }
        REP(i, m) printf("%d\n", ans[i]);
    }
    return 0;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：kmp&&hdu 1711 next数组	下一篇：1015. Reversible Primes (20) PA..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: