【bzoj3110】[Zjoi2013]K大数查询

2015.02.16 08:20 Mon | 4次阅读 | 旧日oi | 固定链接 | 源码

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操作中abs(c)<=Maxlongint

题解

先用和二逼平衡树一样的方法写了一个线段树套treap,re到死也过不了……
后来上网查了题解,发现都是线段树套线段树,看了代码觉得不甚了了,研究了大概2个小时总算是明白了,为了给后来者做一做贡献,我写一个详细版的题解吧。
第一维是值域线段树
第二维是区间线段树
先看代码

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define maxn 200005 
using namespace std;
int sum[20000005],flag[20000005],siz;//sum[k]代表值域为[l.r],位于区间[L,R]的元素个数,下文会说明。 flag是下传标记 ,siz是节点标号 
int lson[20000005],rson[20000005],root[maxn];//左儿子,右儿子,每个值域范围对应的第二维区间线段树的根节点 
int n,m;
int a,L,R,c;
void push_down(int rt,int l,int r)//下传 
{
    if(!flag[rt]||l==r) return;
    if(!lson[rt]) lson[rt]=++siz;
    if(!rson[rt]) rson[rt]=++siz;
    flag[lson[rt]]+=flag[rt];
    flag[rson[rt]]+=flag[rt];
    int mid=(l+r)>>1;
    sum[lson[rt]]+=(mid-l+1)*flag[rt];
    sum[rson[rt]]+=(r-mid)*flag[rt];
    flag[rt]=0;
}
void update(int &rt,int l,int r,int L,int R)//和正常线段树类似 
{
    if(!rt) rt=++siz;//若不存在,则建立新节点 
    push_down(rt,l,r);//下传 
    if(l==L&&r==R)
    {
        sum[rt]+=r-l+1; //此时的sum[rt]表示值域为add函数中的[l,r],区间为[L,R]的元素个数 
        flag[rt]++;
        return;
    }
    int mid=(l+r)>>1;
    if(R<=mid) update(lson[rt],l,mid,L,R);
    else if(L>mid) update(rson[rt],mid+1,r,L,R);
    else
    {
        update(lson[rt],l,mid,L,mid);
        update(rson[rt],mid+1,r,mid+1,R);
    }
    sum[rt]=sum[lson[rt]]+sum[rson[rt]];
}
void add()//在第一维线段树上定位并在第二维线段树上修改 
{
    int l=1,r=n,rt=1;//l,r为值域,rt为此值域在第二维区间线段树中的根节点 
    while(l!=r)
    {
        update(root[rt],1,n,L,R);//在此值域内更新[L,R]的元素个数 
        int mid=(l+r)>>1;
        if(c<=mid) r=mid,rt<<=1;
        else l=mid+1,rt=rt<<1|1;//根据c确定下一个需要修改的值域 
    }
    update(root[rt],1,n,L,R);//这步不能忘 
}
int query(int rt,int l,int r,int L,int R)//普通的线段树查询 
{
    if(!rt)return 0;
    push_down(rt,l,r);
    if(l==L&&r==R)return sum[rt];
    int mid=(l+r)>>1;
    if(R<=mid)return query(lson[rt],l,mid,L,R);
    else if(L>mid)return query(rson[rt],mid+1,r,L,R);
    else return query(lson[rt],l,mid,L,mid)+query(rson[rt],mid+1,r,mid+1,R);
}
int solve()
{
    int l=1,r=n,rt=1;//l,r为值域,rt为此值域在第二维区间线段树中的根节点  
    while(l!=r)
    {
        int mid=(l+r)>>1;
        int t=query(root[rt<<1|1],1,n,L,R);//看此值域的右子树位于区间[L,R]的元素个数之和 
        if(t<c) r=mid,rt<<=1,c-=t;//如果不够c个,则需进入左子树,并在c中减去t 
        else l=mid+1,rt=rt<<1|1;//否则进入右子树 
    }
    return r;
}
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read();m=read();
    while(m--)
    {
        a=read();L=read();R=read();c=read();
        if(a==1) add();//添加元素 
        else printf("%d\n",solve());//查询 
    }
    return 0;
} 
下面演示一下这个算法
 为什么图粘不上。。好吧那就没办法了……```