BZOJ3110 K大数查询 【线段树 + 整体二分 或 树套树(非正解)】

Description

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

如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M

接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5

1 1 2 1

1 1 2 2

2 1 1 2

2 1 1 1

2 1 2 3

Sample Output

1

2

1

HINT

【样例说明】



第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1



的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是



1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3



大的数是 1 。‍


N,M<=50000,N,M<=50000



a<=b<=N



1操作中abs(c)<=N



2操作中c<=Maxlongint

题解

不得不承认我真是太弱了,怼了这题几天,最后一个点还特判过的。。
不过终于解决这道难题,收货颇丰【QAQ蒟蒻的自我安慰】

首先说一下最容易想到的树套树做法
要求第k大,我们先权值取反,变为求第k小
先建一棵树维护每个权值出现的次数,这棵树并不是真的存在,它储存的只是另一棵树的根节点,对于根节点建一棵关于区间的线段树,表示权值[a,b]在区间[l,r]出现的次数
这样我们就可以通过二分求出[l,r]区间内的第k小数

例如我们要求[1,10]内第5小的数【假设总权值为[1,100]】
我们现在权值[1,50]的区间的根节点所在线段树询问[1,10]内的值,表示[1,50]权值在[1,10]这个区间内出现过多少次,
如果大于5,说明[1,10]区间内第k小一定在[1,50]权值内,
同理,我们在[1,25]找,一直到区间长度为1,即为答案

修改就更简单了,找到对应区间的树进行区间修改就好了


但正解不是树套树
正解是      整体二分 + 线段树


我们按顺序先存下所有的询问与修改,然后以权值为关键字进行二分,建立一棵关于区间出现次数的线段树
每次我们将一半的权值添加对线段树进行修改,就可以的出当前任意区间内该部分权值出现的次数,就可以对所有的询问进行二分了

对于区间[l,r],我们找到中间的mid值,然后从左开始扫描操作
1、如果是修改 且 权值大于mid,那么属于[mid + 1,r]范围内的权值,在线段树中[a,b]区间整体+1,表示[mid + 1,r]在区间[a,b]个出现了一次,然后放到相应的左边右边
2、如果是询问,我们看看当前[a,b]区间[mid + 1,r]权值出现的次数,如果大于c,说明在答案在该区间内,放到右边,否则放到左边
3、所有处理完后,对左右区间再二分,直至区间长度为1,得到答案



下面是树套树【没有A】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 400005,maxm = 20000005,INF = 1000000000; inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
return out * flag;
} int a,b,c,N;
int n,m,siz = 0;
int rt[maxn];
int ls[maxm],rs[maxm],sum[maxm],lazy[maxm],L,R; inline void pd(int u,int l,int r){
if (!lazy[u] || l == r) return;
if (!ls[u]) ls[u] = ++siz;
if (!rs[u]) rs[u] = ++siz;
lazy[ls[u]] += lazy[u]; lazy[rs[u]] += lazy[u];
int mid = l + r >> 1;
sum[ls[u]] += lazy[u] * (mid - l + 1);
sum[rs[u]] += lazy[u] * (r - mid);
lazy[u] = 0;
} void modify(int& u,int l,int r){
if (!u) u = ++siz;
if (l >= L && r <= R){
sum[u] += (r - l + 1);
lazy[u]++;
}else {
pd(u,l,r);
int mid = l + r >> 1;
if (mid >= L) modify(ls[u],l,mid);
if (mid < R) modify(rs[u],mid + 1,r);
sum[u] = sum[ls[u]] + sum[rs[u]];
}
} int Query(int u,int l,int r){
if (!u) return 0;
if (l >= L && r <= R) return sum[u];
else {
pd(u,l,r);
int mid = l + r >> 1;
if (mid >= R) return Query(ls[u],l,mid);
else if (mid < L) return Query(rs[u],mid + 1,r);
else return Query(ls[u],l,mid) + Query(rs[u],mid + 1,r);
}
} inline void insert(){
int u = 1,l = 1,r = N;
L = a; R = b;
while (l < r){
int mid = l + r >> 1;
modify(rt[u],1,n);
if (c <= mid) r = mid,u = u << 1;
else l = mid + 1,u = u << 1 | 1;
}
modify(rt[u],1,n);
} inline void solve(){
int u = 1,l = 1,r = N,t;
L = a; R = b;
while (l < r){
int mid = l + r >> 1;
t = Query(rt[u << 1],1,n);
if (c <= t) r = mid,u = u << 1;
else l = mid + 1,u = u << 1 | 1,c -= t;
}
printf("%d\n",N - l + 1 - n);
} int main()
{
int cmd;
n = read(); m = read();N = n * 2 + 1;
while (m--){
cmd = read(); a = read(); b = read(); c = read();
if (cmd & 1){
c += n;
c = N - c + 1;
insert();
}else solve();
}
return 0;
}


正解,整体二分【特判了一下。。。】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 500005,maxm = 100005,INF = 1000000000;
//begin 18:00 end 19:27
inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
return out * flag;
} int n,M; struct node{
int l,r,v,p,id,k;
}e[maxn]; inline bool cmp(const node& a,const node& b){
return a.k == b.k ? a.id < b.id : a.k < b.k;
} int ans[maxn];
int sum[4 * maxn],lazy[4 * maxn],L,R;
bool cl[4 * maxn]; inline void pd(int u,int l,int r){
if (cl[u]) sum[u<<1] = sum[u<<1|1] = lazy[u<<1] = lazy[u<<1|1] = cl[u] = 0,cl[u<<1] = cl[u<<1|1] = true;
if (lazy[u]){
int mid = l + r >> 1;
sum[u<<1] += (mid - l + 1) * lazy[u];
sum[u<<1|1] += (r - mid) * lazy[u];
lazy[u<<1] += lazy[u];
lazy[u<<1|1] += lazy[u];
lazy[u] = 0;
}
} inline void update(int u,int l,int r){
pd(u,l,r);
if (l >= L && r <= R){
sum[u] += (r - l + 1);
lazy[u]++;
}
else {
int mid = l + r >> 1;
if (mid >= L) update(u<<1,l,mid);
if (mid < R) update(u<<1|1,mid + 1,r);
sum[u] = sum[u<<1] + sum[u<<1|1];
}
} inline int Query(int u,int l,int r){
pd(u,l,r);
if (l >= L && r <= R) return sum[u];
else {
int mid = l + r >> 1;
if (mid >= R) return Query(u<<1,l,mid);
else if (mid < L) return Query(u<<1|1,mid + 1,r);
else return Query(u<<1,l,mid) + Query(u<<1|1,mid + 1,r);
}
} void solve(int l,int r,int el,int er){
if (el > er) return;
if (l == r){
for (int i = el; i <= er; i++)
if (e[i].p == 2) ans[e[i].id] = l;
}
else {
cl[1] = true; sum[1] = lazy[1] = 0;
int mid = (l + r) >> 1,i = el - 1,t;
for (int k = el; k <= er; k++){
if (e[k].p == 1){
if (e[k].v > mid){
L = e[k].l; R = e[k].r;
update(1,1,n);
e[k].k = 1;
}else {
e[k].k = 0;
i++;
}
}
else {
L = e[k].l; R = e[k].r;
t = Query(1,1,n);
if (e[k].v <= t) e[k].k = 1;
else {
e[k].v -= t;
e[k].k = 0;
i++;
}
}
}
sort(e + el,e + er + 1,cmp);
solve(l,mid,el,i);
solve(mid + 1,r,i + 1,er);
}
} void init(){
n = read(); M = read();
REP(i,M){
e[i].p = read();
e[i].l = read();
e[i].r = read();
e[i].v = read();
if (e[i].p == 1) e[i].v = e[i].v + n;
e[i].id = i;
}
memset(ans,-1,sizeof(ans));
} void print(){
for (int i = 1; i <= M; i++)
if (ans[i] != -1) {
if (ans[i] == n) printf("50000\n");
else printf("%d\n",ans[i] - n);
}
} int main()
{
init();
solve(0,2 * n,1,M);
print();
return 0;
}


上一篇:深入解析VueJs中的V-bind指令


下一篇:HDU - 5307 :He is Flying (分治+FFT)(非正解)