首页 > 其他分享 >项链 题解

项链 题解

时间:2023-10-04 16:34:30浏览次数:40  
标签:int 题解 void long 端点 项链 lz define

image

随机化写法很强,但是这里不说。

这里只记录数据结构写法。

枚举右端点,快速找左端点。

首先一种合法的方案中,一种颜色只会有两种情况。全部在区间中及全部在区间外。

对于区间外的情况,也就是最后一次出现的位置 \(p\) 大于右端点 \(r\),我们可以维护当前枚举右端点之前的所有颜色非最后一次出现的点的最大位置,但为了方便后续维护,我们对于每种颜色只维护最后一个该颜色非最后一次出现的点。这里可以用可删堆实现。即当遍历到一个点时,将上一个该颜色的点从堆中删除。

对于区间内的情况,即后一次出现的位置 \(p\) 小于等于右端点 \(r\),则这个颜色第一次出现的位置的下一个位置到当前右端点都不能作为区间的左端点,我们可以在这个区间打标记。

最后堆顶即为左端点,答案为左右端点距离减去中间被删去的点的数量。

点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define int long long
#define debug cout<<"DEBUG"<<endl;
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define imp map<int,int>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
const int N=1e6+5; 
int n,k,a[N],st[N],ans=0,pos[N];
vi g[N];
ll seg[N*4],lz[N*4];
struct pq{
	priority_queue<int> x,y;
	void ins(int d){x.push(d);}
	void del(int d){y.push(d);}
	int tp(){
		while(x.size()&&y.size()&&x.top()==y.top()){
			x.pop();y.pop();
		}
		return x.top();
	}
}q;
void pushdown(int p,int l,int r){
	if(!lz[p]) return; 
	int mid=(l+r)>>1;
	lz[ls(p)]=lz[p];
	lz[rs(p)]=lz[p];
	seg[ls(p)]=mid-l+1;
	seg[rs(p)]=r-mid;
	lz[p]=0;
}
void change(int p,int nx,int ny,int l,int r){
	if(l<=nx&&ny<=r){
		seg[p]=ny-nx+1;
		lz[p]=1;
		return;
	}
	pushdown(p,nx,ny);
	int mid=(nx+ny)>>1;
	if(l<=mid) change(ls(p),nx,mid,l,r);
	if(mid<r) change(rs(p),mid+1,ny,l,r);
	seg[p]=seg[ls(p)]+seg[rs(p)];
}
int query(int p,int nx,int ny,int l,int r){
	if(l<=nx&&ny<=r){
		return seg[p];
	}
	pushdown(p,nx,ny);
	int mid=(nx+ny)>>1;
	int sum=0;
	if(l<=mid) sum+=query(ls(p),nx,mid,l,r);
	if(mid<r) sum+=query(rs(p),mid+1,ny,l,r);
	return sum;
}
signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",a+i);
		g[a[i]].pb(i);
		pos[i]=g[a[i]].size();
	}
	q.ins(0);
	for(int r=1;r<=n-1;r++){
		if(pos[r]!=1){
			q.del(g[a[r]][pos[r]-2]);	
		}
		if(pos[r]==g[a[r]].size()){
			if(g[a[r]].size()>1) change(1,1,n,g[a[r]][0]+1,r);
			int l=q.tp()+1;
			int res=query(1,1,n,l,r);
			ans+=r-l+1-res;
		}else{
			q.ins(r);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

标签:int,题解,void,long,端点,项链,lz,define
From: https://www.cnblogs.com/victoryang-not-found/p/17742408.html

相关文章

  • CF1203(Div. 3) 题解(C to F1)
    由于太懒了,所以不想(会)写\(\texttt{AB}\)和\(\texttt{F2}\)。CCommonDivisors题解题目大意给定一个长度为\(n\)的数列\(\{a_i\}\),求\(\sigma(\gcd\limits_{i\in[1,n]}\{a_i\})\)。解题思路先算出所有元素的最大公因数,如果最大公因数\(g\)为\(1\),即所有元素两两......
  • CF1873(Div. 4) 题解 (A to E)
    AShortSort题解题目大意给定一个长度为\(3\)、由\(a,b,c\)组成的字符串,问可以不变或交换两个字符是的变为\(\texttt{abc}\)。解题思路由于大小固定,所以预处理可行的字符串(仅包含\(\texttt{abcacbbaccba}\))即可。代码#include<bits/stdc++.h>usingnamespacest......
  • 题解 CF1034C【Region Separation】/ SS221116D【Xiong AK 10 IOI】
    很妙的性质题!全是意识流证明见过吗?problem每次选一个非空边集删掉,谓之曰砍树。砍树后需要满足每个连通块的点权和相同。在一个方案中可以砍很多次树,都要满足砍树后的要求。一共有多少种合法方案呢?\(n\leq10^6,1\leqa_i\leq10^9\)。solution假如我们将树砍成\(k\)个连通......
  • 传奇团子师傅题解
    传奇团子师傅题解(模拟退火)申明:本篇题解借鉴了:https://www.luogu.com.cn/blog/SDNetFriend/solution-p7218这篇博客(主要在bitset部分)。题意:给你个矩阵,包含三种颜色,一个美丽串要求你横着或者竖着或者斜着串成一串的三个颜色有特定的顺序,求拿取最多美丽串的方案是什么。题目分......
  • 【UVA 442】Matrix Chain Multiplication 题解(栈)
    假设您必须计算一个表达式,如ABCDE,其中A、B、C、D和E是矩阵。由于矩阵乘法是关联的,所以执行乘法的顺序是任意的。然而,所需的初等乘法的数量很大程度上取决于求值顺序您可以选择。例如,设A为5010矩阵,B为1020矩阵,C为205矩阵。有两个计算ABC的不同策略,即(AB)C和A(B*C)。第一个需要1500......
  • Hadoop问题解决记(2)
     1.发现问题在对HBase集群进行压力测试过程中发现,当实际写入HBase和从HBase查询的量是平时的若干倍时(集群规模10~20台,每秒读写数据量在几十万条记录的量级),导致集群的读写出现一定程度的波动。具体如下:1)写端抛出以下异常信息:org.apache.hadoop.hbase.client.RetriesExha......
  • Hadoop问题解决记(1)
    最近在测试HBase时遇到一个非常奇怪的问题:集群有7台机器,其中1台Master,6台RegionServer。但是Master只能控制其中1台RegionServer,而无法控制其他5台RegionServer。打开master的日志文件,发现以下错误信息:2011-04-2216:37:21,242WARNorg.apache.hadoop.hbase.master.Assignment......
  • 『题解』P9688
    题目传送门思路:设有两个颜色\(x_1x_2\),两端分别为\(l_1\)\(r_1\),\(l_2\)\(r_2\)。通过观察可以发现,若满足\(x_1<x_2\)且\(r_1>l_2\)则\(x_1x_2\)一定是单调不下降的。那么我们可以先预处理出一个颜色可以与前面的哪些颜色构成单调不下降,然后用dp求出最终答案......
  • 题解 Coloring Brackets
    题目链接对于括号问题,考虑区间\(dp\)。这道题的括号序列是固定的,所以直接找出每个括号对应的括号在进行转化即可。设\(f_{l,r,0/1/2,0/1/2}\)表示\(l\simr\),左括号不染色/染红色/染蓝色,右括号不染色/染红色/染蓝色的方案数。若\(l,r\)是一对匹配括号,那么f_{l,r}便可以......
  • CF1661D Progressions Covering 题解
    最详细的题解题目传送门:ProgressionsCovering阅读前人题解时,限于个人能力有限,有一些地方想了好一会儿才懂。发现很多题解都是在@SDLTF_凌亭风等作者基础上延伸,但详细程度依旧有限,尽管这篇题解亦是站在他们基础上延伸的,这篇题解更为详细的点明了很多地方。本人第一次写题解,......