[ZJOI 2013] bzoj3110 K大数查询 【树套树】

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

Sample Output

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

树套树入门题 算法不难？但是第一次写的话感觉不好写。。orz。。

知识点很多啊。。

外层权值线段树。。内层区间线段树。。懒惰标记永久化

引自表姐博客

"""

第一想法是外层线段树内层treap名次树。。嗯这样写的话大概就是个暴力 ?= = TLE不说。。内存估计都要爆（即使有512M内存）

后来发现这玩意其实线段树套线段树就可以解决 于是我就orz了 = =

外层不是区间。。外层写权值线段树（就是每次add进去的值） 内层套区间（add进去的值在哪些地方） 然后就可以放lazy标记了 每次更新的时候lazy++

当然好像普通的lazy标记只能卡着过。。所以我们可以放永久化标记……（其实直接转zkw最好……就是那玩意太高端了弱比表示不会……）

永久化标记就是lazy不pushdown 直接在询问的时候把lazy加在答案里（……语死早）

对于每个询问 先查找右边的总数cnt 如果右边总数大于等于c就在右子树查询第c大的 如果不够就在左子树查询第c-cnt大的。。



内存的问题呢。。外层线段树开个4*maxn的root数组就可以了。。然后内层根本不用建出来 每次动态分配1下就好了（当然还是先把内存申请好 = =动态申请太慢了）

内层线段树的空间我算出来是17600000这样。。就是4 * (logn)^2 * 4 *n = =反正512M嘛应该都是够用的。。

"""

贴表姐代码（勿交，因为数据加强了。。）

    #include <cstdio>  
    #include <iostream>  
      
    #define lch (u << 1)  
    #define rch (u << 1 | 1)  
      
    using namespace std;  
      
    int ReadInt()  
    {  
        int x = 0,sign = 1; char ch = getchar();  
        while(ch < '0' || ch > '9') { if(ch == '-') sign = -1; ch = getchar(); }  
        while(ch >= '0' && ch <= '9') {x = x*10 + ch-'0'; ch = getchar();}  
        return x*sign;  
    }  
      
    const int maxn = 50000+5;  
    const int maxm = 360 * maxn;  
      
    int N,M;  
    int root[3*maxn]; // 外层线段树   
      
    int sum[maxm],lazy[maxm],lc[maxm],rc[maxm]; // 内层线段树   
    int size;  
      
    void insert(int u,int l,int r,int L,int R)  
    { // 内层线段树   
        if(l == L && r == R)   
        {  
            sum[u] += r-l+1;  
            lazy[u]++; return;  
        }  
          
        int mid = (l + r) >> 1;  
          
        if(R <= mid) insert(lc[u] ? lc[u] : lc[u] = ++size,l,mid,L,R);  
        else if(L > mid) insert(rc[u] ? rc[u] : rc[u] = ++size,mid+1,r,R);  
        else  
        {  
            insert(lc[u] ? lc[u] : lc[u] = ++size,mid);  
            insert(rc[u] ? rc[u] : rc[u] = ++size,R);  
        }  
          
        sum[u] += R - L + 1;  
    }  
      
    void add(int u,int R,int x)    
    { // 外层线段树  
        insert(root[u] ? root[u] : root[u] = ++size,1,R);  
        if(l == r) return;  
          
        int mid = (l + r) >> 1;  
          
        if(x <= mid) add(lch,R,x);  
        else add(rch,x);  
    }  
      
    int count(int u,int R)  
    { // 内层线段树   
        if(l == L && r == R) return sum[u];  
          
        int mid = (l + r) >> 1,ans = 0;  
          
        if(R <= mid) ans = count(lc[u],R);  
        else if(L > mid) ans = count(rc[u],R);  
        else  
        {  
            ans += count(lc[u],mid);  
            ans += count(rc[u],R);  
        }   
        ans += (R - L + 1) * lazy[u];  
          
        return ans;  
    }  
      
    int query(int u,int x)  
    { // 外层线段树   
        if(l == r) return l;  
          
        int mid = (l + r) >> 1;  
          
        int cnt = count(root[rch],R);  
        if(cnt >= x) return query(rch,x);  
        else return query(lch,x - cnt);  
    }  
      
    int main()  
    {  
        N = ReadInt(); M = ReadInt();  
          
        int type,a,b,c;  
        while(M--)  
        {  
            type = ReadInt(); a = ReadInt(); b = ReadInt(); c = ReadInt();  
            if(type == 1) add(1,c);  
            else printf("%dn",query(1,c));  
        }  
          
        return 0;  
    }  

（编辑：南平站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!