题意：给一个数组，每次询问输出在区间[L,R]之间小于H的数字的个数。
此题可以使用划分树在线解决。
划分树可以快速查询区间第K小个数字。逆向思考，判断小于H的最大的一个数字是区间第几小数，即是答案。这一步可以使用二分搜索上界。时间复杂度是O（logn*logn)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#define MAXN 100005
using namespace std;
struct Divide_Tree
{
][MAXN];
][MAXN];
void build(int c,int L,int R)
{
,lsame=mid+-L,lp=L,rp=mid+;
for(int i=L; i<mid; ++i)
if(sorted[i]<sorted[mid]) lsame--;
for(int i=L; i<=R; ++i)
{
;
];
if(dat[c][i]<sorted[mid])
{
dat[c+][lp++]=dat[c][i];
toleft[c][i]++;
}
else if(dat[c][i]>sorted[mid])
dat[c+][rp++]=dat[c][i];
else
{
if(lsame)
{
lsame--;
toleft[c][i]++;
dat[c+][lp++]=sorted[mid];
}
][rp++]=sorted[mid];
}
}
if(L==R) return ;
build(c+,L,mid);
build(c+,mid+,R);
}
int query(int c,int L,int R,int ql,int qr,int k)
{
if(L==R) return dat[c][L];
;
int la,lb,ra,rb;
;
];
lb=toleft[c][qr];
ra=ql-L-la;
rb=qr+-L-lb;
int s=lb-la;
,L,mid,L+la,L+lb-,k);
,mid+,R,mid++ra,mid+rb,k-s);
}
};
Divide_Tree tree;
int n;
int Bsearch(int low,int high,int key,int ql,int qr)
{
)>>;
while(low<high)
{
,,n,ql,qr,mid)<=key) low=mid;
;
mid=(low+high+)>>;
}
,,n,ql,qr,mid)<=key) return mid;
;
}
int main()
{
;
int q;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
; i<=n; ++i)
{
scanf("%d",&tree.arr[i]);
tree.sorted[i]=tree.dat[][i]=tree.arr[i];
}
sort(tree.sorted+,tree.sorted+n+);
tree.build(,,n);
int l,r,k;
printf("Case %d:\n",++kase);
while(q--)
{
scanf("%d%d%d",&l,&r,&k);
l++;
r++;
,r-l+,k,l,r);
) printf("0\n");
else printf("%d\n",p);
}
}
;
}
另外，此题有更高效的算法。 未完待续。
此题也可以离线解决。
首先考虑单次查询整个区间小于某个数的数字个数的思路，我们可以统计每个数字出现的次数，然后利用前缀和快速计算小于该数的数字个数。
如果是查询部分区间[L,R]小于某数x的数字个数的话，答案为 区间[1,R]小于x的数字个数 减去 区间[1,L-1]小于x的数字个数。那么如何计算区间[1,S]内小于x的数字个数呢。
每出现一个数字v就在第v个位置加一即可。统计小于x的数字个数即计算前x个位置的和，这里需要求和，也用到了修改，显然用树状数组更高效。这样当枚举到第i个数字时，求区间[1,i]内小于x的数字个数即此时计算前x个数字的和。
由于这里数字较大，数组下标存不下，所以需要离散化。
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
#include<cstdio>
#include<algorithm>
#define MAXN 100005
using namespace std;
int n,m,cn;
map<int,int> has;
struct BIT
{
int dat[MAXN];
void clear()
{
memset(dat,,sizeof(dat));
}
int lowbit(int x)
{
return -x&x;
}
void add(int x,int v)
{
while(x<=cn)
{
dat[x]+=v;
x+=lowbit(x);
}
}
int sum(int x)
{
;
)
{
s+=dat[x];
x-=lowbit(x);
}
return s;
}
};
struct Segment
{
int num,left,right,high;
int presum,ans;
Segment (int a,int b,int c,int d):num(a),left(b),right(c),high(d) {}
bool operator < (const Segment &p) const
{
return left<p.left;
}
};
bool cmp(Segment a,Segment b)
{
return a.num<b.num;
}
vector<Segment> vec;
vector<int> numb;
int arr[MAXN];
vector<int> posL[MAXN],posR[MAXN];
BIT tree;
int main()
{
int T;
scanf("%d",&T);
;
while(T--)
{
scanf("%d%d",&n,&m);
numb.clear();
; i<=n; ++i)
{
scanf("%d",&arr[i]);
numb.push_back(arr[i]);
posL[i+].clear();
posR[i+].clear();
}
vec.clear();
; i<m; ++i)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x++;
y++;
numb.push_back(z);
vec.push_back(Segment (i,x,y,z));
}
sort(vec.begin(),vec.end());
; i<vec.size(); ++i)
{
posL[vec[i].left].push_back(i);
posR[vec[i].right].push_back(i);
}
has.clear();
cn=;
sort(numb.begin(),numb.end());
; i<numb.size(); ++i)
if(!has[numb[i]]) has[numb[i]]=++cn;
tree.clear();
; i<=n; ++i)
{
; j<posL[i].size(); ++j)
{
int u=posL[i][j];
int v=has[vec[u].high];
vec[u].presum=tree.sum(v);
}
tree.add(has[arr[i]],);
; j<posR[i].size(); ++j)
{
int u=posR[i][j];
int v=has[vec[u].high];
vec[u].ans=tree.sum(v)-vec[u].presum;
}
}
sort(vec.begin(),vec.end(),cmp);
printf("Case %d:\n",++kase);
; i<vec.size(); ++i)
printf("%d\n",vec[i].ans);
}
;
}
离线的另一种思路。
我们可以按照每个数的大小顺序插入到树状数组中，同时按照高度的大小顺序查询。
这样将所有数和高度一起存入数组并从小到大排序。这样遇到数就在树状数组该数字的位置加一，遇到查询就对该区间求和，这样可以保证在查询的时候树状数组上被插入的数都是小于x的。
注意，排序的时候如果数的大小和查询高度大小一样，则查询放在后面。
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
#include<cstdio>
#include<algorithm>
#define MAXN 100005
using namespace std;
int n,m;
struct BIT
{
int dat[MAXN];
void clear()
{
memset(dat,,sizeof(dat));
}
int lowbit(int x)
{
return -x&x;
}
void add(int x,int v)
{
while(x<=n)
{
dat[x]+=v;
x+=lowbit(x);
}
}
int sum(int x)
{
;
)
{
s+=dat[x];
x-=lowbit(x);
}
return s;
}
};
struct Segment
{
int num,dat,left,right;
int ans;
Segment(,,,):num(a),dat(b),left(c),right(d) {}
bool operator <(const Segment &p) const
{
return dat<p.dat||(dat==p.dat&&num>p.num);
}
};
bool cmp(Segment a,Segment b)
{
return a.num<b.num;
}
vector<Segment> vec;
BIT tree;
int main()
{
;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
vec.clear();
; i<=n; ++i)
{
int t;
scanf("%d",&t);
vec.push_back(Segment(i,t));
}
; i<m; ++i)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x++;
y++;
vec.push_back(Segment(-m+i,z,x,y));
}
sort(vec.begin(),vec.end());
tree.clear();
; i<vec.size(); ++i)
{
) tree.add(vec[i].num,);
);
}
sort(vec.begin(),vec.end(),cmp);
printf("Case %d:\n",++kase);
; i<vec.size(); ++i)
) printf("%d\n",vec[i].ans);
else break;
}
;
}