专栏文章

P14085 [ICPC 2023 Seoul R] Apricot Seeds 題解

DDengDuck鄧德
P14085题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minr4t0b
此快照首次捕获于
2025/12/02 06:59
3 个月前
此快照最后确认于
2025/12/02 06:59
3 个月前
查看原文
好牛啊這個。
有這樣一個結論，對於一個前綴 [1,x][1,x]，經過 kk 輪的冒泡排序，[1,x][1,x] 的數字會變成 [1,x+k][1,x+k] 的前 xx 小的數字。
證明
首先 [x+k+1,n][x+k+1,n] 的數字肯定不可能出現，因為每個數字每次最多左移一位。
進過 kk 輪之後，[1,x+k][1,x+k] 中前 kk 大的數字必然已經不在 [1,x][1,x] 的位置內，因此 [1,x][1,x] 只能是 [1,x+k][1,x+k] 中前 xx 小的數字。
這道題目每次操作相當於抽出來一個子區間做操作然後子區間內區間查詢，先轉成前綴和形式然後主席樹實現查詢前 kk 小的和即可。
CPP
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+5;
int n,m,A[N],Rt[N],TOT;
struct Tree{int L,R,Sz;LL S;}t[N*50];
#define Ls(x) t[x].L
#define Rs(x) t[x].R
#define Mid (L+R>>1)
void Upd(int &u,int L,int R,int x)
{
	t[++TOT]=t[u],u=TOT;
	t[u].Sz++,t[u].S+=x;
	if(L==R)return;
	if(x<=Mid)Upd(Ls(u),L,Mid,x);
	else Upd(Rs(u),Mid+1,R,x);
}
LL Qry(int u,int u2,int L,int R,int x)
{
	if(L==R)return 1ll*x*L;
	if(x<=t[Ls(u)].Sz-t[Ls(u2)].Sz)return Qry(Ls(u),Ls(u2),L,Mid,x);
	return t[Ls(u)].S-t[Ls(u2)].S+Qry(Rs(u),Rs(u2),Mid+1,R,x-(t[Ls(u)].Sz-t[Ls(u2)].Sz));
}
const int Inf=1e9;
inline LL Qry(int L,int R,int x,int v)
{
	if(!v)return 0;
	return Qry(Rt[min(R,L+v+x-1)],Rt[L-1],1,Inf,v);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&A[i]),Rt[i]=Rt[i-1],Upd(Rt[i],1,Inf,A[i]);
	for(int i=1,L,R,t,x,y;i<=m;i++)
	{
		scanf("%d%d%d%d%d",&L,&R,&t,&x,&y);
		printf("%lld\n",Qry(L,R,t,y)-Qry(L,R,t,x-1));
	}
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...