Reincarnation

正因为梦易碎，才格外美好。

P2617 Dynamic Rankings

发表于 更新于 分类于
本文字数： 5k 阅读时长 ≈ 5 分钟

单点修改区间 小值。

题目出处：洛谷
评测链接：https://www.luogu.com.cn/problem/P2617

如果没有单点修改的话，这就是道主席树板子题，开一个大小为 大小的权值线段树就可以把问题解决了。

考虑怎么让主席树带修。

题解

根据我们前缀差分的知识我们知道，这是一种 的结构，即线性预处理与单时查询，所以每一次修改也都是 的，所以我们需要平衡规划，优化到 ，而显而易见的，将前缀差分优化成这个样子的数据结构我们还是有所了解—— 和线段树。

考虑本来那种在权值线段树上二分改成在 棵前缀 上的权值线段树上同步二分，这样的话，我们就可以让我们当前的查询区间变得完整，从而做到在区间 中找 值。

那么，思路就很明了了（树套树就是这样，没有啥技巧，有的只是码量）。

用 棵权值线段树组成 ，然后每次修改和查询都调用其中的 棵，二分复杂度 ，这样的话，时间复杂度可以在 中解决，常数是一个大问题。空间复杂度 ，考虑到是权值线段树，所以要离线下来离散化之后建树。

AC 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
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// ----- Eternally question-----
// Problem: P2617 Dynamic Rankings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2617
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2022-12-25 09:48:20
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N,Q,Val[MAXN],Len;
std::vector<int>Nums;
struct PST
{
	#define ls(p) Tr[p].lc
	#define rs(p) Tr[p].rc
	int Idx,Rt[MAXN<<4];
	struct Segment
	{
		int lc,rc,val;
	}Tr[MAXN<<8];
	inline void pushUp(int p){ Tr[p].val=Tr[ls(p)].val+Tr[rs(p)].val; }
	void modifyX(int &p,int l,int r,int x,int v)
	{
		if(!p) p=++Idx;
		Tr[p].val+=v;
		if(l==r) return ;
		int mid=(l+r)>>1;
		if(x<=mid) modifyX(ls(p),l,mid,x,v);
		else modifyX(rs(p),mid+1,r,x,v);
	}
}Tr;
inline int lowbit(int x){ return x&(-x); }
inline void add(int x,int k,int v){ for(;x<=Nums.size();x+=lowbit(x)) Tr.modifyX(Tr.Rt[x],1,Nums.size(),k,v); }
int St1[MAXN],St2[MAXN],cur1,cur2;
inline void getSet(int x,int *s,int &p)
{
	p=0;
	for(;x;x-=lowbit(x)) s[++p]=Tr.Rt[x];
}
int queryKth(int l,int r,int k)
{
	if(l==r) return l;
	int mid=(l+r)>>1,res=0;
	for(int i=1;i<=cur1;++i) res+=Tr.Tr[Tr.Tr[St1[i]].lc].val;
	for(int i=1;i<=cur2;++i) res-=Tr.Tr[Tr.Tr[St2[i]].lc].val;
	if(res>=k)
	{
		for(int i=1;i<=cur1;++i) St1[i]=Tr.Tr[St1[i]].lc;
		for(int i=1;i<=cur2;++i) St2[i]=Tr.Tr[St2[i]].lc;
		return queryKth(l,mid,k);
	}
	else
	{
		for(int i=1;i<=cur1;++i) St1[i]=Tr.Tr[St1[i]].rc;
		for(int i=1;i<=cur2;++i) St2[i]=Tr.Tr[St2[i]].rc;
		return queryKth(mid+1,r,k-res);
	}
}
struct Qry
{
	int opt,l,r,k,x,v;
}qry[MAXN];
char Opt[3];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(Val[i]),Nums.push_back(Val[i]);
	for(int i=1;i<=Q;++i)
	{
		int ql,qr,qk,qx,qv;
		scanf("%s",Opt+1);
		if(Opt[1]=='Q')
		{
			read(ql,qr,qk);
			qry[i]=(Qry){1,ql,qr,qk,0,0};
		}
		else
		{
			read(qx,qv);
			qry[i]=(Qry){0,0,0,0,qx,qv};
			Nums.push_back(qv);
		}
	}
	std::sort(Nums.begin(),Nums.end());
	Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
	for(int i=1;i<=N;++i) Val[i]=std::lower_bound(Nums.begin(),Nums.end(),Val[i])-Nums.begin()+1;
	for(int i=1;i<=Q;++i) if(!qry[i].opt) qry[i].v=std::lower_bound(Nums.begin(),Nums.end(),qry[i].v)-Nums.begin()+1;
	for(int i=1;i<=N;++i) add(i,Val[i],1);
	for(int i=1;i<=Q;++i)
	{
		if(qry[i].opt)
		{
			getSet(qry[i].r,St1,cur1);
			getSet(qry[i].l-1,St2,cur2);
			write(Nums[queryKth(1,Nums.size(),qry[i].k)-1],'\n');
		}
		else
		{
			add(qry[i].x,Val[qry[i].x],-1);
			add(qry[i].x,qry[i].v,1);
			Val[qry[i].x]=qry[i].v;
		}
	}
	return 0;
}
/*

*/

另话

好巧不巧的是，这道题有“双倍经验”。

题目来源：

评测链接：https://www.luogu.com.cn/problem/P4119

值域从 变成了 ， 同阶 不变。但是时限从 变成了 。

然后这道题带修主席树过不了，因为这是「最初分块」，也称「第一分块」。当然，我这里是不会讲的啦，只是提一嘴。

有兴趣的同学可以去卡卡常找虐。

相关文章