洛谷 P3332 [ZJOI2013]K大数查询解题报告

P3332 [ZJOI2013]K大数查询

题目描述

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

输入输出格式

输入格式：

第一行(N)，(M)接下来(M)行，每行形如( t{1 a b c})或( t{2 a b c})

输出格式：

输出每个询问的结果

说明

(N,Mle 50000)

(ale ble N)

(1)操作中(abs(c)le N)

(2)操作中(cle long long)

把整体二分的树状数组改成线段树区间操作即可

Code:

#include <cstdio>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N=1e5+10;
struct node{int op,l,r;ll c;}q[N],ql[N],qr[N];
int ans[N],n,m,Q;
ll sum[N<<1],tag[N<<1];
#define ls id<<1
#define rs id<<1|1
void pushdown(int id,int L,int R)
{
    if(tag[id])
    {
        int Mid=L+R>>1;
        sum[ls]+=tag[id]*(Mid+1-L),sum[rs]+=tag[id]*(R-Mid);
        tag[ls]+=tag[id],tag[rs]+=tag[id];
        tag[id]=0;
    }
}
void change(int id,int L,int R,int l,int r,ll d)
{
    if(L==l&&R==r)
    {
        tag[id]+=d,sum[id]+=1ll*(R+1-L)*d;
        return;
    }
    pushdown(id,L,R);
    int Mid=L+R>>1;
    if(r<=Mid) change(ls,L,Mid,l,r,d);
    else if(l>Mid) change(rs,Mid+1,R,l,r,d);
    else change(ls,L,Mid,l,Mid,d),change(rs,Mid+1,R,Mid+1,r,d);
    sum[id]=sum[ls]+sum[rs];
}
ll query(int id,int L,int R,int l,int r)
{
    if(L==l&&R==r)return sum[id];
    pushdown(id,L,R);
    int Mid=L+R>>1;
    if(r<=Mid) return query(ls,L,Mid,l,r);
    else if(l>Mid) return query(rs,Mid+1,R,l,r);
    else return query(ls,L,Mid,l,Mid)+query(rs,Mid+1,R,Mid+1,r);
}
void divide(int l,int r,int s,int t)
{
    if(s>t) return;
    if(l==r) {rep(i,s,t)ans[q[i].op]=l;return;}
    int mid=l+r>>1,lp=0,rp=0;
    rep(i,s,t)
    {
        if(q[i].op)
        {
            ll c=query(1,1,n,q[i].l,q[i].r);
            if(c>=q[i].c) qr[++rp]=q[i];
            else ql[++lp]=q[i],ql[lp].c-=c;
        }
        else
        {
            if(q[i].c>mid) change(1,1,n,q[i].l,q[i].r,1),qr[++rp]=q[i];
            else ql[++lp]=q[i];
        }
    }
    rep(i,s,t)if(!q[i].op&&q[i].c>mid) change(1,1,n,q[i].l,q[i].r,-1);
    rep(i,s,s+lp-1) q[i]=ql[i+1-s];
    rep(i,s+lp,t) q[i]=qr[i+1-s-lp];
    divide(l,mid,s,s+lp-1),divide(mid+1,r,s+lp,t);
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,m)
    {
        scanf("%d%d%d%lld",&q[i].op,&q[i].l,&q[i].r,&q[i].c),--q[i].op;
        if(q[i].op) q[i].op=++Q;
    }
    divide(-n,n,1,m);
    rep(i,1,Q) printf("%d
",ans[i]);
    return 0;
}

2018.11.1