bzoj 3110 [Zjoi2013]K大数查询-布布扣-bubuko.com

3110: [Zjoi2013]K大数查询

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 13159 Solved: 4067
[Submit][Status][Discuss]

Description

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

Input

第一行N，M
接下来M行，每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output

1
2
1

HINT

【样例说明】

第一个操作后位置 1 的数只有 1 ，位置 2 的数也只有 1 。第二个操作后位置 1

的数有 1 、 2 ，位置 2 的数也有 1 、 2 。第三次询问位置 1 到位置 1 第 2 大的数是

1 。第四次询问位置 1 到位置 1 第 1 大的数是 2 。第五次询问位置 1 到位置 2 第 3

大的数是 1 。‍

N,M<=50000,N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中c<=Maxlongint

本题恶心的地方是还有负数。。。还有树套树的空间需要很大

本题常见的两种做法：

1. 权值线段树套区间线段树，时间复杂度可以做到$O(n(logn)^2)$

由于常数较大，所以在区间线段树里面的标记我们就不下放了（标记永久化）。

每个权值线段树代表的区间都是一个值的范围，区间线段树表示这个值范围内的数在数组里面的分布情况。

这样待会我们要查找某个下标区间内有几个值在[l,r]范围内的数，我们就可以直接去这个区间线段树上查询了。

附树套树代码：

 1 #include<bits/stdc++.h>
 2 using namespace std; 
 3 #define mid (l+r)/2  
 4 #define LL  long long  
 5 int const N=600000+10;  
 6 int n,m,rt[N*10],sum,lc[N*20],rc[N*20];  
 7 LL s[N*20],tg[N*20]; 
 8 int read(){
 9     int x=0,w=0; char c=0;  
10     while (!isdigit(c)) w=w||(c==‘-‘),c=getchar();  
11     while (isdigit(c)) x=x*10+(c^48),c=getchar();  
12     if(w) x=-x; 
13     return x;  
14 }
15 void insert(int &x,int l,int r,int ll,int rr ){
16     if(!x) x=++sum;  
17     if(ll<=l && r<=rr){
18         tg[x]++;  
19         s[x]+=(r-l+1);  
20         return;  
21     }
22     if(ll<=mid) insert(lc[x],l,mid,ll,rr);  
23     if(rr>mid)  insert(rc[x],mid+1,r,ll,rr);  
24     s[x]=s[lc[x]]+s[rc[x]]+tg[x]*(r-l+1);  
25 }  
26 void update(int x,int l,int r,int a,int b,int c){
27     insert(rt[x],1,n,a,b);  
28     if(l==r) return;  
29     if(c<=mid) update(x<<1,l,mid,a,b,c);  
30     else update(x<<1|1,mid+1,r,a,b,c);  
31 }
32 LL  ask(int x,int l,int r,int ll,int rr){
33     if(!x) return 0;  
34     if(ll<=l && r<=rr)  return s[x];  
35     LL lnum=0,rnum=0;  
36     if(ll<=mid) lnum=ask(lc[x],l,mid,ll,rr); 
37     if(rr>mid)  rnum=ask(rc[x],mid+1,r,ll,rr);  
38     return lnum+rnum+tg[x]*(min(r,rr)-max(ll,l)+1);  
39 }
40 int query(int x,int l,int r,int a,int b,int c){
41     if(l==r) return l;  
42     LL k=ask(rt[x<<1],1,n,a,b);
43     if(k>=c) return query(x<<1,l,mid,a,b,c);  
44     else return query(x<<1|1,mid+1,r,a,b,c-k);  
45 }
46 int main(){
47     //freopen("testdata.in","r",stdin); 
48     //freopen("std.out","w",stdout);  
49     scanf("%d%d",&n,&m); 
50     while (m--){
51         int t,a,b,c; 
52         t=read(); a=read(); b=read(); c=read();  
53         //scanf("%d%d%d%d",&t,&a,&b,&c);  
54         if(t==1){
55             c=n+c;  
56             //cout<<c<<endl; 
57             c=2*n-c; 
58             //cout<<c<<endl;     
59             update(1,0,2*n,a,b,c);  
60         }else {
61             printf("%d\n",2*n-query(1,0,2*n,a,b,c)-n);  
62         }
63     } 
64     return 0; 
65 }

View Code

2.整体二分

bzoj 3110 [Zjoi2013]K大数查询

原文：https://www.cnblogs.com/ZJXXCN/p/11374616.html