LP3332 [ZJOI2013]K大数查询 [整体二分]
整体二分真难...
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;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-3332.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆