hdu 4638 Group
http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意：给定一个序列，序列由1-N个元素全排列而成，求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。 思路：增加一个元素，如果它两边的元素都出现了，那么段数-1（相当于把两段连接起来合并成了一段），如果两边元素都没有出现，那么段数+1.反过来，减少一个元素时，如果两边元素都出现了，俺么段数+1（相当于把完整的一段断开成两段），如果两边元素都没有出现，那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000，所以判断某个元素是否出现开一个100000大小的布尔数组即可（我竟然傻逼得去用set….然后华丽丽得TLE了2333）
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月18日 星期四 03时03分48秒
4File Name :code/hdu/4638.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n,m;
35int pos[N];
36int a[N];
37int ans[N];
38int sum;
39bool vis[N];
40
41struct node
42{
43 int l,r;
44 int id;
45
46 bool operator <(node b)const
47 {
48 if (pos[l]==pos[b.l]) return r<b.r;
49 return pos[l]<pos[b.l];
50 }
51}q[N];
52
53
54void update( int x,int d)
55{
56
57 // cout<<"cnt1:"<<cnt1<<" cnt2:"<<cnt2<<endl;
58 if (d>0)
59 {
60 if (vis[a[x]-1]&&vis[a[x]+1])
61 sum--;
62 if (!vis[a[x]-1]&&!vis[a[x]+1])
63 sum++;
64
65 vis[a[x]] = true;
66 }
67 else
68 {
69 if (vis[a[x]-1]&&vis[a[x]+1]) sum++;
70 if (!vis[a[x]-1]&&!vis[a[x]+1])sum--;
71 vis[a[x]] = false;
72 }
73}
74int main()
75{
76 #ifndef ONLINE_JUDGE
77 freopen("code/in.txt","r",stdin);
78 #endif
79 int T;
80 cin>>T;
81 while (T--)
82 {
83 ms(ans,0);
84 ms(vis,false);
85 scanf("%d %d",&n,&m);
86 int siz = 316; //sqrt(100000)
87 for ( int i = 1 ; i <= n ; i++)
88 {
89 scanf("%d",&a[i]);
90 pos[i] = (i-1)/siz;
91 }
92
93 for ( int i =1 ; i <= m ; i++)
94 {
95 scanf("%d %d",&q[i].l,&q[i].r);
96 q[i].id = i;
97 }
98 sort(q+1,q+m+1);
99// for ( int i = 1 ; i <= m ; i++) cout<<q[i].l<<" "<<q[i].r<<endl;
100
101
102 int pl=1,pr=0;
103 int id,l,r;
104 sum = 0 ;
105 for ( int i = 1 ; i <= m ; i++)
106 {
107 id = q[i].id;
108 l = q[i].l;
109 r = q[i].r;
110
111 if (pr<r)
112 {
113 for ( int j = pr +1 ; j <= r ; j++) update(j,1);
114 }
115 else
116 {
117 for ( int j = r + 1 ; j <= pr ; j++) update(j,-1);
118 }
119 pr = r;
120
121 if (l<pl)
122 {
123 for ( int j = l ; j <= pl-1 ; j++) update(j,1);
124 }
125 else
126 {
127 for ( int j = pl ; j <= l-1 ; j++) update(j,-1);
128 }
129 pl = l;
130
131 ans[id]=sum;
132 }
133
134 for ( int i = 1 ; i <= m ; i++) printf("%d\n",ans[i]);
135 }
136
137 #ifndef ONLINE_JUDGE
138 fclose(stdin);
139 #endif
140 return 0;
141}