首页 > 代码库 > BZOJ 3110: [Zjoi2013]K大数查询 [树套树]

BZOJ 3110: [Zjoi2013]K大数查询 [树套树]

2024-08-30 13:34:13   222人阅读

3110: [Zjoi2013]K大数查询

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 6050  Solved: 2007
[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

 

本题做法好多啊，人太弱先写权值线段树套区间线段树吧

蒟蒻无脑总结：树套树是一种二维数据结构，用来解决二维的信息修改和询问

本题两个信息，一段区间中保存数，求第k大

显然用一个区间数据结构一个可求排名的数据结构，可以用权值线段树和区间线段树

区间线段树在外层，维护增加数的信息好难啊

权值线段树在外层，每个节点放一颗区间线段树维护这个节点权值在区间中出现次数

修改...修改就行了啊

查询，在权值线段树上二分答案，只不过用的是[a,b]中的出现次数

复杂度nlog^2n

 

参考别人写的，好诡异啊，明明有范围那么大还有负数，不离散化也能A

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define m ((l+r)>>1)#define lc t[o].l#define rc t[o].r#define lson t[o].l,l,m#define rson t[o].r,m+1,rconst int N=5e4+5;typedef long long ll;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}    return x*f;}int n,Q,op,ql,qr,v;struct node{    int l,r;    ll sum,tag;}t[N*300];int sz;inline void merge(int o){    t[o].sum=t[lc].sum+t[rc].sum;}inline void paint(int &o,int l,int r,ll d){    if(!o) o=++sz;    t[o].sum+=(ll)(r-l+1)*d;    t[o].tag+=d; }inline void pushDown(int o,int l,int r){    if(t[o].tag){        paint(lson,t[o].tag);        paint(rson,t[o].tag);        t[o].tag=0;    }}void add(int &o,int l,int r,int ql,int qr,int d){    if(!o) o=++sz;    if(ql<=l&&r<=qr) paint(o,l,r,d);    else{        pushDown(o,l,r);        if(ql<=m) add(lson,ql,qr,d);        if(m<qr) add(rson,ql,qr,d);        merge(o);    }}ll query(int o,int l,int r,int ql,int qr){    if(!o) return 0;    if(ql<=l&&r<=qr) return t[o].sum;    else{        pushDown(o,l,r);        ll ans=0;        if(ql<=m) ans+=query(lson,ql,qr);        if(m<qr) ans+=query(rson,ql,qr);        return ans;    }}int rt[N<<2];void add2(int o,int l,int r,int ql,int qr,int v){    add(rt[o],1,n,ql,qr,1);    if(l==r) return;    if(v<=m) add2(o<<1,l,m,ql,qr,v);    else add2(o<<1|1,m+1,r,ql,qr,v);}ll query2(int o,int l,int r,int ql,int qr,int k){    if(l==r) return l;    ll rsize=query(rt[o<<1|1],1,n,ql,qr);    if(rsize>=k) return query2(o<<1|1,m+1,r,ql,qr,k);    else return query2(o<<1,l,m,ql,qr,k-rsize);}int main(){    //freopen("in.txt","r",stdin);    n=read();Q=read();    while(Q--){        op=read();ql=read();qr=read();v=read();        if(op==1) add2(1,1,n,ql,qr,v);        else printf("%lld\n",query2(1,1,n,ql,qr,v));    }}

 

BZOJ 3110: [Zjoi2013]K大数查询 [树套树]


联系
我们