Solution - P3332 [ZJOI2013]K大数查询

Posted on Edited on

P3332 [ZJOI2013]K大数查询

idea:

参考 zhoukangyangzhoukangyang 题解。

树状数组套动态加点权值线段树。

Solution：

设有 maxnmaxn 个不同的值。可以先离散化（从大到小）。

  1. 开一个大小为 maxnmaxn 的树状数组。

支持两个操作：

I(le,ri,c)I(le,ri,c) 将第 cc 大的数插入 [le,ri][le,ri] 的集合中。

Findk(le,ri,k)Findk(le,ri,k) 找到 [le,ri][le,ri] 中的第 kk 大数。

树状数组依然维护前缀和。 T(le,ri,x)T(le,ri,x) 表示 [le,ri][le,ri] 内的集合的并集内 (x−lowbit(x),x](x-lowbit(x),x] 内的数的出现次数。

如何求得 T(le,ri,x)T(le,ri,x) 呢？细品。

  1. 开 maxnmaxn 个权值线段树。

权值线段树支持区间修改和区间查询（区间和）。

区间修改：将以 cc 为根的线段树中的 [le,ri][le,ri] 所有数加上 11 。

意义：将 [le,ri][le,ri] 内的集合在 (c−lowbit(c),c](c-lowbit(c),c] 的数的数量 +1+1 。

巧妙到我说不出话。。。

区间查询一样的。

时间复杂度 O(mlog⁡nlog⁡m)O(m\log n\log m) 。

注意：空间要尽可能开得大！！！

CODE:CODE:

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
#include<bits/stdc++.h>
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
#define int long long
inline int read(){
	int x=0;bool p=1;char ch=gc();
	while (!isdigit(ch)) ch=='-'?p=0:0,ch=gc();
	while ( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^'0'),ch=gc();
	return p?x:-x;
}
void print(int x){ if (x<0) pc('-'),x=-x;if (x>9) print(x/10);pc('0'+x%10); }
const int N=5e4+5;
struct node{
	int val,tag;
} G[N];int idx,maxn,v[N],logmaxn;
inline bool cmpval(node a,node b){ return a.val>b.val; }
bool qtag[N];int ql[N],qr[N],qc[N];
int n,m,tot;
int T[N*301],son[N*301][2],lz[N*301];
inline int qson(int x,int y){ return (son[x][y])?(son[x][y]):(son[x][y]=++tot); }
inline void Add(int k,int l,int r,int v){ T[k]+=(r-l+1)*v,lz[k]+=v; }
inline void pushdown(int k,int l,int r,int mid){
	if (l==r||!lz[k]) return;
	Add(qson(k,0),l,mid,lz[k]),Add(qson(k,1),mid+1,r,lz[k]);
	lz[k]=0;
}
inline void pushup(int k){ T[k]=T[qson(k,0)]+T[qson(k,1)]; }
inline int Query(int k,int l,int r,int le,int ri){
	if (l>=le&&r<=ri) return T[k];
	int mid=l+r>>1,res=0;pushdown(k,l,r,mid);
	if (mid>=le) res+=Query(qson(k,0),l,mid,le,ri);
	if (mid< ri) res+=Query(qson(k,1),mid+1,r,le,ri);
	return res;
}
inline void Modify(int k,int l,int r,int le,int ri){
	if (l>=le&&r<=ri) return Add(k,l,r,1);
	int mid=l+r>>1,res=0;pushdown(k,l,r,mid);
	if (mid>=le) Modify(qson(k,0),l,mid,le,ri);
	if (mid< ri) Modify(qson(k,1),mid+1,r,le,ri);
	pushup(k);
}
inline void I(int le,int ri,int c){ for (;c<=maxn;c+=c&-c) Modify(c,1,n,le,ri); }
inline int Findk(int le,int ri,int k){
	int res=0;
	R(i,logmaxn,0){
		if (res+(1<<i)>maxn) continue;
		int d=Query(res+(1<<i),1,n,le,ri);
		if (d<k) k-=d,res+=(1<<i);
	}
	return res+1;
}
signed main(){
	n=read(),m=read();
	F(i,1,m){
		qtag[i]=read()&1,ql[i]=read(),qr[i]=read(),qc[i]=read();
		if (qtag[i]) G[++idx].tag=i,G[idx].val=qc[i];
	}
	std::sort(G+1,G+1+idx,cmpval);
	int pre=N;
	F(i,1,idx){
		if (G[i].val!=pre) pre=G[i].val,v[++maxn]=pre;
		qc[G[i].tag]=maxn;
	}
	logmaxn=log2(maxn),tot=maxn;
	F(i,1,m){
		if (qtag[i]) I(ql[i],qr[i],qc[i]);
		else print(v[Findk(ql[i],qr[i],qc[i])]),pc('\n');
	}
	return 0;
}