BZOJ5011 & 洛谷4065 & LOJ2275:[JXOI2017]颜色——题解
2024-09-04 13:00:39
https://www.lydsy.com/JudgeOnline/problem.php?id=5011
https://www.luogu.org/problemnew/show/P4065
可怜有一个长度为n的正整数序列Ai,其中相同的正整数代表着相同的颜色。现在可怜觉得这个序列太长了,于是她决定选择一些颜色把这些颜色的所有位置都删去。删除颜色i可以定义为把所有满足Aj=i的位置j都从序列中删去。然而有些时候删去之后,整个序列变成了好几段,可怜不喜欢这样,于是她想要知道有多少种删去颜色的方案使得最后剩下来的序列非空且连续。例如颜色序列{1,2,3,4,5},删除颜色3后序列变成了{1,2}和{4,5}两段,不满足条件。而删除颜色1后序列变成了{2,3,4,5},满足条件。两个方案不同当且仅当至少存在一个颜色i只在其中一个方案中被删去。
套路裸,但我不会啊。
参考:https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-p4065
这个人的讲解有点长我就转述一下吧。
首先惯用的套路:枚举右端点,用线段树查找有多少个可能的左端点。
于是我们设$mn[i]-mx[i]$表示$i$颜色所在的区间范围。
显然当右端点$r>=mx[i]$的时候左端点一定不能在$mn[i]+1-mx[i]$这段区间中,于是用线段树维护之。
并且对于$mx[i]>r$的颜色$i$也是一定要被删除的,这个可以帮助我们确定左端点的下界。
我们显然要找的$l$为$mx[col[l]]>r$并且离$r$最近的点+1(因为$l$这个点本身是不可取的)。
我们还能发现随着$r$的增大$l$在单调不增,于是可以用单调栈来维护。
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3e5+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
int n,b[N],mx[N],mn[N];
int tr[N*],lz[N*];
stack<int>q;
inline void push(int a,int l,int r){
if(lz[a]){
int mid=(l+r)>>;
lz[a<<]=lz[a<<|]=lz[a];
tr[a<<]=mid-l+;tr[a<<|]=r-mid;
lz[a]=;
}
}
void mdy(int a,int l,int r,int l1,int r1){
if(l1>r1||r<l1||r1<l)return;
if(l1<=l&&r<=r1){
tr[a]=r-l+;lz[a]=;
return;
}
push(a,l,r);
int mid=(l+r)>>;
mdy(a<<,l,mid,l1,r1);mdy(a<<|,mid+,r,l1,r1);
tr[a]=tr[a<<]+tr[a<<|];
}
int qry(int a,int l,int r,int l1,int r1){
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1)return tr[a];
push(a,l,r);
int mid=(l+r)>>;
return qry(a<<,l,mid,l1,r1)+qry(a<<|,mid+,r,l1,r1);
}
int main(){
int t=read();
while(t--){
n=read();
while(!q.empty())q.pop();
for(int i=;i<=n;i++)b[i]=read();
for(int i=;i<=n;i++)mx[i]=,mn[i]=N;
for(int i=;i<=n*;i++)lz[i]=tr[i]=;
for(int i=;i<=n;i++)mx[b[i]]=max(mx[b[i]],i);
for(int i=;i<=n;i++)mn[b[i]]=min(mn[b[i]],i);
ll sum=;
for(int i=;i<=n;i++){
if(i==mx[b[i]])
mdy(,,n,mn[b[i]]+,mx[b[i]]);
else q.push(i);
while(!q.empty()){
if(mx[b[q.top()]]>i)break;
q.pop();
}
int l=q.empty()?:q.top();
if(i!=l)sum+=i-l-qry(,,n,l+,i);
}
printf("%lld\n",sum);
}
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
最新文章
- Solved: “Cannot execute a program. The command being executed was \roslyn\csc.exe”
- requirejs使用
- HQL查询——聚集函数
- overfitting过拟合
- C/C++在Java项目、Android和Objective-C三大平台下实现混合编程
- 21.Android之SQLite数据库学习
- BZOJ 1010 玩具装箱toy(四边形不等式优化DP)(HNOI 2008)
- 关于JDK,tomcat,MyEclipse的配置
- iOS - Swift NSRect 位置和尺寸
- Java -- Thread中start和run方法的区别
- ViewPager 详解(五)-----使用Fragment实现ViewPager滑动
- JAVA泛型那些事儿
- Ionic开发笔记
- Java中的i=i++
- 点击<;a>;页面跳转解决办法/跨域请求,JSONP
- 【转】python3 内循环中遍历map,遍历一遍后再次进入内循环,map为空
- Spring Boot 与 OAuth2 官方最详细教程
- 【ARTS】01_20_左耳听风-20190325~20190331
- Python全栈学习_day001作业
- [Oracle]包含了MVIEW的表领域,在进行导出,表领域改名,再导入后,MVIEW会消失不见。
热门文章
- spl_autoload_register()函数
- 2019年猪年海报PSD模板-第五部分
- Qt-QML-Popup,弹层界面编写
- Selenium 入门到精通系列:一
- (转载)Unity3d中的属性(Attributes)整理
- JSON.parse() 与 eval()
- 《Effective C++》读书笔记 条款02 尽量以const,enum,inline替换#define
- 一个五位数ABCDE乘以9,得到EDCBA,求此五位数
- Bcp 使用心得【转】
- ZOJ 2760 How Many Shortest Path(最短路径+最大流)