LP3332 [ZJOI2013]K大数查询 [整体二分]

Author Avatar
空気浮遊 2018年07月21日
  • 在其它设备中阅读本文章

整体二分真难...

Problem

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

Solution

整体二分整体将修改和询问二分。

二分答案,并对修改和询问的序列分割成两份,并移动到分治树两边的子树中。

共 $\log S$ 层($S$ 为值域大小),共 $m+n$ 个操作,因此总复杂度为 $O((m+n)\log n \log S)$。

即,本题最原始的二分思想是对于一个询问,二分一个 $mid$ 值,查看区域中有 $a$ 个数比其大。这个 $a$ 应小于 $k$,否则 mid 应当会更大。由此我们可以确定询问答案的范围。

则我们在每一层分治 $[l,r]$ 中,我们二分一个 mid 值,并确定询问各自答案所属区间 $[l,mid]$ 或 $[mid+1,r]$。

我们需要计算答案对询问的贡献。由于询问有多少个数比 $mid$ 大,因此我们在本层用线段树来进行加法算贡献,只对修改 >mid 的区间整体 +1.

这部分有点像 cdq,按照时间顺序边算贡献的同时边算询问贡献并推进贡献。然后可以确定询问的范围。

我们发现如果询问的答案值域是属于 $[l,mid]$ 的,那么刚刚所有进行的修改操作一定持续对该询问产生贡献。因此这部分修改就不需要再去往左边值域进行分治,而直接在 k 上减 a 来造成永久影响,在此之后询问继续二分不重复计算询问的贡献。

但如果值域属于 $[mid+1, r]$ 的,刚刚的修改操作仍要参与这部分询问的贡献。当 mid 变动的时候,部分修改操作仍旧对该询问生效。

所以二分的步骤,我们对于操作值 <=mid 的,分配到左边值域进行整体二分。否则反之。
再进行答案的值域分配就行了。

注意线段树 lazy 清零的一些细节。

Code

// Code by ajcxsu
// Problem: kth query

#include<bits/stdc++.h>
using namespace std;

template<typename T> void gn(T &x) {
    char ch=getchar(), pl=0;
    x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    if(pl) x=-x;
}

const int N=5e4+10;
typedef long long ll;

#define ls x<<1
#define rs x<<1|1
ll sum[N*6]; int lazy[N*6], len[N*6];
void pud(int x) {
    if(!len[x] || !lazy[x]) return;
    if(lazy[x]==-1)
        sum[ls]=sum[rs]=0, lazy[ls]=lazy[rs]=-1;
    else if(lazy[x]) {
        if(lazy[ls]==-1) pud(ls);
        if(lazy[rs]==-1) pud(rs); // 这里判断很重要
        lazy[ls]+=lazy[x], lazy[rs]+=lazy[x], sum[ls]+=lazy[x]*len[ls], sum[rs]+=lazy[x]*len[rs];
    }
    lazy[x]=0;
}
void build(int x, int l, int r) {
    len[x]=r-l+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
}
void updata(int x, int l, int r, int xl, int xr) {
    pud(x);
    if(xl<=l && r<=xr) { lazy[x]++; sum[x]+=len[x]; return; }
    int mid=(l+r)>>1;
    if(xl<=mid) updata(ls, l, mid, xl, xr);
    if(xr>mid) updata(rs, mid+1, r, xl, xr);
    sum[x]=sum[ls]+sum[rs];
}
ll query(int x, int l, int r, int xl, int xr) {
    pud(x);
    if(xl<=l && r<=xr) return sum[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return query(ls, l, mid, xl, xr);
    else if(xl>mid) return query(rs, mid+1, r, xl, xr);
    else return query(ls, l, mid, xl, mid) + query(rs, mid+1, r, mid+1, xr);
}
void clear() { lazy[1]=-1, sum[1]=0; }


struct Ope { int l, r; ll c; int idx; } o[N];
int opt[N], que[N], ca1[N], ca2[N], ans[N];
int n, m;
void div(int pl, int pr, int ql, int qr, int l, int r) {
    if(l==r) {
        for(int i=ql;i<=qr;i++) ans[o[que[i]].idx]=l;
        return;
    }
    int mid=(l+r)>>1, t1=0, t2=0, j=pl, k;
    for(int i=pl;i<=pr;i++)
        if(o[opt[i]].c<=mid) ca1[++t1]=opt[i];
        else ca2[++t2]=opt[i];
    for(int i=1;i<=t1;i++) opt[j++]=ca1[i];
    k=j;
    for(int i=1;i<=t2;i++) opt[j++]=ca2[i];
    j=k, clear(), t1=t2=0;
    ll t;
    for(int i=ql;i<=qr;i++) {
        while(k<=pr && opt[k]<que[i]) updata(1, 1, n, o[opt[k]].l, o[opt[k]].r), k++;
        t=query(1, 1, n, o[que[i]].l, o[que[i]].r);
        if(t>=o[que[i]].c) ca2[++t2]=que[i];
        else ca1[++t1]=que[i], o[que[i]].c-=t;
    }
    k=j, j=ql;
    for(int i=1;i<=t1;i++) que[j++]=ca1[i];
    t1=j-1;
    for(int i=1;i<=t2;i++) que[j++]=ca2[i];
    if(t1>=ql) div(pl, k-1, ql, t1, l, mid);
    if(t1+1<=qr) div(k, pr, t1+1, qr, mid+1, r);
}

int main() {
    int a, b, c, d, n1=0, n2=0;
    gn(n), build(1, 1, n), gn(m);
    for(int i=1;i<=m;i++) {
        gn(a), gn(b), gn(c), gn(d);
        o[i].l=b, o[i].r=c, o[i].c=d;
        if(a==1) opt[++n1]=i;
        else que[++n2]=i, o[i].idx=n2;
    }
    div(1, n1, 1, n2, -n, n);
    for(int i=1;i<=n2;i++) printf("%d\n", ans[i]);
    return 0;
}