问题 H: Boring Counting
时间限制: 3 Sec 内存限制: 128 MB
题目描述
In this problem you are given a number sequence P consisting of N integer and Pi is the ith element in the sequence. Now you task is to answer a list of queries, for each query, please tell us among [L, R], how many Pi is not less than A and not greater than B( L<= i <= R). In other words, your task is to count the number of Pi (L <= i <= R, A <= Pi <= B).
输入
In the first line there is an integer T (1 < T <= 50), indicates the number of test cases.
For each case, the first line contains two numbers N and M (1 <= N, M <= 50000), the size of sequence P, the number of queries. The second line contains N numbers Pi(1 <= Pi <= 10^9), the number sequence P. Then there are M lines, each line contains four number L, R, A, B(1 <= L, R <= n, 1 <= A, B <= 10^9)
输出
For each case, at first output a line ‘Case #c:’, c is the case number start from 1. Then for each query output a line contains the answer.
样例输入 Copy
1
13 5
6 9 5 2 3 6 8 7 3 2 5 1 4
1 13 1 10
1 13 3 6
3 6 3 6
2 8 2 8
1 9 1 9
样例输出 Copy
Case #1:
13
7
3
6
9
题意：
给定一个长度为n的序列和m次询问，每次询问给出L,R,A,B，问在下标为[ L,R ] 的序列里，满足A<=X<=B的X有多少个。
思路：
如果我们知道A是第几个数，B是第几个数，就能计算出在A和B之间有多少个数。
对于求区间第K大的值，可以用主席树求；现在是知道值求该值是区间的第几个数，可以用二分来做。
需要注意判断一下A和B之间没有数的情况。
代码：
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>PLL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
#define I_int ll
#define x first
#define y second
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
char F[200];
inline void out(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0) putchar(F[--cnt]);
//cout<<" ";
}
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int inf=0x3f3f3f3f,mod=1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn=1e5+7,maxm=3e5+7;
const double PI = atan(1.0)*4;
int n,m;
int a[maxn];
vector<int>nums;
struct node{
int l,r,cnt;
}tr[maxn*20];
int root[maxn],idx;
int Find(int x){
return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
int build(int l,int r){
int p=++idx;
if(l==r) return p;
int mid=(l+r)>>1;
tr[p].l=build(l,mid);tr[p].r=build(mid+1,r);
return p;
}
int Insert(int p,int l,int r,int x){
int q=++idx;
tr[q]=tr[p];
if(l==r){
tr[q].cnt++;
return q;
}
int mid=(l+r)>>1;
if(x<=mid) tr[q].l=Insert(tr[p].l,l,mid,x);
else tr[q].r=Insert(tr[p].r,mid+1,r,x);
tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;
return q;
}
int qask(int q, int p, int l, int r, int k)
{
if (l == r) return r;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid=(l+r)>>1;
if (k <= cnt) return qask(tr[q].l, tr[p].l, l, mid, k);
else return qask(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
int main(){
int T=read();
for(int Case=1;Case<=T;Case++){
printf("Case #%d:
",Case);
nums.clear();idx=0;
memset(tr,0,sizeof tr);memset(root,0,sizeof root);
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();nums.push_back(a[i]);
}
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
root[0]=build(0,nums.size()-1);
for(int i=1;i<=n;i++)
root[i]=Insert(root[i-1],0,nums.size()-1,Find(a[i]));
while(m--){
int l=read(),r=read(),A=read(),B=read();
///int tmp=qask(root[r],root[l-1],0,nums.size()-1,k);区间第k大
int res=0;
bool flag=0;
int la=1,ra=r-l+1,resa=-1;
while(la<=ra){
int mid=(la+ra)>>1;
int tmp=qask(root[r],root[l-1],0,nums.size()-1,mid);
if(nums[tmp]>=A) ra=mid-1,resa=mid;
else la=mid+1;
}
if(resa==-1) flag=1;
else res=res-resa+1;
int lb=1,rb=r-l+1,resb=-1;
while(lb<=rb){
int mid=(lb+rb)>>1;
int tmp=qask(root[r],root[l-1],0,nums.size()-1,mid);
if(nums[tmp]<=B) lb=mid+1,resb=mid;
else rb=mid-1;
}
if(resb==-1) flag=1;
else res=res+resb;
if(flag) res=0;
///cout<<resa<<" "<<resb<<endl;
out(res);puts("");
}
}
return 0;
}