[原创]第四届山东省赛 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]rt[l] - rt[r]之间在[A,B]\big[A,B\big]区间的数的个数就行了

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# 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;
}