连接：http://acm.hdu.edu.cn/showproblem.php?pid=4638
题意：就给给你n个数（大小在1-n里），然后给你连续的可以构成一个块，再给你N个询问，每个询问一个l,一个r问你l-r里面有多少个连续的段
其实每一个数都是一个独立的段，当有连续的时候连续段数就会-1，因为连续的段中，位置最靠前的哪一个只会影响以这个位置为l的询问，不会影响后面的，所以，我们可以对询问从后向前去找，离线话去找。这样的话就可以用树状数组去解决问题、
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <vector> 7 #include <queue> 8 #define loop(s,i,n) for(i = s;i < n;i++) 9 #define cl(a,b) memset(a,b,sizeof(a)) 10 #define lowbit(x) x&-x 11 using namespace std; 12 int c[100050]; 13 vector<int> e[100050]; 14 struct node 15 { 16 int r,num; 17 }; 18 vector <node> q[100050]; 19 int m,n; 20 int sum(int x) 21 { 22 int res = 0; 23 while(x > 0) 24 { 25 res += c[x]; 26 x -= lowbit(x); 27 } 28 return res; 29 } 30 31 void add(int x,int d) 32 { 33 while(x <= n) 34 { 35 c[x] += d; 36 x += lowbit(x); 37 } 38 } 39 int loc[100050]; 40 int a[100050]; 41 int ans[100050]; 42 43 int main() 44 { 45 int t; 46 scanf("%d",&t); 47 while(t--) 48 { 49 int i,j; 50 cl(c,0); 51 scanf("%d %d",&n,&m); 52 loop(1,i,n+1) 53 { 54 scanf("%d",a+i); 55 loc[a[i]] = i; 56 } 57 loop(1,i,n+1) 58 e[i].clear(); 59 loop(1,i,n+1) 60 { 61 if(a[i]> 1) 62 { 63 if(loc[a[i]-1] > loc[a[i]]) 64 e[loc[a[i]]].push_back(loc[a[i]-1]); 65 else 66 e[loc[a[i]-1]].push_back(loc[a[i]]); 67 } 68 } 69 loop(1,i,m+1) 70 { 71 q[i].clear(); 72 } 73 loop(1,i,m+1) 74 { 75 int l,r; 76 struct node temp; 77 scanf("%d %d",&l,&r); 78 temp.num = i,temp.r = r; 79 80 q[l].push_back(temp); 81 } 82 83 for(i = n;i >= 1;i--) 84 { 85 loop(0,j,e[i].size()) 86 { 87 int v; 88 v = e[i][j]; 89 add(v,1); 90 } 91 92 loop(0,j,q[i].size()) 93 { 94 ans[q[i][j].num] = q[i][j].r-i-sum(q[i][j].r)+1; 95 } 96 97 } 98 99 loop(1,i,m+1) 100 printf("%d ",ans[i]); 101 102 } 103 return 0; 104 }