一类区间查询对应答案具有单调性--维护前缀对应端点最大值
title: 一类区间查询对应答案具有单调性–维护前缀对应端点最大值
categories:
- ICPC
tags:
- null
abbrlink: 415ae054
date: 2023-05-03 00:00:00
https://www.luogu.com.cn/problem/P8773
[蓝桥杯 2022 省 A] 选数异或
题目描述
给定一个长度为 $n$ 的数列 $A_{1}, A_{2}, \cdots, A_{n}$ 和一个非负整数 $x$, 给定 $m$ 次查询, 每次询问能否从某个区间 $[l, r]$ 中选择两个数使得他们的异或等于 $x$ 。
##Solution:我们预处理每个端点对应的左边最近的配点,然后$O(1)$回答询问。
详细来说,对于每个右端点我们找到其左边最近的对应位置。进一步,我们考虑对于一个区间,我们只需要存在一个点他的对应端点在区间内就可以了,于是我们需要维护对应端点的区间最大值,RMQ问题可以线段树或者st表解决。
但我们可以利用我们只需要回答存在性,而不用具体回答,我们只需要维护前缀最大值,对于每个查询只需要检验ans[r]>=l即可
int a[N];
int ans[N];
map<int,int>mp;
//ans[i]记录前缀i中能够异或后成x的位置的最大值
void solve(){
cin>>n>>m;
int x;cin>>x;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
int tmp=a[i]^x;
if(mp.count(tmp)){
ans[i]=mp[tmp];
ans[i]=max(ans[i-1],ans[i]);
}
else {
mp[tmp]=0;
ans[i]=ans[i-1];
}
mp[a[i]]=i;
}
for(int i=1;i<=m;i++){
int l,r;cin>>l>>r;
if(ans[r]>=l)cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
}
牛课周赛38F
链接:https://ac.nowcoder.com/acm/contest/78292/F
来源:牛客网
小苯有一个长度为 $n$ 的数组 $a$,他定义一个数组是好数组,当且仅当该数组是一个回文数组,且长度严格大于 $2$。
他现在进行了 $q$ 次询问,每次询问都给出一段区间 $[l, r]$,他想知道 $a$ 在这一段区间中是否存在一个子序列是一个好数组,请你帮帮他吧。
输入描述:
Solution:首先我们注意子序列,然后会发现任何一个长度回文子序列都规约到一个长度为3的回文子序列,所以我们只需要找到对于当前右端点,我们在i-1里去寻找对应的最大位置j满足a[j]==a[i].
####对于一个区间来说,我们只需要存在i是的对应的j在区间内,也就是大于L,所以依然是维护区间对应数的最大值。值得注意区别上题的是,我们对于i是需要在i-1的前缀最大值里找答案,因为要求长度为3,所以要有一个空隙。
int n, m;
int a[N];
//我们先找对于每个右端点最近的和他相等的数,当然由于要构造长度
//大于2的回文,所以我们要营造时间差,我们只能在1-i-2开始考虑
int ans[N];
map<int,int>mp;
//我们维护上述这个性质的前缀最大值
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
if(mp.count(a[i])){
ans[i]=max(ans[i-1],mp[a[i]]);
}
else {
ans[i]=ans[i-1];
}
mp[a[i-1]]=i-1;
}
for(int i=1;i<=m;i++){
int l,r;cin>>l>>r;
if(ans[r]>=l)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
广州大学2024校赛E题
链接:https://ac.nowcoder.com/acm/contest/77448/E
来源:牛客网
这 $n$ 颗星星都会发出各种颜色的光,其中第 $i$ 个星星发出的光的编号为 $col_i$;
小A很无聊,于是以第一颗星星为根,用 $n$ 颗星星建立了一棵树;
一颗星星是 漂亮的 当且仅当以这颗星星为根的子树的所有星星颜色都不同;
到底有多少星星是漂亮的呢?
##前言:本题最大N=2e6,$O(nlogn)$做法需要非常小的常数,链式前向星登场(bushi。
##Solution:首先利用dfs序将树上问题转化到序列上。原问题等价于每次查询区间[l,r](子树dfs序连续)是不是每个数都不同,我们应该考虑预处理pre[i]表示i上次出现的最近位置,然后$O(1)$查询。同样套路的,我们只需要维护前缀最大值就可以了
int n, m;
int a[N];
vector<int>e[N];
int l[N],r[N];
int ans[N];
int tong[N];
int idx=0;
int dfn[N];
//所以dfs序标准写法在哪?
void dfs(int u,int fa){
dfn[++idx]=u;
l[u]=idx;
for(auto v:e[u]){
if(u==fa)continue;
dfs(v,u);
}
r[u]=idx;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n-1;i++){
int x;cin>>x;
e[x].push_back(i+1);
}
dfs(1,0);
for(int i=1;i<=n;i++){
int u=dfn[i];
int col=a[u];
if(tong[col]){
ans[i]=max(ans[i-1],tong[col]);
}
else {
ans[i]=ans[i-1];
}
tong[col]=i;
}
int cnt=0;
//for(int i=1;i<=n;i++)cerr<<dfn[i]<<" ";
//cerr<<endl;
for(int i=1;i<=n;i++){
int u=dfn[i];
int ql=l[u];
int qr=r[u];
//cerr<<u<<" "<<ql<<" "<<qr<<endl;
if(ans[qr]>=ql)cnt++;
}
cout<<n-cnt<<endl;
}
出题人标程:dfs过程中计算答案
#include <bits/stdc++.h>
using namespace std;
int n,dfn,ans,mx;
vector<int> a,id;
vector<vector<int>> e;
void dfs(int u){
int l=++dfn;
mx=max(mx,id[a[u]]);
id[a[u]]=dfn;
for(int v:e[u])dfs(v);
int r=dfn;
if(mx<l)++ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n;cin>>n;
a.resize(n+1);
id.resize(n+1);
e.resize(n+1);
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=2;i<=n;++i){
int x;cin>>x;
e[x].push_back(i);
}
dfs(1);
cout<<ans<<"\n";
return 0;
}