[ZJOI2013][luoguP3332]K大数查询

奇怪的区间第k大~

题目描述

有N个位置,M个操作。操作有两种,每次操作是:
1 l r c:表示在第l个位置到第r个位置,每个位置加上一个数c
2 l r c:表示询问从第l个位置到第r个位置,第C大的数是多少。
注意:这个数组的每个元素都是一个栈,这里的“加上”指的是在某个位置压进去一个新数
其中,$n,m\le 50000$ ,对于1操作,$|c|\le n$,对于2操作,c在long long范围内

题解:

大致思路

我不会整体二分,所以我采用了树套树。
这个第k小看起来很不舒服,所以我们统计一下区间中数的总数,转成第k大就好了。

回忆一下$O(n\lg^3n)$的区间第k大做法,我们用外层线段树维护位置,内层线段树维护数值。查询的时候二分得到答案。由于外面一层没有给我们什么有用的信息,所以我们只能采用近乎智障的二分…而且还不能区间修改…

真的只能这样吗?

考虑实际上我们维护的还是一种偏序关系,位置和值的限制实际上是等价的。我们完全可以让外层的线段树维护值域,内层的线段树(平衡树)维护位置.而且,这样的话,我们自动拥有了值域线段树具有的二分性质,不用在外面套上一个傻乎乎的二分了。。
具体来说,我们在外层线段树(值域)递归,每一层中,使用内层线段树查询左子树中落在$[l..r]$之间的数的个数cnt。如果$k\le cnt$,进入左子树;反之,进入右子树。到叶子的时候返回值。

考虑区间修改,我们只需要把平衡树换成线段树就好了——这样我们就可以打lazy标记辣!于是就做完了!

撒花!

几个优化的小技巧:

  • 内层线段树使用动态开点,将空间降至$O(n\lg^2 n)$
  • 内层线段树可以标记永久化,减小常数。

    “永久化的标记就是值” –zkw《统计的力量》

  • 标记永久化:我们不再下传标记,而是改为查询时经过每个节点都累计其具有的标记,最后递归访问终止节点的时候计算这些标记造成的贡献。

其实树套树也不是多慢嘛,就比整体二分慢了一倍
写个快读是不是就差不多了啊

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <cstdio>
#include <cstring>
#include <climits>
#include <cstdint>
#include <algorithm>

const int maxn=5e4+1000;

int bl[maxn],br[maxn],cntl,cntr;

template<class T>inline T max(T a,T b){return a<b?b:a;}
template<class T>inline T min(T a,T b){return a<b?a:b;}

struct Node
{
int ls,rs;
int64_t siz,tag;
}T[maxn*300];

int root[maxn<<3],cnt;

inline int _modify(int L,int R,int rt,int l,int r) // 内层线段树的插入操作
{
if (!rt) rt=++cnt;
T[rt].siz+=min(R,r)-max(L,l)+1;
if (L<=l && R>=r)
return T[rt].tag++,rt;
int mid=(l+r)>>1;
if (L<=mid) T[rt].ls=_modify(L,R,T[rt].ls,l,mid);
if (R> mid) T[rt].rs=_modify(L,R,T[rt].rs,mid+1,r);
return rt;
}

inline int64_t _query(int L,int R,int rt,int l,int r,int64_t add=0) // 内层线段树查询size
{
if (!rt) rt=++cnt;
if (L<=l && R>=r) return T[rt].siz+add*(r-l+1);
int mid=(l+r)>>1;
int64_t tot=0;
if (L<=mid) tot+=_query(L,R,T[rt].ls,l,mid,add+T[rt].tag);
if (R> mid) tot+=_query(L,R,T[rt].rs,mid+1,r,add+T[rt].tag);
return tot;
}

inline void modify(int x,int L,int R,int l,int r,int o,int n) // 外层线段树的修改
{
root[o]=_modify(L,R,root[o],1,n);
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) modify(x,L,R,l,mid,o<<1,n);
else modify(x,L,R,mid+1,r,o<<1|1,n);
}

inline int query(int L,int R,int64_t k,int l,int r,int o,int n) // 外层线段树的查询
{
if (l==r) return l;
int mid=(l+r)>>1;
int64_t rnk=_query(L,R,root[o<<1],1,n,0);
// printf("%d %d %d %d %d\n",L,R,l,mid,rnk);
if (k<=rnk) return query(L,R,k,l,mid,o<<1,n);
else return query(L,R,k-rnk,mid+1,r,o<<1|1,n);
}

int64_t sumv[maxn<<2],tag[maxn<<2];
#define ls l,mid,o<<1
#define rs mid+1,r,o<<1|1

inline void pushdown(int o,int len)
{
sumv[o<<1]+=tag[o]*(len-(len>>1));
sumv[o<<1|1]+=tag[o]*(len>>1);
tag[o<<1]+=tag[o];tag[o<<1|1]+=tag[o];
tag[o]=0;
}

inline void pushup(int o){sumv[o]=sumv[o<<1]+sumv[o<<1|1];}

inline void add(int L,int R,int c,int l,int r,int o)
{
if (L<=l && R>=r) return (void)(sumv[o]+=c*(r-l+1),tag[o]+=c);
pushdown(o,r-l+1);
int mid=(l+r)>>1;
if (L<=mid) add(L,R,c,ls);
if (R> mid) add(L,R,c,rs);
pushup(o);
}

inline int64_t query(int L,int R,int l,int r,int o)
{
if (L<=l && R>=r) return sumv[o];
pushdown(o,r-l+1);
int mid=(l+r)>>1;
int64_t tot=0;
if (L<=mid) tot+=query(L,R,ls);
if (R> mid) tot+=query(L,R,rs);
return tot;
}

inline int query(int L,int R,int64_t k,int n)
{
k=query(L,R,1,n,1)-k+1;
// printf("%d\n",k);
return query(L,R,k,1,n*2+2,1,n)-n-1;
}

inline void modify(int l,int r,int c,int n)
{
add(l,r,1,1,n,1);
modify(c+n+1,l,r,1,n*2+2,1,n);
}

int main()
{
// freopen("testdata3332.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
int64_t c;
for (int i=1,a,b,opt;i<=m;++i)
{
scanf("%d%d%d%lld",&opt,&a,&b,&c);
if (opt&1) modify(a,b,c,n);
else printf("%d\n",query(a,b,c,n));
}
}