Super Mario 主席树 hdu-4417
题目链接:
题面:
题意:有n个墙,m次查询,下面给每个墙的高度,每次查询给左区间,右区间和马里奥跳跃的最高高度,问马里奥可以跳上几座墙
思路:主席树,可以通过离散化的方法,把墙的高度离散下去,然后维护从第一面墙到第i面墙中一共的不同墙体的数量,然后通过前缀和的思想可以快速求值
#include <bits/stdc++.h> using namespace std; #define endl " " #define N 100005 int a[N]; vector<int> ve; struct node{ int num;//存这个区间内总墙体数量 int lson; int rson; }tree[N * 40]; int root[N]; int cnt = 0; void pushup(int rt){ tree[rt].num = tree[tree[rt].lson].num + tree[tree[rt].rson].num; } int build(int l, int r, int rt){ tree[++cnt] = tree[rt]; rt = cnt; if(l == r){ tree[rt].num = 0; return rt; } int mid = (l + r) / 2; tree[rt].lson = build(l, mid, tree[rt].lson); tree[rt].rson = build(mid + 1, r, tree[rt].rson); pushup(rt); return rt; } int find(int x){ return lower_bound(ve.begin(), ve.end(), x) - ve.begin() + 1; } int updata(int l, int r, int rt, int k){ tree[++cnt] = tree[rt]; rt = cnt; if(l == r){ //将高为k的墙体数量++ tree[rt].num ++; return rt; } int mid = (l + r) / 2; if(k <= mid){ tree[rt].lson = updata(l, mid, tree[rt].lson, k); }else{ tree[rt].rson = updata(mid + 1, r, tree[rt].rson, k); } pushup(rt); return rt; } int query(int l, int r, int L, int R, int k){ if(r <= k){ return tree[R].num - tree[L].num; } int mid = (l + r) / 2; if(k <= mid){ return query(l, mid, tree[L].lson, tree[R].lson, k); }else{ int ans = 0; ans += query(l, mid, tree[L].lson, tree[R].lson, k); ans += query(mid + 1, r, tree[L].rson, tree[R].rson, k); return ans; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int ans = 1; int t; cin >> t; while(t--){ cnt = 0; int n, m; cin >> n >> m; ve.clear(); for(int i = 1; i <= n; i++){ cin >> a[i]; ve.push_back(a[i]); } sort(ve.begin(), ve.end()); ve.erase(unique(ve.begin(), ve.end()), ve.end()); root[0] = build(1, ve.size(), 0); for(int i = 1; i <= n; i++){//加上这面墙是一个新的线段树 root[i] = updata(1, ve.size(), root[i - 1], find(a[i])); } cout << "Case " << ans++ << ":" << endl; for(int i = 0; i < m; i++){ int l, r, h; cin >> l >> r >> h; l++; r++; int k = find(h); if(k == 1 && ve[0] > h){ cout << 0 << endl; }else { if(k == ve.size() + 1){ k--; }else if(ve[k - 1] != h){ k--; } cout << query(1, ve.size(), root[l - 1], root[r], k) << endl; } } } return 0; }