InputFirst line is T indicate the case number.
For each case first line is n, m(1<=n ,m<=100000) indicate there are n men and m query.
Then a line have n number indicate the ID of men from left to right.
Next m line each line has two number L,R(1<=L<=R<=n),mean we want to know the answer of [L,R].
OutputFor every query output a number indicate there should be how many group so that the sum of value is max.Sample Input
1 5 2 3 1 2 5 4 1 5 2 4
Sample Output
1 2
题意:给你N个数,然后给出M个查询;对于每一个查询,该区间内最少可以有多少个连续的序列;
题解:莫队(也可以用树,单位现在还不会,以后补上~~);
AC代码为:
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 typedef long long ll; 5 const int M = 200000 + 5; 6 7 int a[M], vis[M], ans, ret[M]; 8 struct node 9 { 10 int id, l, r, pos; 11 }v[M]; 12 13 14 int cmp(node x, node y) 15 { 16 if (x.pos<y.pos) 17 return 1; 18 else if (x.pos == y.pos&&x.r<y.r) 19 return 1; 20 return 0; 21 } 22 23 inline void insert(int x) 24 { 25 x = a[x]; 26 vis[x] = 1; 27 if (vis[x - 1] && vis[x + 1]) 28 { 29 ans--; 30 } 31 else if (!vis[x - 1] && !vis[x + 1]) 32 { 33 ans++; 34 } 35 } 36 37 inline void erase(int x) 38 { 39 x = a[x]; 40 vis[x] = 0; 41 if (vis[x - 1] && vis[x + 1]) 42 { 43 ans++; 44 } 45 else if (!vis[x - 1] && !vis[x + 1]) 46 { 47 ans--; 48 } 49 } 50 51 int main() 52 { 53 int t, n, m, i, j, k; 54 int l, r; 55 scanf("%d", &t); 56 while (t--) 57 { 58 scanf("%d%d", &n, &m); 59 for (i = 1; i <= n; i++) 60 scanf("%d", &a[i]); 61 int x = sqrt(n); 62 for (i = 1; i <= m; i++) 63 { 64 scanf("%d%d", &v[i].l, &v[i].r); 65 v[i].id = i; 66 v[i].pos = v[i].l / x; 67 } 68 sort(v + 1, v + m + 1, cmp); 69 memset(vis, 0, sizeof(vis)); 70 ans = 0; 71 insert(1); 72 int p = 1, q = 1; 73 for (i = 1; i <= m; i++) 74 { 75 l = v[i].l; 76 r = v[i].r; 77 while (q<r) insert(++q); 78 while (q>r) erase(q--); 79 while (p<l) erase(p++); 80 while (p>l) insert(--p); 81 ret[v[i].id] = ans; 82 } 83 for (i = 1; i <= m; i++) 84 printf("%d\n", ret[i]); 85 } 86 return 0;
© 著作权归作者所有
发表评论