首页 > 其他分享 >Luogu P1110 [ZJOI2007] 报表统计

Luogu P1110 [ZJOI2007] 报表统计

时间:2024-07-04 11:43:00浏览次数:21  
标签:P1110 元素 MIN int Luogu Treap1 GAP ii ZJOI2007

题目描述

给定一个长度为 \(n\) 的整数序列 \(a\),有以下三种操作:

  • INSERT i x:\(i\) 位置后面添加一个新元素 \(x\),下一个元素挂在这个元素后面。
  • MIN_GAP:查询相邻元素差值的最小值。
  • MIN_SORT_GAP:查询元素中最接近的两个元素的差值。

题目解析

平衡树经典题目。建立 \(2\) 棵平衡树,分别维护所谓的相邻元素差值与最接近的差值,也就是 MIN_GAPMIN_SORT_GAP

对于 Insert 和 Delete 操作;

  • MIN_GAP 平衡树维护的是相邻差值。先将原本的所有相邻元素之间的差值 Insert 进平衡树,再记录一个 \(lst_i\) 表示以 \(a_i\) 为开头的添加于 \(i\) 后的上一个元素。对于一个 \(1 \le i \le n\),每一次 INSERT i x 操作,上一次的 \(lst_i\) 与 \(a_{i+1}\) 之间的相邻关系消除,即 Delete 掉 \(|lst_i-a_{i+1}|\);本次增加 \(lst_i\) 与 \(x\) 之间的相邻关系,以及 \(x\) 与 \(a_{i+1}\) 之间的相邻关系,即 Insert 进 \(|lst_i-x|\) 和 \(|x-a_{i+1}|\)。

  • MIN_SORT_GAP 平衡树维护的是最接近的两个元素的差值?其实也不然。先将 \(a\) 数组的所有元素 Insert 进去,每次 INSERT i x 操作也就是 Insert 进去 \(x\)。只是每个元素在 Insert 进去前先用当前他与 pre 和 nxt 之间的差值更新一下答案而已,运用平衡树,这就相当于去求排序后所有相邻元素之间的差值的最小值。

最终对于 MIN_GAP 的询问,输出 rk 为 \(1\) 的元素即可;对于 MIN_SORT_GAP 的询问,输出记录最小值的变量即可。

实现写的是 FHQ-Treap,FHQ-Treap 太好写辣(

代码实现

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,ans=INT_MAX;
int a[1145141],b[1145141],lsta[1145141],lstb[1145141];
int rt1,rt2,l1=0,r1=0,l2=0,r2=0,px1,px2,cnt1=0,cnt2=0;
struct node{
	int l,r,siz,val,randval;
}Treap1[1145141],Treap2[1145141];
void pushup1(int p){
	Treap1[p].siz=Treap1[Treap1[p].l].siz+Treap1[Treap1[p].r].siz+1;
	return ;
}
void build1(int x){
	++cnt1;
	Treap1[cnt1].l=Treap1[cnt1].r=0;
	Treap1[cnt1].siz=1;
	Treap1[cnt1].val=x;
	Treap1[cnt1].randval=rand();
	return ;
}
void Split1(int p,int val,int &l,int &r){
	if(!p){
		l=r=0;
		return ;
	}
	if(Treap1[p].val<=val){ 
		l=p; 
		Split1(Treap1[p].r,val,Treap1[p].r,r); 
	}else{
		r=p; 
		Split1(Treap1[p].l,val,l,Treap1[p].l); 
	}
	pushup1(p);
	return ;
}

int Merge1(int l,int r){
	if(!l||!r) return l+r;
	if(Treap1[l].randval<=Treap1[r].randval){
		Treap1[l].r=Merge1(Treap1[l].r,r);
		pushup1(l);
		return l;
	}
	Treap1[r].l=Merge1(l,Treap1[r].l);
	pushup1(r);
	return r;
}

void Insert1(int x){
	Split1(rt1,x,l1,r1);
	build1(x);
	rt1=Merge1(Merge1(l1,cnt1),r1);
	return ;
}

void Delete1(int x){
	Split1(rt1,x,l1,r1);
	Split1(l1,x-1,l1,px1);
	px1=Merge1(Treap1[px1].l,Treap1[px1].r);
	rt1=Merge1(Merge1(l1,px1),r1);
	return ;
}

int rk1(int p,int k){
	if(k==Treap1[Treap1[p].l].siz+1) return p;
	if(k<Treap1[Treap1[p].l].siz+1) return rk1(Treap1[p].l,k);
	k-=Treap1[Treap1[p].l].siz+1;
	return rk1(Treap1[p].r,k);
}
void pushup2(int p){
	Treap2[p].siz=Treap2[Treap2[p].l].siz+Treap2[Treap2[p].r].siz+1;
	return ;
}
void build2(int x){
	++cnt2;
	Treap2[cnt2].l=Treap2[cnt2].r=0;
	Treap2[cnt2].siz=1;
	Treap2[cnt2].val=x;
	Treap2[cnt2].randval=rand();
	return ;
}
void Split2(int p,int val,int &l,int &r){
	if(!p){
		l=r=0;
		return ;
	}
	if(Treap2[p].val<=val){ 
		l=p; 
		Split2(Treap2[p].r,val,Treap2[p].r,r); 
	}else{
		r=p; 
		Split2(Treap2[p].l,val,l,Treap2[p].l); 
	}
	pushup2(p);
	return ;
}

int Merge2(int l,int r){
	if(!l||!r) return l+r;
	if(Treap2[l].randval<=Treap2[r].randval){
		Treap2[l].r=Merge2(Treap2[l].r,r);
		pushup2(l);
		return l;
	}
	Treap2[r].l=Merge2(l,Treap2[r].l);
	pushup2(r);
	return r;
}

void Insert2(int x){
	Split2(rt2,x,l2,r2);
    if(Treap2[l2].siz){
        int now=l2;
        while(Treap2[now].r) now=Treap2[now].r;
        ans=min(ans,abs(x-Treap2[now].val));
    }
    if(Treap2[r2].siz){
        int now=r2;
        while(Treap2[now].l) now=Treap2[now].l;
        ans=min(ans,abs(Treap2[now].val-x));
    }
	build2(x);
	rt2=Merge2(Merge2(l2,cnt2),r2);
	return ;
}

void Delete2(int x){
	Split2(rt2,x,l2,r2);
	Split2(l2,x-1,l2,px2);
	px2=Merge2(Treap2[px2].l,Treap2[px2].r);
	rt2=Merge2(Merge2(l2,px2),r2);
	return ;
}

signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1;i<n;i++) Insert1(abs(a[i+1]-a[i]));
	for(int i=1;i<n;i++) Insert2(a[i]);
	for(int i=1;i<=n;i++) lsta[i]=a[i];
	while(q--){
		string op;
		cin>>op;
		if(op=="INSERT"){
			int ii,x;
			cin>>ii>>x;
            Insert2(x);
			if(ii==n){
				Delete1(abs(a[n]-lsta[n]));
				Insert1(abs(x-lsta[n]));
				lsta[n]=x; 
			}
			else{
				Delete1(abs(a[ii+1]-lsta[ii]));
				Insert1(abs(x-lsta[ii]));
				Insert1(abs(a[ii+1]-x));
				lsta[ii]=x;
			}
		}
		else if(op=="MIN_GAP") cout<<Treap1[rk1(rt1,1)].val<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}

标签:P1110,元素,MIN,int,Luogu,Treap1,GAP,ii,ZJOI2007
From: https://www.cnblogs.com/HAM-qwq/p/18283342

相关文章

  • Luogu P6104 [EER2] 相同的数字
    令\(\text{nxt}_i\)为\(i\)之后的第一个质数。考虑最后\(a_i\)会变成什么。首先第一种就是直接变为\(\maxa_i\)。其次还发现可能变为\(\operatorname{nxt}_{\maxa_i}\)。对于其他的,可以证明一定不优于这两种,因为其他的情况无非就是在这基础上继续跳\(\operatorname......
  • Luogu P10674 【MX-S1-T3】电动力学
    首先考虑这个\(S,T\)肯定需要固定一个算另一个的方案数。如果固定\(S\),会发现非常不好给\(T\)下限制。于是考虑固定\(T\),对\(S\)计数。首先考虑如果\(T\)只有\(2\)个点\(x,y\),该怎么对\(S\)计数。考虑到这个简单路径的定义是不经过重点,考虑找到点双。然后能......
  • Luogu P9542 [湖北省选模拟 2023] 棋圣 alphago
    2023.08.19:修改了一处笔误。手玩发现对于一颗生成树,如果存在至少一个点的度数\(>2\)(即不为链),那么肯定能使得所有棋子都在一条边的两个端点上。因为有度数\(>2\)的点的存在,这里就可以合并与其相连的点的棋子。先考虑非链的情况的答案,记两部分棋子黑白棋子颜色分别为\(c(a/......
  • Luogu P6864 [RC-03] 记忆
    先考虑没有\(3\)操作该怎么做。对于当前字符串把其分成多组互不包含的括号的形式,即\((\cdots)()()\)这样,考虑经过\(1/2\)操作后对互不包含的括号组数\(b\)和答案\(v\)会产生什么影响。\(1\)操作,加上过后便会多上一组互不包含的括号,\(b\leftarrowb'+1\),同时这个......
  • [刷题笔记] Luogu P1612 [yLOI2018] 树上的链
    ProblemDescriptionDescription给定一棵有\(n\)个节点的树。每个节点有一个点权和一个参数。节点\(i\)的权值为\(w_i\),参数为\(c_i\)。\(1\)是这棵树的根。现在,对每个节点\(u\)(\(1\lequ\leqn\)),请在树上你找到最长的一条链\(v_1,v_2,\dotsv_m\),满足如下条件:......
  • [luoguP10608]双人游戏
    题目信息原题链接来源:[LGR-190]2024洛谷6月月赛IIDiv1T1/Div2T3题意长度为\(n\)的序列\(s\),其中只包含B,W和\(m\)个_。给定长度为\(m\)的序列\(O=[\langc_1,x_1\rang,\langc_2,x_2\rang,\cdots,\langc_m,x_m\rang](c_i\in\{\mathtt{R},\mathtt{M}\},s_{x_i}=\text{'_'......
  • [lnsyoj166/luoguP2822/NOIP2016提高组] 组合数问题
    题意原题链接给定\(n,m,k\),对于所有的\(0\lei\len,0\lej\lemin\{i,m\}\),有多少对\((i,j)\)满足\(k|(^i_j)\)sol在解决组合数问题时,若遇到\(n,m\le2000\)的情况,可以使用递推法(杨辉三角)来进行\(O(n^2)\)的预处理,再\(O(1)\)直接调用递推法求组合数\[(^n_m)=(^{n-1}_m)+(......
  • [lnsyoj284/luoguP2286/HNOI2004]宠物收养场
    题意原题链接每个宠物和领养人有一个对应的特点值\(a\),当领养人过多时,若添加一个特点值为\(a_p\)的宠物,则查询收养店中特点值最接近\(a_p\),为\(a_q\)的领养人(\(<a_p\)的值优先),将答案累加\(|a_q-a_p|\),然后删除该领养人,否则在收养店中添加一个领养人。反之亦然。求最终的答案\(......
  • [lnsyoj98/luoguP1403]约数研究
    题意原题链接求\(1\simn\)的约数个数和sol直接算很困难,考虑换一个角度求\(1\simn\)的约数个数和,等价于求\(1\simn\)分别是范围内几个数的约数对于第\(i\)个值,在\(1\simn\)中,存在\(i,2\cdoti,3\cdoti,\cdots,k\cdoti\),共\(\lfloor\frac{n}{i}\rfloor\)因此,最终......
  • C138 线段树分治 P2056 [ZJOI2007] 捉迷藏
    视频链接:C138线段树分治P2056[ZJOI2007]捉迷藏_哔哩哔哩_bilibili   P2056[ZJOI2007]捉迷藏-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树分治O(nlognlogn)#include<iostream>#include<cstring>#include<algorithm>#include<vector>#inclu......