Super Mario

思路

區間查找問題，容易想到離線莫隊，確實這題就是莫隊，接下來我們考慮如何維護區間高度值問題。

既然是離線嘛，我們容易想到離散化和他掛鉤，想想這題是否需要離散化，高度的最大值是$100000000$，但是我們的數據最大值只有$100000$，由此我們可以考慮離散化之后用樹狀數組來維護區間的高度值，再通過樹狀數組的前綴和查詢來得到我們需要的$[1,h]$的答案，由此一個完美的算法(莫隊 + 離散化 + 樹狀數組)就呈現出來了。

具體細節我在代碼中詳細講述。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 1e5 + 10;int h[N], a[N], tree[N], pos[N], ans[N], n, m, block, tot;struct Node {int l, r, h, id;bool operator < (const Node & t) const {return (l / block) != (t.l / block) ? l < t.l : ((l / block) & 1) ? r < t.r : r > t.r;} }ask[N];void update(int x, int value) {while(x <= tot) {tree[x] += value;x += (-x) & (x);} }int query(int x) {int ans = 0;while(x) {ans += tree[x];x -= (-x) & (x);}return ans; }void add(int pos) {update(pos, 1); }void del(int pos) {update(pos, -1); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int _ = read();for(int cas = 1; cas <= _; cas++) {printf("Case %d:\n", cas);n = read(), m = read(), block = sqrt(n);for(int i = 1; i <= n; i++) h[i] = a[i] = read();sort(a + 1, a + 1 + n);tot = unique(a + 1, a + n + 1) - (a + 1);//對高度進行離散化操作，這點應該沒問題。for(int i = 1; i <= m; i++) {ask[i] = {(int)read() + 1, (int)read() + 1, (int)read(), i};//為了順手，我把所有的坐標向右移動了一格。}sort(ask + 1, ask + 1 + m);//為了莫隊，進行排序。int l = 1, r = 0;for(int i = 1; i <= n; i++) {//把每一個位置離散化后的位置記錄下來，方便后面查詢。pos[i] = lower_bound(a + 1, a + tot + 1, h[i]) - a;}for(int i = 1; i <= m; i++) {//莫隊開始了。while(r < ask[i].r) add(pos[++r]);while(r > ask[i].r) del(pos[r--]);while(l > ask[i].l) add(pos[--l]);while(l < ask[i].l) del(pos[l++]);//查詢的是小于等于當前高度的數量，所以直接upper_bound - 1操作即可。ans[ask[i].id] = query(upper_bound(a + 1, a + tot + 1, ask[i].h) - a - 1);}for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);for(int i = 1; i <= tot; i++) tree[i] = 0;//樹狀數組清零。}return 0; }

總結

以上是生活随笔為你收集整理的HDU 4417 Super Mario（莫队 + 树状数组 + 离散化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。