首页 > 代码库 > BZOJ3110: [Zjoi2013]K大数查询

BZOJ3110: [Zjoi2013]K大数查询

3110: [Zjoi2013]K大数查询

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1190  Solved: 568
[Submit][Status]

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

 



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

a<=b<=N

1操作中abs(c)<=N

2操作中abs(c)<=Maxlongint

题解:

线段树套线段树,一旦要动态开点就得传一大堆参数,幸好改了一个sb错误之后就A了。。。

外层为权值线段树,内层为区间线段树。

自己想一下基本上就知道是怎么回事儿了。。。

代码:

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #define inf 1000000000 12 #define maxn 50000+1000 13 #define maxm 500+100 14 #define eps 1e-10 15 #define ll long long 16 #define pa pair<int,int> 17 using namespace std; 18 inline int read() 19 { 20     int x=0,f=1;char ch=getchar(); 21     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();} 22     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();} 23     return x*f; 24 } 25 struct seg1{int lc,rc,tag,sum;}t[300*maxn]; 26 struct seg2{int l,r,rt;}tt[4*maxn]; 27 int n,m,tot; 28 void pushup(int k) 29 { 30     t[k].sum=t[t[k].lc].sum+t[t[k].rc].sum; 31 } 32 void update(int &k,int l,int r,int z) 33 { 34     if(!k)k=++tot; 35     t[k].tag+=z; 36     t[k].sum+=(r-l+1)*z; 37 } 38 void pushdown(int k,int l,int r) 39 { 40     if(!t[k].tag)return; 41     int mid=(l+r)>>1; 42     update(t[k].lc,l,mid,t[k].tag);update(t[k].rc,mid+1,r,t[k].tag); 43     t[k].tag=0; 44 } 45 void add(int &k,int l,int r,int x,int y) 46 { 47     if(!k)k=++tot; 48     int mid=(l+r)>>1; 49     if(l==x&&r==y){update(k,l,r,1);return;} 50     pushdown(k,l,r); 51     if(y<=mid)add(t[k].lc,l,mid,x,y); 52     else if (x>mid)add(t[k].rc,mid+1,r,x,y); 53     else  54     { 55         add(t[k].lc,l,mid,x,mid);add(t[k].rc,mid+1,r,mid+1,y); 56     } 57     pushup(k); 58 } 59 ll getsum(int k,int l,int r,int x,int y) 60 { 61     if(!k)return 0; 62     if(l==x&&r==y)return t[k].sum; 63     pushdown(k,l,r); 64     int mid=(l+r)>>1; 65     if(y<=mid)return getsum(t[k].lc,l,mid,x,y); 66     else if(x>mid)return getsum(t[k].rc,mid+1,r,x,y); 67     else return getsum(t[k].lc,l,mid,x,mid)+getsum(t[k].rc,mid+1,r,mid+1,y); 68 } 69 void build(int k,int x,int y) 70 { 71     int l=tt[k].l=x,r=tt[k].r=y, mid=(l+r)>>1; 72     if(l==r)return; 73     build(k<<1,l,mid);build(k<<1|1,mid+1,r); 74 } 75 void change(int k,int x,int y,int z) 76 { 77     int l=tt[k].l,r=tt[k].r, mid=(l+r)>>1; 78     add(tt[k].rt,1,n,x,y); 79     if(l==r)return; 80     if(z<=mid)change(k<<1,x,y,z);else change(k<<1|1,x,y,z); 81 } 82 int query(int k,int x,int y,int z) 83 { 84     int l=tt[k].l,r=tt[k].r, mid=(l+r)>>1; 85     if(l==r)return l; 86     ll tmp=getsum(tt[k<<1|1].rt,1,n,x,y); 87     if(tmp>=z)return query(k<<1|1,x,y,z); 88     else return query(k<<1,x,y,z-tmp); 89 } 90 int main() 91 { 92     freopen("input.txt","r",stdin); 93     freopen("output.txt","w",stdout); 94     n=read();m=read(); 95     build(1,1,n); 96     while(m--) 97     { 98         int ch=read(),x=read(),y=read(),z=read(); 99         if(ch==1)change(1,x,y,z);else printf("%d\n",query(1,x,y,z));100     }101     return 0;102 }
View Code

 

BZOJ3110: [Zjoi2013]K大数查询