山东第四届省赛： Boring Counting 线段树

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=3237

Problem H:Boring Counting

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 6 Solved: 2
[Submit][Status][Discuss]

Description

In this problem you are given a number sequence P consisting of N integer and P_i is the i^th 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 P_i is not less than A and not greater than B( L<= i <= R). In other words, your task is to count the number of P_i (L <= i <= R, A <= P_i <= B).

Input

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 P_i(1 <= P_i <= 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)

Output

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.

Sample Input

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

Sample Output

Case #1:

13

7

3

6

9

HINT

Source

山东省第四届ACM程序设计大赛2013.6.9

比赛的时候，没有头绪，今天别人说起划分树，想了一下，还真是可以做的。

但是要一点变形，这样的变形，让我已经看不清划分树的影子了。

划分树----求区间第K 小/大值

这道题是求区间求区间[l,r]中满足 A<=xi<=B; xi属于[l,r]。求xi的个数。

如何转化的呢？

枚举区间第k小数==A。此时能求出一个值 hxl

枚举区间第K小数==B，此时得到一个值 tom

显然满足tom>=hxl。

那在这范围的数，是不是就满足了 A<=xi<=B !~~

这么一说，其实好简单。为什么没有想到呢？划分树做的时候是求第 k 小的是什么什么数字，现在换了回来而已，

求的是某个数字是区间里面第几小。

其实有个问题就又来了，A,B在区间[l,r]未必存在，这该怎么办？？？？？

其实上面的说法，不严谨，（求的是某个数字是区间里面第几小。）应该说是求A的下届，B的上届值。

二分枚举，平均的时间会更小。在求下届和上届的过程中也要注意一些细节的问题、

 #include<cstdio>

 #include<iostream>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #define N 100010

 using namespace std; 

 int toleft[][N];

 int Tree[][N];

 int Sort[N]; 

 void build(int l,int r,int dep)

 {

     int mid=(l+r)/,sum=mid-l+,lpos,rpos,i;

     if(l==r) return ;

     for(i=l;i<=r;i++)

         if(Tree[dep][i]<Sort[mid]) sum--;

     lpos=l;

     rpos=mid+;

     for(i=l;i<=r;i++)

     {

         if(Tree[dep][i]<Sort[mid])

         {

             Tree[dep+][lpos++]=Tree[dep][i];

         }

         else if(Tree[dep][i]==Sort[mid] && sum>)

         {

             Tree[dep+][lpos++]=Tree[dep][i];

             sum--;

         }

         else

         {

             Tree[dep+][rpos++]=Tree[dep][i];

         }

         toleft[dep][i]=toleft[dep][l-]+lpos-l;

     }

     build(l,mid,dep+);

     build(mid+,r,dep+);

 } 

 int query(int L,int R,int l,int r,int dep,int k)

 {

     int mid=(L+R)/,newl,newr,cur;

     if(l==r) return Tree[dep][l];

     cur=toleft[dep][r]-toleft[dep][l-];

     if(cur>=k)

     {

         newl=L+toleft[dep][l-]-toleft[dep][L-];

         newr=newl+cur-;

         return query(L,mid,newl,newr,dep+,k);

     }

     else

     {

         newr=r+(toleft[dep][R]-toleft[dep][r]);

         newl=newr-(r-l-cur);

         return query(mid+,R,newl,newr,dep+,k-cur);

     }

 }

 int EF1(int l,int r,int num,int n) //枚举下届

 {

     int low=,right=r-l+,mid,tmp;

     mid=(low+right)/;

     while(low<right)

     {

         tmp=query(,n,l,r,,mid);

         if(tmp>=num)

         right=mid-;

         else low=mid; //！！！！

         mid=(low+right+)/; //!!! 加了一个1。

     }

     return low; 

 } 

 int EF2(int l,int r,int num,int n)

 {

     int low=,right=r-l+,mid,tmp;

     mid=(low+right)/;

     while(low<right)

     {

         tmp=query(,n,l,r,,mid);

         if(tmp>num)

         right=mid; //!!!

         else low=mid+;

         mid=(low+right)/; //木有加1

     }

     return low;

 } 

 int main()

 {

     int T,n,m,i,l,r,k,a,b,hxl,tom,qq;

     scanf("%d",&T);

     {

         for(qq=;qq<=T;qq++)

         {

             scanf("%d%d",&n,&m);

             memset(Tree,,sizeof(Tree));

             for(i=;i<=n;i++)

             {

                 scanf("%d",&Tree[][i]);

                 Sort[i]=Tree[][i];

             }

             sort(Sort+,Sort++n);

             build(,n,);

             printf("Case #%d:\n",qq);

             while(m--)

             {

                 scanf("%d%d%d%d",&l,&r,&a,&b);

                 hxl=query(,n,l,r,,);

                 if(a<=hxl) hxl=; //对临界条件的判断。如果A就是最小的，木有下届

                 else

                 {

                     hxl=EF1(l,r,a,n);

                     hxl++;

                 }

                 tom=query(,n,l,r,,r-l+);

                 if(b>=tom) tom=r-l+; //如果B是该区间[l,r]最大的，显然木有上届

                 else

                 {

                     tom=EF2(l,r,b,n);

                     tom--;

                 }

                 hxl=tom-hxl+;

                 printf("%d\n",hxl);

             }

         }

     }

     return ;

 }

巴特西