问题 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:\n",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; }
