Super Mario
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10963 Accepted Submission(s): 4580
Problem Description
Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.
Input
The first line follows an integer T, the number of test data.
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)
Output
For each case, output "Case X: " (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.
Sample Input
1 10 10 0 5 2 7 5 4 3 8 7 7 2 8 6 3 5 0 1 3 1 1 9 4 0 1 0 3 5 5 5 5 1 4 6 3 1 5 7 5 7 3
Sample Output
Case 1: 4 0 0 3 1 2 0 1 5 1
Source
2012 ACM/ICPC Asia Regional Hangzhou Online
题意：
给你一个数组，多次询问，每一次询问区间里[l,r],有多少个数<=h?
分析：
离线树状数组
我们分别对操作排序，按照h的大小排序，对于最小的h来说，将<=h的数按下标加入到树状数组当中，则sum(r)-sum(l-1)就为答案。这题的核心就是在进行询问时，只有小于等于h的数在树状数组当中。
主席树+二分
主席数可以查出区间第k小的元素，我们二分这个k，找到第k小的元素<=h的最大的那一个即可。
离线树状数组
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 11;
const int mod = 1e9 + 7;
//树状数组只能计算A[1]开始的和，A[0]这个元素是不能用的。
const int MAXN=100000+5;//最大元素个数
int n,m;//元素个数
int c[MAXN];//c[i]==A[i]+A[i-1]+...+A[i-lowbit(i)+1]
//返回i的二进制最右边1的值
int lowbit(int i)
{return i&(-i);
}
//返回A[1]+...A[i]的和
ll sum(int x)
{ll sum = 0;while(x){sum += c[x];x -= lowbit(x);}return sum;
}//令A[i] += val
void add(int x, ll val)
{while(x <= n) //注意这里的n，是树状数组维护的长度{c[x] += val;x += lowbit(x);}
}
struct Node
{int val;int index;
} a[N];
bool cmp1(Node x,Node y)
{return x.val<y.val;
}
struct Option
{int l,r,w;int index;
} op[N];
bool cmp2(Option x,Option y)
{return x.w<y.w;
}
int ans[N];
int main()
{int T;scanf("%d",&T);int kase=0;while(T--){kase++;memset(c,0,sizeof(c));scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){scanf("%d",&a[i].val);a[i].index=i;}sort(a+1,a+n+1,cmp1);for(int i=1; i<=m; i++){scanf("%d%d%d",&op[i].l,&op[i].r,&op[i].w);op[i].l++;op[i].r++;op[i].index=i;}sort(op+1,op+m+1,cmp2);int top=1;for(int i=1; i<=m; i++){while(top<=n&&a[top].val<=op[i].w){add(a[top].index,1);top++;}ans[op[i].index]=sum(op[i].r)-sum(op[i].l-1);}printf("Case %d:\n",kase);for(int i=1;i<=m;i++){printf("%d\n",ans[i]);}}return 0;
}
主席树+二分
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll ;
const int oo=0x7f7f7f7f ;
const int maxn=1e5+7;
const int mod=1e9+7;
int t,n,m,cnt,root[maxn],a[maxn];
//cnt和root：主席树的总点数和每一个根
struct node
{int l,r,sum;
} T[maxn*25];
vector<int> v;
int getid(int x) //离散化
{return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
///单点修改
void update(int l,int r,int &x,int y,int pos)
{T[++cnt]=T[y],T[cnt].sum++,x=cnt;if(l==r)return;int mid=(l+r)/2;if(mid>=pos)update(l,mid,T[x].l,T[y].l,pos);elseupdate(mid+1,r,T[x].r,T[y].r,pos);
}
///查询区间（x，y）第k小
int query(int l,int r,int x,int y,int k)
{if(l==r)return l;int mid=(l+r)/2;int sum=T[T[y].l].sum-T[T[x].l].sum;if(sum>=k)return query(l,mid,T[x].l,T[y].l,k);elsereturn query(mid+1,r,T[x].r,T[y].r,k-sum);
}
int two_find(int x,int y,int k)
{int l=0,r=y-x+1;while(l<r){int mid=(l+r+1)>>1;if(v[query(1,n,root[x-1],root[y],mid)-1]<=k)l=mid;elser=mid-1;}return l;}
int main(void)
{scanf("%d",&t);int kase=0;while(t--){v.clear();cnt=0;kase++;scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){scanf("%d",&a[i]);v.push_back(a[i]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i=1; i<=n; i++)update(1,n,root[i],root[i-1],getid(a[i]));printf("Case %d:\n",kase);for(int i=1; i<=m; i++){int x,y,k;scanf("%d%d%d",&x,&y,&k);x++,y++;printf("%d\n",two_find(x,y,k));}}return 0 ;
}