首页 > 代码库 > BNUOJ52317 As Easy As Possible（树上倍增）
BNUOJ52317 As Easy As Possible（树上倍增）
题意：
给你一个1e5长度的easy串（只含easy四个字母）
1e5个询问，每个询问一个区间l，r
问这个区间内easy的个数
思路：
当时还想预处理出最优的easy区间，然后lower_bound
wa了几发发现这样并不是最优的，然后就放弃了~
出题解后补了一个倍增
每个字母记录前面那个字母出现的位置，然后倍增
每次查询先找出距离r最近的那个‘y‘
然后直到找到l，统计出找到的字母的数量/4就是答案
/* ***********************************************Author :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <stack>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){ char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-‘0‘; c=getchar(); }}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int N=1e5+10;char s[N];int py[N],fa[N][20],n,m,last[4],dep,l,r;int main(){ scanf("%s",s+1); rd(m); n=strlen(s+1); rep(i,1,n) { if(s[i]==‘e‘) { fa[i][0]=last[3]; last[0]=i; } else if(s[i]==‘a‘) { fa[i][0]=last[0]; last[1]=i; } else if(s[i]==‘s‘) { fa[i][0]=last[1]; last[2]=i; } else { fa[i][0]=last[2]; last[3]=i; } py[i]=last[3]; } for(dep=1;1<<dep<=n;dep++); rep(i,1,dep-1) rep(j,1,n) fa[j][i]=fa[fa[j][i-1]][i-1]; while(m--) { rd(l),rd(r); r=py[r]; int ans=1; dep(i,dep-1,0) if(fa[r][i]>=l) { r=fa[r][i]; ans+=1<<i; } printf("%d\n",ans/4); } return 0;}
BNUOJ52317 As Easy As Possible（树上倍增）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。