分块

1、POJ 2104 K-th Number

参考：《挑战程序设计竞赛》P186

注意：

1、各种边界问题

2、块的大小要合适，比如书中的1000，块的大小为sqrt(n)会超时，因为在进行判断的时候复杂度是有差别的，分别为sqrt(n * logn和sqrt(n) * logn

3、二分的时候试着不用判断而是循环100次，竟然WA了。。。

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #include <stack> #include <map> #include <set> #include <cmath> #include <cctype> #include <ctime> #include <cassert> using namespace std; #define REP(i, n) for (int i = 0; i < (n); ++i) #define eps 1e-9 typedef long long ll; typedef pair<int, int> pii; const int INF = 1e9; const int maxn = 1e5 + 10; int n, m, x, y, k, block, Left, Right; int a[maxn], a_t[maxn], a_sorted[maxn]; int judge(int num); int main() { #ifdef __AiR_H freopen("in.txt", "r", stdin); // freopen("out3.txt", "w", stdout); #endif // __AiR_H scanf("%d %d", &n, &m); block = 1000; int t = n / block; REP(i, n) { scanf("%d", &a[i]); a_t[i] = a[i]; a_sorted[i] = a[i]; } for (int i = 0; i < t * block; i += block) { sort(a + i, a + i + block); } sort(a_sorted, a_sorted + n); int low = -1, high = n - 1, mid; while (m--) { scanf("%d %d %d", &x, &y, &k); if ((x - 1) % block == 0) { Left = x - 1; } else { Left = ((x - 1) / block + 1) * block; } if (y % block == 0) { Right = y; } else { Right = (y / block) * block; } --x; --y; low = -1; high = n - 1; while (high - low > 1) { mid = low + (high - low) / 2; if (judge(a_sorted[mid])) { high = mid; } else { low = mid; } } printf("%d\n", a_sorted[high]); } #ifdef __AiR_H printf("Time used = %.2fs\n", (double)clock() / CLOCKS_PER_SEC); #endif // __AiR_H return 0; } int judge(int num) { int cnt = 0; if (Left >= Right - 1) { for (int i = x; i <= y; ++i) { if (a_t[i] <= num) { ++cnt; } } if (cnt >= k) { return 1; } return 0; } for (int i = x; i < Left; ++i) { if (a_t[i] <= num) { ++cnt; } } for (int i = Left; i < Right; i += block) { cnt += upper_bound(a + i, a + i + block, num) - (a + i); } for (int i = Right; i <= y; ++i) { if (a_t[i] <= num) { ++cnt; } } if (cnt >= k) { return 1; } return 0; }

2、SPOJ - ADALIST

借鉴了@tju-fishporridge大佬的代码，他是双端队列写的，比vector要慢好多。。。

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #include <stack> #include <map> #include <set> #include <cmath> #include <cctype> #include <ctime> #include <cassert> using namespace std; #define REP(i, n) for (int i = 0; i < (n); ++i) #define eps 1e-9 typedef long long ll; typedef pair<int, int> pii; const int INF = 0x7fffffff; const int maxn = 1e5 + 10; int N, Q, cmd, k, x, block; int a[maxn]; vector<int> v[1000]; int main() { #ifdef __AiR_H freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif // __AiR_H scanf("%d %d", &N, &Q); REP(i, N) { scanf("%d", &a[i]); } block = sqrt(N + Q); REP(i, N) { v[i / block].push_back(a[i]); } while (Q--) { scanf("%d %d", &cmd, &k); if (cmd == 1) { --k; } int cur = 0; while (k > (int)v[cur].size()) { k -= v[cur++].size(); } if (cmd == 1) { scanf("%d", &x); v[cur].insert(v[cur].begin() + k, x); } else if (cmd == 2) { v[cur].erase(v[cur].begin() + k - 1); } else { printf("%d\n", v[cur][k - 1]); } } #ifdef __AiR_H printf("Time used = %.2fs\n", (double)clock() / CLOCKS_PER_SEC); #endif // __AiR_H return 0; }