侧边栏壁纸
博主头像
落叶人生博主等级

走进秋风,寻找秋天的落叶

  • 累计撰写 130562 篇文章
  • 累计创建 28 个标签
  • 累计收到 9 条评论
标签搜索

目 录CONTENT

文章目录

Codeforces Round #549 (Div. 2)E(倍增处理按排列顺序的上一个位置)

2023-04-06 星期四 / 0 评论 / 0 点赞 / 76 阅读 / 1955 字

https://codeforces.com/contest/1143/problem/E 题意 p为n的一个排列,给出有m个数字的数组a,q次询问,每次询问a数组区间[l,r]中是否存在子序列为

... .

https://codeforces.com/contest/1143/problem/E

题意

.

p为n的一个排列,给出有m个数字的数组a,q次询问,每次询问a数组区间[l,r]中是否存在子序列为p的循环排列

.

题解

  • 预处理出值x在排列中的上一个值_p[x]
  • 从左向右扫一遍a数组,维护值x最后出现的地方/(pre[x]/),和每个位置i在排列顺序下前j个数在数组中的位置/(par[i][j]/)(倍增),然后能处理出每个位置i在排列顺序下前n-1个数的位置/(v[i]/)
  • 线段树维护v数组的区间最大值,查询区间v[l,r]>=l即存在

代码

#include<bits/stdc++.h>#define MAXN 200005using namespace std;int n,m,q,p[MAXN],par[MAXN][25],_p[MAXN],a[MAXN],v[MAXN],mx[MAXN<<2],pre[MAXN],l,r;void build(int o,int l,int r){    if(l==r){mx[o]=v[l];return;}    int mid=(l+r)/2;    build(o<<1,mid);build(o<<1|1,mid+1,r);    mx[o]=max(mx[o<<1],mx[o<<1|1]);}int qy(int o,int r,int L,int R){    if(L<=l&&r<=R)return mx[o];    int mid=(l+r)/2;    int ans=0;    if(L<=mid)ans=max(ans,qy(o<<1,mid,L,R));    if(R>mid)ans=max(ans,qy(o<<1|1,r,R));    return ans;}int main(){    cin>>n>>m>>q;    for(int i=0;i<n;i++)scanf("%d",&p[i]);    for(int i=1;i<=m;i++)scanf("%d",&a[i]);    for(int i=0;i<n;i++)_p[p[i]]=p[(i-1+n)%n];    for(int i=1;i<=m;i++){        int x=pre[_p[a[i]]];        par[i][0]=x;for(int j=1;j<=20;j++)par[i][j]=par[par[i][j-1]][j-1];        int d=n-1,u=i;        for(int j=20;j>=0;j--)if(d>>j&1)u=par[u][j];        v[i]=u;        pre[a[i]]=i;    }    build(1,1,m);    while(q--){        scanf("%d%d",&l,&r);        if(qy(1,r)>=l)printf("1");        else printf("0");    }}
. .. ...

广告 广告

评论区