题意：有一个无序数组，求有多少个长度为k的区间满足把区间内的数排序后是连续的。
思路：长度为k的区间排序后是 连续的数等价于maxval-minval等于k-1并且不同的数有k个（或者说没有相同的数），第一个条件可以用rmq快速得到区间最大值与最小值之差，第二个条件可以这样求，按区间的左边界分类预处理，遍历右边界，如果[L,R]内有相同的数，则[L,R+k]有相同的数，否则转化为判断a[R+1]是否在区间[L,R]内出现过，维护一个last数组，last[i]表示i上一次出现的位置，那么等价于判断last[a[R+1]]是否>=L，由于a[i]很大，所以需离散后处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <vector>using namespace std;typedef long long LL;#define all(a) (a).begin(), (a).end()const int maxn = 1e4 + 7;struct ST { struct Node { int a[22]; int &operator [] (int x) { return a[x]; } }; const static int maxn = 1e6 + 7; vector<Node> dp; static int index[maxn]; static void init_index() { index[1] = 0; for (int i = 2; i < maxn; i ++) { index[i] = index[i - 1]; if (!(i & (i - 1))) index[i] ++; } } void init_min(vector<int> &a) { int n = a.size(); dp.resize(n); for (int i = 0; i < n; i ++) dp[i][0] = a[i]; for (int j = 1; (1 << j) <= n; j ++) { for (int i = 0; i + (1 << j) - 1 < n; i ++) { dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } } } void init_max(vector<int> &a) { int n = a.size(); dp.resize(n); for (int i = 0; i < n; i ++) dp[i][0] = a[i]; for (int j = 1; (1 << j) <= n; j ++) { for (int i = 0; i + (1 << j) - 1 < n; i ++) { dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } } } int query_min(int L, int R) { int p = index[R - L + 1]; return min(dp[L][p], dp[R - (1 << p) + 1][p]); } int query_max(int L, int R) { int p = index[R - L + 1]; return max(dp[L][p], dp[R - (1 << p) + 1][p]); }};int ST::index[maxn];ST st1, st2;vector<int> a, b;bool chk[maxn][1000];int last[maxn];int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE puts("Case #1:"); int n, m; cin >> n >> m; a.resize(n); for (int i = 0; i < n; i ++) { scanf("%d", &a[i]); } b = a; ST::init_index(); st1.init_max(a); st2.init_min(a); sort(all(a)); a.erase(unique(all(a)), a.end()); for (int i = 0; i < n; i ++) { b[i] = lower_bound(all(a), b[i]) - a.begin(); } for (int i = 0; i < n; i ++) { chk[i][1] = true; memset(last, 0xff, sizeof(last)); last[b[i]] = i; for (int L = 2; i + L - 1 < n && L <= 1000; L ++) { if (last[b[i + L - 1]] >= i) break; last[b[i + L - 1]] = i + L - 1; chk[i][L] = true; } } for (int i = 0; i < m; i ++) { int k; scanf("%d", &k); int ans = 0; for (int i = 0; i + k - 1 < n; i ++) { ans += st1.query_max(i, i + k - 1) - st2.query_min(i, i + k - 1) == k - 1 && chk[i][k]; } printf("%d
", ans); } return 0;} |