HDU4417:Super Mario(主席树查询区间比k小的数的个数)
程序员文章站
2024-03-03 18:24:46
...
题意如标题所示,查询[i,j]区间内小于等于h的数的个数,是一道主席树的模板题,刚开始没离散化,直接用1e9建树T了,然后不太清醒的情况下写了2个小时离散化。。。
/*
主席树查询小于等于k的数的个数;
*/
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<map>
int t,n,m,x,y,h,tot;
const int maxn = 1e5 + 10;
map<int,int> mp;
struct tt{
int ls,rs,val;
}tree[20 * maxn];
int root[maxn],cnt,a[maxn],b[maxn];
void init(){
mp.clear();
memset(root,0,sizeof(root));
root[0] = cnt = tot = 0;
tree[0].ls = tree[0].rs = tree[0].val = 0;
}
void update(int &rt,int k,int l,int r){
tree[++cnt] = tree[rt];
rt = cnt;
tree[rt].val++;
if(l == r) return;
int mid = l + r >> 1;
if(k > mid) update(tree[rt].rs,k,mid + 1,r);
else update(tree[rt].ls,k,l,mid);
}
int query(int i,int j,int k,int l,int r){
if(r <= k){
return tree[j].val - tree[i].val;
}
int res = 0;
int mid = l + r >> 1;
if(l <= k) res += query(tree[i].ls,tree[j].ls,k,l,mid);
if(mid + 1 <= k) res += query(tree[i].rs,tree[j].rs,k,mid + 1,r);
return res;
}
int main(){
scanf("%d",&t);
int ce = 0;
while(t--){
printf("Case %d:\n",++ce);
scanf("%d%d",&n,&m);
init();
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
b[i] = a[i];
}
sort(a + 1,a + n + 1);
for(int i = 1; i <= n; i++){
if(mp[a[i]]) continue;
mp[a[i]] = ++tot;
}
for(int i = 1; i <= n; i++){
root[i] = root[i - 1];
update(root[i],mp[b[i]],1,tot);
}
sort(b + 1,b + n + 1);
int p = unique(b + 1,b + n + 1) - b - 1;
b[0] = -10;
for(int i = 1; i <= m; i++){
scanf("%d%d%d",&x,&y,&h);
x++;y++;
int tmp = lower_bound(b + 1,b + p + 1,h) - b;
if(h != b[tmp]) tmp--;
h = b[tmp];
printf("%d\n",query(root[x - 1],root[y],mp[h],1,tot));
}
}
return 0;
}
上一篇: 最长上升子序列