分享例题两则主要是分享一种 \(\text{trick}\) 。
\(\text{UVA1608}\)
题目描述
给定一个长度为 \(n\) 的序列 \(a\) ，如果 \(a\) 的每一个子串都存在至少一个元素只出现了一次，输出 \(\text{Non-boring}\) 。反之，输出 \(\text{Boring}\) 。\(n \leqslant 2\times 10^5\) 。
思路点拨
类似于这样的题目，可以按照我下述的方法进行思考。
对于一个元素而言，我们记录上一个与他值相同的元素的下标 \(pre_i\) ，下一个与他元素值相同的下标 \(suc_i\) 。那么对于左端点在 \([pre_i+1,i]\) 并且右端点在 \([i,suc_i-1]\) 的区间就是满足题目要求的。我们考虑建立一个平面直角坐标系，以区间的左端点作为横坐标，以区间的右端点作为纵坐标。那么一个元素 \(a_i\) 产生的贡献就可以看作一个以 \((pre_i+1,i)\) 为左下角，以 \((i,suc_i-1)\) 为右上角的矩形。
如果对于点 \((l,r) (1 \leqslant l \leqslant r\leqslant n)\) 都被至少一个矩形覆盖，我们可以判断为有解。现在我们需要使用某种方法来加速这一过程，并且不难想到使用扫描线算法。如果这些矩形的面积并为 \(\dfrac{n(n+1)}{2}\) ，那么我们就认为是有解的。
时间复杂度 \(O(T\times n \log n)\) ，可以通过。
\(\text{code}\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int MAXN=4e5+10;
int T,n,a[MAXN];
map<int,int> pre,suc;
int lef[MAXN],rig[MAXN];
struct node{
int l,r,h,w;
bool friend operator<(const node &A,const node &B){
return A.h<B.h;
}
}line[MAXN];
struct seg{
int l,r;
int sum,len;
}t[MAXN<<3];
void pushup(int i){
if(t[i].sum) t[i].len=t[i].r-t[i].l+1;
else t[i].len=t[i<<1].len+t[i<<1|1].len;
}
void build(int i,int l,int r){
t[i].l=l,t[i].r=r;
t[i].sum=t[i].len=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
void update(int i,int l,int r,int w){
if(l<=t[i].l&&t[i].r<=r){
t[i].sum+=w;
pushup(i);
return ;
}
if(t[i].l>r||t[i].r<l) return ;
update(i<<1,l,r,w);
update(i<<1|1,l,r,w);
pushup(i);
}
signed main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
pre.clear(),suc.clear();
for(int i=1;i<=n;i++){
lef[i]=pre[a[i]];
if(!lef[i]) lef[i]=0;
pre[a[i]]=i;
}
for(int i=n;i;i--){
rig[i]=suc[a[i]];
if(!rig[i]) rig[i]=n+1;
suc[a[i]]=i;
}
for(int i=1;i<=n;i++){
//(lef[i]+1,i),(i,rig[i]-1)
line[(i<<1)-1].l=line[i<<1].l=lef[i]+1;
line[(i<<1)-1].r=line[i<<1].r=i;
line[(i<<1)-1].h=i,line[i<<1].h=rig[i];
line[(i<<1)-1].w=1,line[i<<1].w=-1;
}
sort(line+1,line+n*2+1);
build(1,1,n);
int ans=0,pos=1;
for(int i=1;i<=n;i++){
while(pos<=n*2&&line[pos].h<=i){
update(1,line[pos].l,line[pos].r,line[pos].w);
pos++;
}
ans+=t[1].len;
}
if(ans==n*(n+1)/2) cout<<"non-boring"<<endl;
else cout<<"boring"<<endl;
}
return 0;
}