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

发布时间：2020-12-14 01:31:59 所属栏目：大数据来源：网络整理

导读：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

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

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

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;  
    }

上面代码风格很好。。可以读懂。。然后给一份glk优化过的代码【可过】（部分非递归优化）

#include <cstdio>  
  
const int Maxn = 50000 + 10,MS = Maxn << 8;  
int root[Maxn << 2],ls[MS],rs[MS],tot,M;  
long long Cnt[MS],ly[MS];  
//线段树的外层为权值，内层为区间  
  
int Ina; char Inc; bool InSign;  

inline int geti() 
{  
    InSign = 0;  
    while (Inc = getchar(),Inc < '0' || Inc > '9') InSign |= Inc == '-';  
    Ina = Inc - '0';  
    while (Inc = getchar(),Inc >= '0' && Inc <= '9') Ina = (Ina << 3) + (Ina << 1) + Inc - '0';  
    if (InSign) Ina = -Ina;  
    return Ina;  
}  
  
void Insert(int &u,int x,int y) {  //内层线段树 
    if (!u) u = ++tot; 
    if (l >= x && r <= y) {  
        Cnt[u] += r - l + 1;  
		 ++ly[u];//永久化懒惰标记 
		 return;  
    }  
    int mid = (l + r) >> 1;  
    if (y <= mid) Insert(ls[u],x,y);  
    else if (x > mid) Insert(rs[u],mid + 1,y);  
    else {  
        Insert(ls[u],mid);  
        Insert(rs[u],y);  
    }  
    Cnt[u] += y - x + 1;  
}
  
void add(int x,int y,int val) {  //外层线段树 权值线段树 
    int l = 1,r = N,u = 1,mid;  
    while (true) {  
        Insert(root[u],y);//  
        if (l == r) break;  //边界 
        mid = (l + r) >> 1; u <<= 1;  
        if (val <= mid) r = mid;  
        else l = mid + 1,u |= 1;  
    }  
}  
  
long long Count(int u,int y) {  
    if (l >= x && r <= y) return Cnt[u];  
    int mid = (l + r) >> 1; long long ans = 0;  
    if (y <= mid) ans = Count(ls[u],y);  
    else if (x > mid) ans = Count(rs[u],y);  
    else ans = Count(ls[u],mid) + Count(rs[u],y);  
    ans += (y - x + 1) * ly[u];  
    return ans;  
}  
  
int query(int x,long long val) {  
    int l = 1,u = 1; long long tmp;  
    while (true) {  
        if (l == r) return l;  
        mid = (l + r) >> 1;  
        tmp = Count(root[u << 1 | 1],y);  
        if (tmp >= val) l = mid + 1,u = u << 1 | 1;  
        else r = mid,u = u << 1,val -= tmp;  
    }  
}  
  
int main() {  
    N = geti(),M = geti();  
    int type,b; long long c;  
    while (M--) {  
        type = geti(),a = geti(),b = geti(),c = geti();  
        if (type < 2) add(a,c);  
        else printf("%dn",query(a,c));
    }  
    return 0;  
}

好像还有其他做法。。暂时先贴这个。。什么CDQ分治整体二分我有空再去看qwq

我的代码比较丑=。=

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
int Ina; char Inc; bool InSign;  
inline int read() 
{  
    InSign = 0;  
    while (Inc = getchar(),Inc >= '0' && Inc <= '9') Ina = (Ina << 3) + (Ina << 1) + Inc - '0';  
    if (InSign) Ina = -Ina;  
    return Ina;  
} 
int n,m;
const int Maxn = 50000 + 10,tot;  
long long cnt[MS],ly[MS];  
//线段树的外层为权值，内层为区间  
void insert(int& u,int y)
{
	if(!u)u = ++tot;
	if(l>=x&&r<=y){	cnt[u] += r-l+1;++ly[u];return;}
	int mid = (l+r)>>1;
	if(y<=mid)insert(ls[u],y);  
	else if(x>mid)insert(rs[u],y);
	else
	{
		insert(ls[u],mid);
		insert(rs[u],y);
	}
	cnt[u] += y - x + 1;
}
/*
void add(int x,LL v)
{
	insert(root[u] ? root[u] : root[u] = ++size,n,R);
	if(l==r) return;
	int mid = (l+r)>>1;
	if(x<=mid)add(u<<1,x);
	else add(u<<1|1,x);
}
*/
void add(int x,int v)
{
	int l=1,r=n,u=1,mid;
	while(true)
	{
		insert(root[u],y);
		if(l==r)break;
		mid = (l+r)>>1;u<<=1;
		if(v<=mid)r = mid;
		else l = mid+1,u|=1;
	}
}
LL Count(int u,int y)
{
	if(l>=x&&r<=y)return cnt[u];
	int mid = (l+r)>>1;LL ans = 0;
	if(y<=mid)ans = Count(ls[u],y);
	else if(x>mid)ans = Count(rs[u],y);
	else ans = Count(ls[u],y);
	ans += (y-x+1)*ly[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 query(int x,LL v)
{
	int l = 1,r = n,u = 1;LL tmp;
	while(true)	
	{
		if(l==r)return l;
		mid = (l+r)>>1;
		tmp = Count(root[u<<1|1],y);
		if(tmp>=v)l=mid+1,u=u<<1|1;
		else r=mid,u=u<<1,v-=tmp;
	}
}
int main(void)
{
	n = read(),m = read();
	int type,b;LL c;
	for(int i=1;i<=m;i++)	
	{
		type = read(),a = read(),b = read(),c = read();
		if(type == 1)add(a,c);
		else printf("%dn",c));
	}
	return 0;
}

下面是其他解法。。

STL暴力大法 http://blog.csdn.net/qq_21110267/article/details/44514709

#include <cstdio>  
#include <vector>  
#include <algorithm>  
using namespace std;  
const int maxn = 50000 + 10;  
  
struct opt {  
    int i,k,c;  
    bool operator < (const opt& rhs) const {  
        if(c == rhs.c) return i < rhs.i;  
        return c > rhs.c;  
    }  
}A[maxn];  
  
vector<opt> T;  
int ID[maxn];  
bool ins[maxn];  
  
int main()  
{  
    int n,m;  
    scanf("%d %d",&n,&m);  
    for(int i = 1; i <= m; i++) {  
        int k,c;  
        scanf("%d %d %d %d",&k,&a,&b,&c);  
        A[i] = (opt){i,c};  
        if(k == 1) T.push_back(A[i]);  
    }  
    sort(T.begin(),T.end());  
    for(int i = 0; i < T.size(); i++) ID[T[i].i] = i;  
    for(int i = 1; i <= m; i++)  
        if(A[i].k == 1) ins[ID[i]] = 1;  
        else {  
            int j,c = 0;  
            for(j = 0; j < T.size(); j++) if(ins[j]) {  
                int len = min(A[i].b,T[j].b) - max(A[i].a,T[j].a) + 1;  
                if(len <= 0) continue;  
                if((c += len) >= A[i].c) break;  
            }  
            printf("%dn",T[j].c);  
        }  
    return 0;  
}

整体二分 http://blog.csdn.net/qq_21841245/article/details/44906735

    #include "cstdio"  
    #define lowbit(x) (x & (-x))   
       
    using namespace std;  
       
    const int Nmax = 50005;  
       
    int N,M;  
    struct Option{  
        int sign,y,c;  
    }op[Nmax];  
       
    int tot = -1,ans[Nmax];  
    int q[Nmax],tmp[2][Nmax];  
       
    namespace BIT{  
        int t[Nmax][2],d[Nmax][2];  
       
        void update(bool s,int pos,int c)  
        {  
            for (int i = pos; i <= N; i += lowbit(i)) {  
                if (t[i][s] != tot) { t[i][s] = tot; d[i][s] = 0; }  
                d[i][s] += c;  
            }  
        }  
           
        int get_sum(bool s,int pos)  
        {  
            int res = 0;  
            for (int i = pos; i; i -= lowbit(i)) {  
                if (t[i][s] != tot) { t[i][s] = tot; d[i][s] = 0; }  
                res += d[i][s];  
            }  
            return res;  
        }  
           
        void Add(int x,int y)  
        {  
            update(0,1); update(0,y + 1,-1);  
            update(1,x); update(1,-(y + 1));  
        }  
           
        int Query(int x,int y)  
        {  
            int temp = get_sum(0,y) * (y + 1) - get_sum(1,y);  
            temp -= get_sum(0,x - 1) * x - get_sum(1,x - 1);  
            return temp;  
        }  
    }  
       
    void solve(int L,int r)  
    {  
        if (L > R) return;  
           
        ++tot; int mid = (l + r) >> 1;  
        if (l == r) {  
            for (int i = L; i <= R; ++i) if (op[q[i]].sign == 2) ans[q[i]] = mid;  
            return;  
        }  
           
        tmp[0][0] = tmp[1][0] = 0; using namespace BIT;  
        for (int i = L; i <= R; ++i) {  
            int temp = q[i];  
            if (op[temp].sign == 1) {  
                if (op[temp].c <= mid) tmp[0][++tmp[0][0]] = temp;  
                else {  
                    tmp[1][++tmp[1][0]] = temp;  
                    Add(op[temp].x,op[temp].y);  
                }  
            } else {  
                int cnt = Query(op[temp].x,op[temp].y);  
                if (cnt < op[temp].c) {  
                    op[temp].c -= cnt;  
                    tmp[0][++tmp[0][0]] = temp;  
                } else tmp[1][++tmp[1][0]] = temp;  
            }  
        }  
           
        int tl = L,t2 = L + tmp[0][0] - 1;  
        for (int i = 1; i <= tmp[0][0]; ++i) q[tl++] = tmp[0][i];  
        for (int i = 1; i <= tmp[1][0]; ++i) q[tl++] = tmp[1][i];  
        solve(L,t2,mid); solve(t2 + 1,r);  
    }  
       
    int main()  
    {  
        scanf("%d%d",&N,&M);  
        for (int i = 1; i <= M; ++i) {  
            scanf("%d%d%d%d",&op[i].sign,&op[i].x,&op[i].y,&op[i].c);  
            q[i] = i;  
        }  
        solve(1,M,N);  
        for (int i = 1; i <= M; ++i) {  
            if (op[i].sign == 2) printf("%dn",ans[i]);  
        }  
           
        return 0;  
    }

（编辑：李大同）

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