【树套树】[Mz]树套树练习

主席树, 树状数组, 线段树

传送门：CodeVS4646

思路：

这道题我先想了一个智障的线段树套线段树做法，似乎是$O(nlog_2^3n)$，然后果断T了。。。。。。

于是学了一下树状数组套主席树的做法：

  • 首先静态区间k小是利用主席树维护一个前缀中的权值个数，然而修改GG
  • 于是由于是区间和，把前缀换成用树状数组维护，没了。。。

讲道理这种题还是看代码比较稳：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot,x,y,k,a[120000],root[120000],X[120000],Y[120000],sum[18000000],ls[18000000],rs[18000000];
void add(int last,int l,int r,int &rt,int w,int z){
	rt=++tot; sum[rt]=sum[last]+z;
	ls[rt]=ls[last]; rs[rt]=rs[last];
	if (l==r) return;
	int mid=(l+r)>>1;
	if (w<=mid) add(ls[last],l,mid,ls[rt],w,z);
	else add(rs[last],mid+1,r,rs[rt],w,z);
}
int query(int l,int r,int k){
	if (l==r) return l;
	int mid=(l+r)>>1,sumx=0,sumy=0;
	for (int i=1;i<=X[0];i++) sumx+=sum[ls[X[i]]];
	for (int i=1;i<=Y[0];i++) sumy+=sum[ls[Y[i]]]; 
	if (sumy-sumx>=k){
		for (int i=1;i<=X[0];i++) X[i]=ls[X[i]];
		for (int i=1;i<=Y[0];i++) Y[i]=ls[Y[i]];
		return query(l,mid,k);
	}
	else{
		for (int i=1;i<=X[0];i++) X[i]=rs[X[i]];
		for (int i=1;i<=Y[0];i++) Y[i]=rs[Y[i]];
		return query(mid+1,r,k-(sumy-sumx));
	}
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		for (int j=i;j<=n;j+=j&(-j)) add(root[j],1,n,root[j],a[i],1);
	}
	
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&k);
		if (x==0){
			for (int j=y;j<=n;j+=j&(-j)) add(root[j],1,n,root[j],a[y],-1);
			a[y]+=k;
			for (int j=y;j<=n;j+=j&(-j)) add(root[j],1,n,root[j],a[y],1);
		}
		else{
			X[0]=Y[0]=0;
			for (int j=x-1;j;j-=j&(-j)) X[++X[0]]=root[j];//取出对1~x-1前缀产生贡献的树状数组区间
			for (int j=y;j;j-=j&(-j)) Y[++Y[0]]=root[j];//取出对1~y前缀产生贡献的树状数组区间
			printf("%d\n",query(1,n,k));
		}
	}
	
	return 0;
}