【ZJOI2013 DAY1】K大数查询 --树套树水题

Description

时限：2s?
有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

对于每个询问回答k 大数是多少。

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。?

30%的数据n=m=1000?
100%的数据n,m≤50000，并且后7 个点的数据n，m 的范围从32000 到50000?
近似成等差数列递增。a≤b≤n,1 操作中|c|≤n,2 操作中|c|≤maxlongint

【分析】

树套树

外层权值树，内层区间树。

这样外层单点修改，内层区间修改比较方便好写。

注意点要动态构建，然后就很水了~

【代码】

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,b,a) for(int i=(b);i>=(a);--i)
#define INF (~0U>>3)
#define sf scanf
#define pf printf
#define ls (id<<1)
#define rs ((id<<1)|1)
#define Mid ((Left+Right)>>1)

#define MAXN 50010

int N,M;
int p,q;

struct SegNode{
	#define node SegNode
    node* lc;
    int sz;
    int lazy;
    node* rc;
    node(bool mark){
    	lc=rc=NULL;
    	sz=lazy=0;
    }
    node(){}
};
node* null=new node(true);
node Pool[MAXN*400];
node* New=Pool;
node* root[MAXN<<2];

inline node* Get(){
    New->lc=New->rc=null;
    New->sz=New->lazy=0;
    return New++;
}

inline void Read(int& x,bool mark=0){
    char tt=getchar();
    for(;tt<'0'||'9'<tt;tt=getchar()) if(tt=='-') mark=1;
    for(x=0;'0'<=tt&&tt<='9';x=(x<<1)+(x<<3)+tt-'0',tt=getchar());
    x=mark?-x:x;
}

inline void Init(){
    Read(N);
    Read(M);
}

inline void Insert(node* T,int Left,int Right){
    if(p<=Left&&Right<=q){
        T->sz+=(Right+1-Left);
        T->lazy++;
        return;
    }
    T->sz+=min(Right,q)+1-max(Left,p);
    if(T->lc==null) T->lc=Get();
    if(T->rc==null) T->rc=Get();
    if(!(q<Left||Mid<p)) Insert(T->lc,Left,Mid);
    if(!(q<Mid+1||Right<p)) Insert(T->rc,Mid+1,Right);
}

inline void Insert(int id,int Right,int loc){
    if(!root[id]) root[id]=Get();
    Insert(root[id],1,N);
    if(Left==Right) return;
    else if(loc<=Mid) Insert(ls,Mid,loc);
    else Insert(rs,Right,loc);
}

inline int Getsum(node* T,int Right){
	if(T==null) return 0;
    if(p<=Left&&Right<=q) return T->sz;
    int rt=(min(Right,p))*T->lazy;
    if(!(q<Left||Mid<p)) rt+=Getsum(T->lc,Mid);
    if(!(q<Mid+1||Right<p)) rt+=Getsum(T->rc,Right);
    return rt;
}

inline int Select(int id,int k){
	while(Left!=Right){
		int t=0;
        if(root[rs]) t=Getsum(root[rs],N);
        if(k<=t){
        	id=rs;Left=Mid+1;
        }
        else{
        	id=ls;Right=Mid;
        	k-=t;
        }
	}
	return Left;
}

inline void Solve(){
    int T,c;
    while(M--){
        Read(T);
        Read(p);
        Read(q);
        Read(c);
        if(T==1) Insert(1,N,c);
        else pf("%dn",Select(1,c));
    }
}

int main(){
	null->lc=null;
	null->rc=null;
    Init();
    Solve();
    return 0;
}