[原创]第四届山东省赛 J Boring Counting [主席树]【数据结构】

[原创]第四届山东省赛 J Boring Counting [主席树]【数据结构】

2017-03-15 07:46:22 Tabris_ 阅读数：426

---

博客爬取于2020-06-14 22:41:12
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/62213988

---

题目链接 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2054
——————————————————————————————————————————
Boring Counting
Time Limit: 3000 MS Memory Limit: 32768 K
Total Submit: 70(22 users) Total Accepted: 6(6 users) Rating: Special Judge: No

Description
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).

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 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)

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

——————————————————————————————————————————

解题思路:

其实就是一个简单的主席树入门,奈何练习赛的时候刚学主席树不到2天,还没理解主席树.于是GG了

其实仔细想想啊,其实 和 SPOJ DQUERY 一样,而且更简单一点,
我们不需要删除操作,只需要保存所有的历史版本,然后找$rt[l] - rt[r]$之间在$\big[A,B\big]$区间的数的个数就行了

只需要离散化后,一次向树上更新即可,

但要注意查询的时候,
离散化A是大于等于A的第一个元素
离散化B是小于等于B的最后一个元素

附本题代码
————————————————————————————————————————————

# include <bits/stdc++.h>

using namespace std;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

/************************************************/
const int N = 5e4+7;

int a[N],b[N],sz;

int rt[N],ls[N*40],rs[N*40],sum[N*40],tot;
void build(int &rt,int l,int r){
    rt=++tot;
    sum[rt]=0;
    if(l>=r)return;
    int m=((r-l)>>1)+l;
    build(ls[rt],l  ,m);
    build(rs[rt],m+1,r);
}

void update(int &rt,int l,int r,int last,int pos){
    rt=++tot;
    ls[rt]=ls[last];
    rs[rt]=rs[last];
    sum[rt]=sum[last]+1;
    if(l>=r)return;
    int m=((r-l)>>1)+l;
    if(pos<=m) update(ls[rt],l  ,m,ls[last],pos);
    else       update(rs[rt],m+1,r,rs[last],pos);
}

int query(int rt,int last,int l,int r,int L,int R){
    if(L>R)return 0;
    if(L<=l&&r<=R)return sum[rt]-sum[last];
    int m=((r-l)>>1)+l;
    int ans=0;
    if(L<=m) ans+=query(ls[rt],ls[last],l  ,m,L,R);
    if(R> m) ans+=query(rs[rt],rs[last],m+1,r,L,R);
    return ans;
}

int lb(int x){
    return lower_bound(b+1,b+sz+1,x)-b;
}
map<int,int>mmp;
int main(){
    int _ = 1,kcase = 0,l,r,L,R,flag;
    scanf("%d",&_);
    while(_--){
        tot=0;mmp.clear();

        int n=read(),m=read();
        for(int i=1;i<=n;i++) b[i]=a[i]=read(),mmp[a[i]]=1;

        sort(b+1,b+n+1);
        sz = unique(b+1,b+n+1)-(b+1);
//        printf("sz = %d\n",sz);
//        for(int i=1;i<=sz;i++) printf("b[%d]=%d ",i,b[i]);puts("");

        build(rt[0],1,sz);

        for(int i=1;i<=n;i++)a[i]=lb(a[i]);
        for(int i=1;i<=n;i++)update(rt[i],1,sz,rt[i-1],a[i]);
//        printf("%d\n",lb(0));
        printf("Case #%d:\n",++kcase);
        while(m--){
            l=read(),r=read(),L=read(),R=read();
            if(L>R){puts("0");continue; }
            flag=0;
            if(!mmp[R])flag=1;
            if(R<b[1]) R=-1;    else R = lb(R)-flag;
            if(L>b[sz])L=1e9+77;else L = lb(L);

//            printf("%d  %d\n",L,R);
            printf("%d\n",query(rt[r],rt[l-1],1,sz,L,R));
        }
    }
    return 0;
}