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
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
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,r
const int N=5e4+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
} int n,Q,op,ql,qr,v;
struct node{
int l,r;
ll sum,tag;
}t[N*];
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+)*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=;
}
}
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 ;
if(ql<=l&&r<=qr) return t[o].sum;
else{
pushDown(o,l,r);
ll ans=;
if(ql<=m) ans+=query(lson,ql,qr);
if(m<qr) ans+=query(rson,ql,qr);
return ans;
}
} int rt[N<<];
void add2(int o,int l,int r,int ql,int qr,int v){
add(rt[o],,n,ql,qr,);
if(l==r) return;
if(v<=m) add2(o<<,l,m,ql,qr,v);
else add2(o<<|,m+,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<<|],,n,ql,qr);
if(rsize>=k) return query2(o<<|,m+,r,ql,qr,k);
else return query2(o<<,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==) add2(,,n,ql,qr,v);
else printf("%lld\n",query2(,,n,ql,qr,v));
}
}