题意:
有n个位置,每个位置可以看做一个集合,现在要求你实现一个数据结构支持以下功能:
1:在a-b的集合中插入一个数
2:询问a-b集合中所有元素的第k大.
SOL:
调得火大! 李建说数据结构题能锻炼人,然而我的水平还是太低啊!每次调这种题到最后往往都会变成找不同...日狗!
树套树的第一题,但是是权值线段树套区间线段树,与心中真正的树套树还是有一点差距-----线段树套平衡树(一直打不完..卡死在不知什么地方).
对于权值线段树套区间线段树的想法,我们可以这么来看,先考虑在一个序列上询问第k大(不是这个序列的区间,也没有修改),那么我们可以通过线段树维护的两个区间的数的个数----权值线段树,维护插入的数,像我们搞逆序对的那个线段树-------来查询.当我们带上插入操作,那么我们可以在这权值线段树上维护一棵区间线段树,维护的是在外层维护的权值范围内,相应位置的个数. 仔细想仔细想仔细体会.非常有意思.
带上查询大概就明白了,当我们要查询一个区间(a,b)的第k大,我们想知道的信息有什么呢?有哪些数,这些数在这个区间出现了多少次. 那么这棵线段树可以很好地实现,查询右儿子即在mid---n这些数在a,b上出现了多少次,如果小于k,那么显然这个数只可能在1-mid间,我们只要查询左子树即可.
这样建树似乎很耗空间,至于省空间的方法,以及无比奇妙的分治方法,以及秒杀一切的套平衡树方法,都一一去实现吧.
CODE:
代码还是很短的,但是两棵线段树之间的逻辑关系,以及各种点,让调试变得无比困难,所以要一次打对,这也是代码能力的体现吧
/*==========================================================================
# Last modified: 2016-02-23 19:07
# Filename: 3110.cpp
# Description:
==========================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define maxn 15000000
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
int sum[maxn],ch[maxn][2],v[maxn],lazy[maxn],root[maxn];
int L,R,m,n,cnt=0;
//void pushup(int node,int l,int r){sum[node]=sum[ch[node][1]]+sum[ch[node][0]]+lazy[node]*(r-l+1);}
int _count(int node,int l,int r){
if (L<=l && r<=R) return sum[node];
int mid=rs(l,r),t=0;
if (L<=mid) t+=_count(ch[node][0],l,mid);
if (R>mid) t+=_count(ch[node][1],mid+1,r);
return t+lazy[node]*(min(r,R)-max(L,l)+1);
}
int query(int node,int l,int r,int k){
if (l==r) return l;
int mid=rs(l,r),lc=ls(node,0),rc=lc|1;
int t=_count(root[lc],1,n);
if (t>=k) query(lc,l,mid,k);
else query(rc,mid+1,r,k-t);
}
void updata(int &o,int l,int r){
if (!o) o=++cnt;
if (L<=l && r<=R) {sum[o]+=r-l+1; lazy[o]++; return ;}
int mid=rs(l,r);
if (L<=mid) updata(ch[o][0],l,mid);
if (R>mid) updata(ch[o][1],mid+1,r);
//pushup(o,l,r);
sum[o]=sum[ch[o][1]]+sum[ch[o][0]]+lazy[o]*(r-l+1);
}
void insert(int node,int l,int r,int x){
//if (root[node]==0) root[node]=++cnt;
updata(root[node],1,n);
if (l==r) return;
int mid=rs(l,r),lc=ls(node,0),rc=lc|1;
if (x<=mid) insert(lc,l,mid,x);
else insert(rc,mid+1,r,x);
}
int main(){
read(n); read(m);
memset(root,0,sizeof(root));
FORP(i,1,m){
int flag,x,y;
int k;
read(flag); read(L); read(R); read(k);
if (flag==1) k=n-k+1,insert(1,1,n,k);
else printf("%d\n",n-query(1,1,n,k)+1);
}
}