[BZOJ3110][Zjoi2013]-K大数查询-树套树

说在前面

mmp，写这道题我真是拒绝的
第一次写树套树，从上午9点写到下午三点半，先是自己没想清楚，yy了个时间复杂度会炸的写法。后来重新写了一个可以过的算法，然而又被数据坑= =#

题目

BZOJ3110传送门
洛谷P3332传送门

题目描述

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

输入输出格式

输入格式：
第一行N，M接下来M行，每行形如1 a b c或2 a b c

输出格式：
输出每个询问的结果

输入输出样例

输入样例#1：
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

解法

树套树
比较容易想清楚的是，一棵线段树只能维护一维的信息
如果一棵线段树以值域来建树，那么这棵树就无法维护下标（位置），同理其他

但是这个题需要区间第K大，位置信息和值域信息都需要保存，因此使用树套树。主树维护值域，小树维护下标（位置），Query和Modify都需要写两个。注意这棵树套树需要动态开点。然后呢，这里是不能主树维护下标而小树维护值域的，如果这样写的话，主树没有办法用永久化标记，要写Pushdown的话复杂度也无法保证（会一层层的往下push）

然后有个比较坑的地方，因为N和M都是50000的规模，那么me可以每次都使区间[1,50000]加上同一个数c，数字c出现的次数就会超过int，这里就需要使用unsigned int或者long long。
另外，针对这个数据，直接用int读入，在查询的时候遇见nd为NULL直接return N也可以过。这样会比使用long long快两秒左右

下面是自带大常数的代码

/************************************************************** Problem: 3110 User: Izumihanako Language: C++ Result: Accepted Time:9160 ms Memory:286396 kb ****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

int N,M,upN,downN,a,b ;
long long c ;

struct downNode{//小树代表下标 
    int tag ;
    long long cnt ;
    downNode *ls,*rs ;
    void init( ){
        cnt = tag = 0 ;
    }
}dw[50005*17*16],*tdw = dw ;

struct upNode{//大树代表值域 
    upNode *ls,*rs ;
    downNode *down ;
    void init(){
        down = ++tdw ;
        down->init() ;
    }
}uw[100005*17],*tuw = uw,*root ;

void up_Newnode( upNode *&nd ){
    nd = ++tuw ;
    nd->init() ;
}

void down_Newnode( downNode *&nd ){
    nd = ++tdw ;
    nd->init() ;
}

void down_Update( downNode *nd,int lf,int rg ){
    if( !nd->ls ) nd->ls = ++tdw,tdw->init() ;
    if( !nd->rs ) nd->rs = ++tdw,tdw->init() ;
    nd->cnt = nd->ls->cnt + nd->rs->cnt + 1LL * nd->tag * ( rg - lf + 1 ) ;
}

void downAdd( downNode *&nd,int rg,int L,int R ){
    if( !nd ) down_Newnode( nd ) ;
    if( L <= lf && rg <= R ){
        nd->cnt += ( rg - lf + 1 ) ;
        nd->tag ++ ; return ;
    }
    int mid = ( lf + rg ) >> 1 ;
    if( L <= mid ) downAdd( nd->ls,lf,mid,L,R ) ;
    if( R >  mid ) downAdd( nd->rs,mid+1,rg,R ) ;
    down_Update( nd,rg ) ;
}

long long downQuery( downNode *nd,int R ){
    if( !nd ) return 0 ;
    if( L <= lf && rg <= R ) return nd->cnt ;
    int mid = ( lf + rg ) >> 1 ;
    long long rt = 1LL * ( min( R,rg ) - max( L,lf ) + 1 ) * nd->tag ;
    if( L <= mid ) rt += downQuery( nd->ls,R ) ;
    if( R >  mid ) rt += downQuery( nd->rs,R ) ;
    return rt ;
}

void upAdd( upNode *&nd,int pos ){
    if( !nd ) up_Newnode( nd ) ;
    downAdd( nd->down,1,b ) ;
    if( lf == rg ) return ;
    int mid = ( lf + rg ) >> 1 ;
    if( pos <= mid ) upAdd( nd->ls,pos ) ;
    if( pos >  mid ) upAdd( nd->rs,pos ) ;
}

int upQuery( upNode *nd,long long K ){
    if( lf == rg ) return lf - N ;
    //if( !nd ) return N ;
    int mid = ( lf + rg ) >> 1 ;
    long long Rcnt = ( nd->rs ? downQuery( nd->rs->down,b ) : 0 ) ;
    if( K <= Rcnt ) return upQuery( nd->rs,K ) ;
    else            return upQuery( nd->ls,K - Rcnt ) ;
}

void solve(){
    for( int i = 1,o ; i <= M ; i ++ ){
        scanf( "%d%d%d%lld",&o,&a,&b,&c ) ;
        switch(o){
            case 1 :{
                upAdd( root,c + N ) ;
                break;
            }
            case 2 :
                printf( "%dn",upQuery( root,c ) ) ;
        }
    }
}

int main(){
    scanf( "%d%d",&N,&M ) ;
    upN = N + N ; downN = N ;
    solve() ;
}