给一个1到N的排列{Ai}，询问是否存在1<=p1=3），使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。
给一个1到N的排列{Ai}，询问是否存在1<=p1=3），使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。
输入的第一行包含一个整数T，表示组数。下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。
对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。
对于100%的数据，N<=10000，T<=7
【思路】
转化+hash+线段树。
首先需要明确的一点：A是一个1..n的排列。
其次将出现情况统计为01字符串分别表示该数字目前为止是否出现，因此对于一个数字当前没有出现以后一定会出现。例如对于{5,2,1,4,3,6}且已经扫到了4，则有01状态为110010，可以看出如果有一对数字以4为中心分别为01则一定有等差数列。又因为非0即1的性质，所以问题可以转化为两个字串是否相等的问题，对应到例子中即s(2,3)是否等于s(6,5)，如果相等则必无等差数列反之则必有一个或多个等差数列。
线段树维护hash，[区间查询单点修改]，O(logn)的查询时间，O(logn)的维护时间，总时间为O(nlogn)。
注：求Hash对应一个区间查询。
【代码】
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define FOR(a,b,c) for(int a=(b);a<=(c);a++) 5 using namespace std; 6 7 typedef long long LL; 8 const int maxn = 10000+10; 9 const int MOD = 100000007; 10 11 int read() { 12 char c=getchar(); 13 while(!isdigit(c)) c=getchar(); 14 int x=0; 15 while(isdigit(c)) { 16 x=x*10+c-'0'; 17 c=getchar(); 18 } 19 return x; 20 } 21 22 int n; 23 int a[maxn],xp[maxn]; 24 25 LL sumv[4*maxn][2]; 26 int v; 27 void update(int u,int L,int R) { 28 int lc=u<<1,rc=lc+1; 29 if(L==R) { 30 sumv[u][0]=sumv[u][1]=1; 31 } 32 else { 33 int M=L+(R-L)/2; 34 if(v<=M) update(lc,L,M); 35 else update(rc,M+1,R); 36 sumv[u][0]=(sumv[rc][0]+xp[R-M]*sumv[lc][0]%MOD)%MOD; 37 sumv[u][1]=(sumv[lc][1]+xp[M-L+1]*sumv[rc][1]%MOD)%MOD; 38 } 39 } 40 LL query(int node,int l,int r,int a,int b,int x){ 41 int lc=node<<1,rc=lc+1; 42 if(l==a&&r==b)return sumv[node][x]; 43 int m=(l+r)>>1; 44 LL left=0,right=0; 45 if(m<b)right=query(rc,m+1,r,max(m+1,a),b,x); 46 if(a<=m)left=query(lc,l,m,a,min(m,b),x); 47 return (x?left+right*xp[max(0,m-a+1)]%MOD:right+left*xp[max(0,b-m)]%MOD)%MOD; 48 } 49 int main() 50 { 51 freopen("cin.in","r",stdin); 52 freopen("coutme.out","w",stdout); 53 int T; 54 T=read(); 55 while(T--) { 56 memset(sumv,0,sizeof(sumv)); 57 n=read(); 58 xp[0]=1; FOR(i,1,n+5) xp[i]=(xp[i-1]<<1)%MOD; 59 FOR(i,1,n) a[i]=read(); 60 bool f=0; 61 FOR(i,1,n) { 62 int x=a[i]; 63 LL lf,rf; 64 int len=min(x-1,n-x); 65 if(len&&query(1,1,n,x-len,x-1,0)!=query(1,1,n,x+1,x+len,1)){ 66 f=1; 67 break; 68 } 69 v=x; 70 update(1,1,n); 71 } 72 if(f) printf("Y\n"); 73 else printf("N\n"); 74 } 75 return 0; 76 }
前言前面的理解OAuth2.0认证与客户端授权码模式详解，我们大致了解了Oauth2.0授权模式四种的授权码模式，清楚了授权码模式的大致流程。这里简单的模拟一下基于授权码模式的客户端和服务端代码实现（这里服务端包含的验证服务端和资源服务端，都是在同一个应用中）。回顾大致授权流程图中步骤1，请求授权，例如我们要登录csdn，这里我们想用qq账号登录，这时候就需要腾讯开放平台进行..._oauthclientrequest
一、背景 最近做网关重构，技术选型为spring cloud gateway，采用consul作为配置中心和注册中心，秉承不重启原则，网关内部实现动态路由机制，采用定时任务定时更新网关路由信息。二、服务信息 微服务网关：spring-cloud-gateway 微服务：order-service、user-service三、问题描述 因为网关服务集成了knife4j，因此可以通过访问http://网关ip:port/doc.html，即可访问所有在同一个...
逗留汉城 (9/12) 开始向往汉城始于2002年韩日世界杯,因为足球和绿茵场足以吸引五大洲的目光.那一年的韩国也因此格外令人心弛神往. 于是知道了韩国的泡菜, 烧烤, 服饰, 美女和World Cup. 从上海到汉城也就短短一个多小时, 一海之隔的异国他乡是如此的不遥远.当飞机降落在仁川机场时,我才有机会踏上这片充满现代气息的土地.不过这里早就没有了两年前世界杯的影子了, 但这
成功现象：编写less文件保存后，会自动生成wxss。如果你生成的是css，那么你肯定写配置文件写成了：“outExit”: “.wxss”要领：1、在vscode下载Easy LESS，不要下载小写的。2、直接找到下载的原文件拖拽到目录下：C:\用户\用户名\AppData\Local\微信开发者工具\User Data\44eeba12734bda28b5a1170964ece91d\Default\Editor\User\extensions下载到vscode一般路径：C:\User_小程序修改less全局变量文件后每个文件都需要保存才生效
一些SCI科技论文公式使用的字体是computer modern，latex排版默认公式格式是computer modern，但是在MS office中mathtype没有各种格式，替代方式是：(1)mathtype->样式->定义->字体修改为euclid或者(2)mathype(Office选项卡)->格式化公式->mathtype preference file->Tex Look()应用到全部公式..._mathtype latex公式字体是什么
参考：https://flutter.dev/docs/development/packages-and-plugins/androidx-compatibility1 第一步在 android/gradle/wrapper/gradle-wrapper.properties中修改Gradle版本为4.10.2distributionUrl=https\://services.gradle..._flutter 对安卓版本的支持
面试鸭 面试刷题 网站系统源码_面试鸭源码
2008年10月16日，原金山软件CEO雷军先生正式宣布出任UCWEB（优视动景）公司董事长。与会现场，优视动景CEO俞永福介绍了公司创业以来的业务进展和目标。产品总裁何小鹏和技术总裁梁捷表示，在手机上学习Google的成功，并希望在5年内将公司打造成中国最伟大的移动互联网技术服务公司。 UCWEB作为手机到互联网的“桥梁”，互联网的文字、图片、视频等内容将更高效的传输给用户，用户...
SPIR-V着色器被嵌入在模块之中。每个模块可以包含一个或多个着色器。每个着色器具有一个入口点，该入口点具有一个名字和一个着色器类型，着色器类型用于定义当前着色器跑在哪个着色阶段。入口点则是当前着色器开始执行的位置。一个SPIR-V模块伴随着创建信息被传递给Vulkan，然后Vulkan返回表示该模块的一个对象。该模块对象随后可以用于构造一条流水线。_spir-v
之前面试的时候，面试有一道题，要记算10的平方根，并且精确到0.01，我也是想了一会才想到了一种简单粗暴的方法，也算是完成了； squareRoot=(num)=>{ let s=1,d=0.1,x=0.01; while(s*s<num){ s++; } let sd=s-1+d; while(sd*sd<num){ sd+=0.1 } let sdx=s._js math.squre
Golang 快速入门Go Modulesgo mod 命令go mod 环境变量GO111MODULEGOPROXYGOSUMDBGOPRIVATE初始化项目修改项目版本依赖关系Golang 生态拓展Web 框架微服务框架容器编排服务发现存储引擎静态建站中间件爬虫框架学习视频：8 小时转职 Golang 工程师，这门课很适合有一定开发经验的小伙伴，强推！Go ModulesGo modules 是 Go 语言的依赖解决⽅案。发布于 Go1.11，成⻓于 Go1.12，丰富于 Go1.13，正_gin zinx
一:创建项目1: 首先AS创建一个项目 2: 登录码云创建项目 需要注意几点 名称需要和AS创建的项目名称一样 介绍随便写 下面三个选择按钮,全不用选二:生成一个.ssh文件安装上git才能生成 在桌面右键 Git Bash Here 输入 ssh-keygen -t rsa -C "码云账号" 回车回车回车回