[BZOJ3110/Luogu3332][ZJOI2013]K大数查询(树套树,线段树)

发布于 2018-04-17  77 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3110/Luogu3332][ZJOI2013]K大数查询(树套树,线段树)

Description

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

Tag

树套树,线段树

解决思路

外层维护权值线段树,内层维护位置线段树。修改则对外层单点修改,内层区间加法。查询则是在外层线段树上二分地查询。需要动态开点。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lson (now<<1)
#define rson (lson|1)

const int maxN=50100;
const int inf=2147483647;

int n,m;
ll numcnt=0,Num[maxN];

class SegData
{
public:
    ll val,lazy;
    int ls,rs;
};

int nodecnt=0;
SegData S[maxN*200];

class InTree//内层线段树
{
public:
    int root;
    InTree(){
        root=0;return;
    }

    void Modify(int &now,int l,int r,int ql,int qr,ll key){
        if (now==0) now=++nodecnt;
        S[now].val+=key*(qr-ql+1);
        if ((l==ql)&&(r==qr)){
            S[now].lazy+=key;return;
        }
        int mid=(l+r)>>1;
        if (qr<=mid) Modify(S[now].ls,l,mid,ql,qr,key);
        else if (ql>=mid+1) Modify(S[now].rs,mid+1,r,ql,qr,key);
        else
        {
            Modify(S[now].ls,l,mid,ql,mid,key);
            Modify(S[now].rs,mid+1,r,mid+1,qr,key);
        }
        return;
    }
    ll Query(int now,int l,int r,int ql,int qr){
        if (now==0) return 0;
        if ((l==ql)&&(r==qr)) return S[now].val;
        int mid=(l+r)>>1;
        ll Ret=S[now].lazy*(ll)(qr-ql+1);
        if (qr<=mid) return Query(S[now].ls,l,mid,ql,qr)+Ret;
        else if (ql>=mid+1) return Query(S[now].rs,mid+1,r,ql,qr)+Ret;
        else return Query(S[now].ls,l,mid,ql,mid)+Query(S[now].rs,mid+1,r,mid+1,qr)+Ret;
    }
};

class OutTree//外层线段树
{
public:
    InTree T[maxN<<2];
    void Modify(int now,int l,int r,int pos,int Rl,int Rr){
        T[now].Modify(T[now].root,1,n,Rl,Rr,1);
        if (l==r) return;
        int mid=(l+r)>>1;
        if (pos<=mid) Modify(lson,l,mid,pos,Rl,Rr);
        else Modify(rson,mid+1,r,pos,Rl,Rr);
        return;
    }
    ll Query(int now,int l,int r,int Rl,int Rr,ll kth){
        if (l==r) return l;
        int mid=(l+r)>>1;
        ll G=T[rson].Query(T[rson].root,1,n,Rl,Rr);
        if (G>=kth) return Query(rson,mid+1,r,Rl,Rr,kth);
        else return Query(lson,l,mid,Rl,Rr,kth-G);
    }
};

class Question
{
public:
    ll opt,a,b,c;
};

Question Q[maxN];
OutTree T;

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld%lld",&Q[i].opt,&Q[i].a,&Q[i].b,&Q[i].c);
        if (Q[i].opt==1) Num[++numcnt]=Q[i].c;
    }
    sort(&Num[1],&Num[numcnt+1]);//离散化
    numcnt=unique(&Num[1],&Num[numcnt+1])-Num-1;
    for (int i=1;i<=m;i++)
        if (Q[i].opt==1)
        {
            Q[i].c=lower_bound(&Num[1],&Num[numcnt+1],Q[i].c)-Num;
            T.Modify(1,1,numcnt,Q[i].c,Q[i].a,Q[i].b);
        }
        else
        {
            printf("%lld\n",Num[T.Query(1,1,numcnt,Q[i].a,Q[i].b,Q[i].c)]);
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3110/Luogu3332][ZJOI2013]K大数查询(树套树,线段树)


HNCJ OIer 一枚