1. 题目

BZOJ – 3110：传送门=￣ω￣=

LUOGU – 3332：传送门=￣ω￣=

2. 题解

哈哈哈终于完美 AC 这题惹！

整体二分就是吼哇 QvQ！

有先决科技点：整体二分解决单点修改区间 kth 问题：传送门=￣ω￣=

上面那题是单点修改所以用的树状数组。

这里区间修改就用线段树（Segment tree QvQ）嘛～

代码：

#include <bits/stdc++.h>
#define NS (50005)
#define MS (50005)
#define LS(a) (a<<1)
#define RS(a) (a<<1|1)
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct Query{int l,r,id,type;LL k;}Q[MS],Q1[MS],Q2[MS];
struct N{int l,r,tag;LL d;}e[NS<<2];
int n,m,cnt,qcnt,ans[MS];
void pdown(int a)
{
    if(e[a].tag)
    {
        e[LS(a)].d+=(e[LS(a)].r-e[LS(a)].l+1)*e[a].tag,e[LS(a)].tag+=e[a].tag;
        e[RS(a)].d+=(e[RS(a)].r-e[RS(a)].l+1)*e[a].tag,e[RS(a)].tag+=e[a].tag;
        e[a].tag=0;
    }
}
void pup(int a){e[a].d=e[LS(a)].d+e[RS(a)].d;}
void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(l,mid,LS(a)),build(mid+1,r,RS(a));
}
void update(int l,int r,LL d,int a)
{
    if(l<=e[a].l&&e[a].r<=r){e[a].d+=(e[a].r-e[a].l+1)*d,e[a].tag+=d;return;}
    pdown(a);
    if(l<=e[LS(a)].r)update(l,r,d,LS(a));
    if(r>=e[RS(a)].l)update(l,r,d,RS(a));
    pup(a);
}
LL query(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].d;
    pdown(a);
    LL tot=0;
    if(l<=e[LS(a)].r)tot+=query(l,r,LS(a));
    if(r>=e[RS(a)].l)tot+=query(l,r,RS(a));
    return tot;
}
void binary(int QL,int QR,int l,int r)
{
    if(QL>QR)return;
    if(l==r){for(int i=QL;i<=QR;i++)if(Q[i].type)ans[Q[i].id]=l;return;}
    int mid=(l+r)>>1,x1=0,x2=0;
    for(int i=QL;i<=QR;i++)
        if(Q[i].type)
        {
            LL tmp=query(Q[i].l,Q[i].r,1);
            if(Q[i].k<=tmp)Q1[++x1]=Q[i];
            else Q2[++x2]=Q[i],Q2[x2].k-=tmp;
        }
        else
        {
            if(Q[i].k<=mid)update(Q[i].l,Q[i].r,1,1),Q1[++x1]=Q[i];
            else Q2[++x2]=Q[i];
        }
    for(int i=1;i<=x1;i++)if(!Q1[i].type)update(Q1[i].l,Q1[i].r,-1,1);
    for(int i=1;i<=x1;i++)Q[QL+i-1]=Q1[i];
    for(int i=1;i<=x2;i++)Q[QL+x1+i-1]=Q2[i];
    binary(QL,QL+x1-1,l,mid),binary(QL+x1,QR,mid+1,r);
}
int main()
{
    IN(n),IN(m),build(1,n,1);
    int opt,a,b;LL c;
    for(int i=1;i<=m;i++)
        if(IN(opt),IN(a),IN(b),IN(c),opt==1)Q[++cnt]=(Query){a,b,0,0,-c};
        else Q[++cnt]=(Query){a,b,++qcnt,1,c};
    binary(1,cnt,-NS,NS);
    for(int i=1;i<=qcnt;i++)printf("%d\n",-ans[i]);
    return 0;
}