HDU 4638 Group （线段树 + 离线）

题意：给定一个N长的序列，有n个人编号1-n ，第i个人和第i-1，i+1 互相为朋友，询问多次，问你询问的区间里面有多少堆（可以互相认识）朋友：

解题思路：开始一想有点像并查集的味道，不过想到LSS（我的队友，图论大牛）博客里面说的是线段树加离线（http://blog.csdn.net/u010126535），就按这个方面去想了，这题的主要思想是对询问的左端点按从大到小排序，然后对序列从后往前扫，对于A[I] 如果 A[I]- 1 或A[I] +1 出现过的话，更新其（它的两个邻居位置）线段树节点（+1）；然后询问的答案就是这个区间长度-区间和，（这里主要是因为总是有一个连续序列排在最后面那个单独出来，我们就是求这个单独出来的个数，读者好好想想，我也是YY了好久。。）。

解题代码：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <string>
  6 #include <math.h>
  7 
  8 using namespace std;
  9 
 10 #define maxn 100005
 11 struct op
 12 {
 13   int l , r ;
 14   int num;
 15 }ops[maxn];
 16 int hs[maxn];
 17 struct node
 18 {
 19   int l , r, m ;
 20   int num ;
 21 }tree[maxn*4];
 22 int L(int c)
 23 {
 24   return 2*c;
 25 }
 26 int R(int c)
 27 {
 28    return 2*c + 1;
 29 }
 30 void Pushup(int c)
 31 {
 32    tree[c].num = tree[L(c)].num + tree[R(c)].num;
 33 }
 34 void build(int c , int p , int v)
 35 {
 36     tree[c].l = p;
 37     tree[c].r = v ;
 38     tree[c].m = (p+v)/2;
 39     tree[c].num = 0 ;
 40     if(p == v)
 41         return ;
 42     build(L(c),p,tree[c].m);
 43     build(R(c),tree[c].m+1,v);
 44 }
 45 void update(int c ,int p  )
 46 {
 47     if(tree[c].l == tree[c].r && tree[c].l == p)
 48     {
 49         tree[c].num ++ ;
 50         return ;
 51     }
 52     if(p <= tree[c].m) update(L(c),p);
 53     else if(p > tree[c].m) update(R(c),p);
 54     Pushup(c);
 55 }
 56 int tsum = 0 ;
 57 void getsum(int c , int p ,int v )
 58 {
 59    if(p <= tree[c].l && v >= tree[c].r)
 60    {
 61      tsum += tree[c].num ;
 62      return ;
 63    }
 64    if(v <= tree[c].m) getsum(L(c),p,v);
 65    else if(p > tree[c].m) getsum(R(c),p,v);
 66    else {
 67     getsum(L(c),p,tree[c].m);
 68     getsum(R(c),tree[c].m+1 ,v);
 69    }
 70 }
 71 int a[maxn];
 72 int cmp(struct op a ,struct op b)
 73 {
 74      return a.l > b.l;
 75 }
 76 int ans[maxn];
 77 int main()
 78 {
 79     int t;
 80     scanf("%d",&t);
 81     while(t--)
 82     {
 83       memset(hs,0,sizeof(hs));
 84       int n ,m ;
 85       scanf("%d %d",&n,&m);
 86       build(1,1,n);
 87       for(int i = 1;i <= n;i ++)
 88         scanf("%d",&a[i]);
 89       for(int i = 1;i <= m;i ++ )
 90         {
 91           scanf("%d %d",&ops[i].l,&ops[i].r);
 92           ops[i].num = i ;
 93         }
 94       sort(ops+1,ops+1+m,cmp);
 95       int k = 1 ;
 96       for(int i = n; i >= 1 ;i --)
 97       {
 98           hs[a[i]] = i ;
 99           if(hs[a[i]-1] != 0 )
100           {
101              update(1,hs[a[i]-1]);
102           }
103           if(hs[a[i]+1] != 0 )
104           {
105              update(1,hs[a[i]+1]);
106           }
107 
108 
109           while(ops[k].l == i)
110           {
111             tsum = 0;
112             getsum(1,ops[k].l,ops[k].r);
113             ans[ops[k].num] =(ops[k].r - ops[k].l +1) -tsum;
114             k++;
115           }
116       }
117       for(int i= 1;i <= m;i ++)
118         printf("%d
",ans[i]);
119     }
120 
121   return 0 ;
122 }

View Code

HDU 4638 Group （线段树 + 离线）

相关推荐