O(n log U) polynomial identity testing, C++ 36ms 100%
Use RMQ to find the minimum and maximum value in [l_i,r_i] (denote by mi and ma), then compute the common difference d. Use polynomial identity testing to test 
Use RMQ to find the minimum and maximum value in [l_i,r_i] (denote by mi and ma), then compute the common difference d. Use polynomial identity testing to test whether \\sum_{l_i\u2264j\u2264r_i}x^{a_j}=\\sum_{j=0}^{r_i-l_i}x^{mi+d\\cdot j}.\n\n```\ntypedef unsigned int uint;\ntypedef long long ll;\nconst int N=505,W=32,D=4,inf=1<<30,P=1000000007,U=100000;  //D=(int)log2(N/W)+1\nint a[N+W];\nnamespace RMinQ{\n\tint f[D][N/W+1],M[N/W],stack[W];\n\tstruct node{\n\t\tuint state[W]; int *a;\n\t\tint Q(int x,int y){return a[x+__builtin_ctz(state[y]>>x)];}\n\t\tvoid init(int *_a){\n\t\t\tint *s1=stack; *s1=0; state[0]=1; a=_a;\n\t\t\tfor (int i=1;i<W;++i){\n\t\t\t\tstate[i]=state[i-1];\n\t\t\t\twhile (s1>=stack&&a[i]<=a[*s1])state[i]-=1<<*(s1--);\n\t\t\t\t*(++s1)=i;state[i]+=1<<i;\n\t\t\t}\n\t\t}\n\t}c[N/W+1];\n\tvoid build(int n){\n\t\tint nn=n/W,d=(int)log2(max(nn,1)); M[0]=-1;\n\t\tfor (int i=1;i<nn;++i)M[i]=!(i&(i-1))?M[i-1]+1:M[i-1];\n\t\tfor (int i=0;i<=nn;++i){\n\t\t\tint &f0=f[0][i],*_a=a+i*W; c[i].init(_a); f0=inf;\n\t\t\tfor (int j=0;j<W;++j)f0=min(f0,_a[j]);\n\t\t}\n\t\tfor (int j=1;j<=d;++j){\n\t\t\tint *f0=f[j-1],*f1=f[j],j1=1<<(j-1);\n\t\t\tfor (int i=1;i<=nn-(1<<j);++i)f1[i]=min(f0[i],f0[i+j1]);\n\t\t}\n\t}\n\tinline int Q_ST(int x,int y){\n\t\tif (x>y)return inf;\n\t\tint z=M[y-x+1],*f0=f[z]; return min(f0[x],f0[y-(1<<z)+1]);\n\t}\n\tinline int Q(int x,int y){\n\t\tint xx=x/W,yy=y/W; x%=W; y%=W;\n\t\treturn min(Q_ST(xx+1,yy-1),xx<yy?min(c[xx].Q(x,W-1),c[yy].Q(0,y)):c[xx].Q(x,y));\n\t}\n} //using namespace RMinQ;\nnamespace RMaxQ{\n\tint f[D][N/W+1],M[N/W],stack[W];\n\tstruct node{\n\t\tuint state[W]; int *a;\n\t\tint Q(int x,int y){return a[x+__builtin_ctz(state[y]>>x)];}\n\t\tvoid init(int *_a){\n\t\t\tint *s1=stack; *s1=0; state[0]=1; a=_a;\n\t\t\tfor (int i=1;i<W;++i){\n\t\t\t\tstate[i]=state[i-1];\n\t\t\t\twhile (s1>=stack&&a[i]>=a[*s1])state[i]-=1<<*(s1--);\n\t\t\t\t*(++s1)=i;state[i]+=1<<i;\n\t\t\t}\n\t\t}\n\t}c[N/W+1];\n\tvoid build(int n){\n\t\tint nn=n/W,d=(int)log2(max(nn,1)); M[0]=-1;\n\t\tfor (int i=1;i<nn;++i)M[i]=!(i&(i-1))?M[i-1]+1:M[i-1];\n\t\tfor (int i=0;i<=nn;++i){\n\t\t\tint &f0=f[0][i],*_a=a+i*W; c[i].init(_a); f0=-inf;\n\t\t\tfor (int j=0;j<W;++j)f0=max(f0,_a[j]);\n\t\t}\n\t\tfor (int j=1;j<=d;++j){\n\t\t\tint *f0=f[j-1],*f1=f[j],j1=1<<(j-1);\n\t\t\tfor (int i=1;i<=nn-(1<<j);++i)f1[i]=max(f0[i],f0[i+j1]);\n\t\t}\n\t}\n\tinline int Q_ST(int x,int y){\n\t\tif (x>y)return -inf;\n\t\tint z=M[y-x+1],*f0=f[z]; return max(f0[x],f0[y-(1<<z)+1]);\n\t}\n\tinline int Q(int x,int y){\n\t\tint xx=x/W,yy=y/W; x%=W; y%=W;\n\t\treturn max(Q_ST(xx+1,yy-1),xx<yy?max(c[xx].Q(x,W-1),c[yy].Q(0,y)):c[xx].Q(x,y));\n\t}\n} //using namespace RMaxQ;\n\nint g[N],_s[N],*s=_s+1,R=rand()%P;\ninline int exp(int x,int y){\n\tint ans=1;\n\twhile (y){\n\t\tif (y&1)ans=(ll)ans*x%P;\n\t\tx=(ll)x*x%P; y>>=1;\n\t}\n\treturn ans;\n}\nclass Solution {\npublic:\n\tvector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n\t\tint n=nums.size(),m=l.size(); vector<bool> ans(m);\n\t\tfor (int i=0;i<n;++i)a[i]=nums[i]+U;\n\t\tRMinQ::build(n); RMaxQ::build(n); s[-1]=0;\n\t\tfor (int i=0;i<n;++i)g[i]=exp(R,a[i]),s[i]=(s[i-1]+g[i])%P;\n\t\tfor (int i=0;i<m;++i){\n\t\t\tint mi=RMinQ::Q(l[i],r[i]),ma=RMaxQ::Q(l[i],r[i]),d=l[i]<r[i]?(ma-mi)/(r[i]-l[i]):0;\n\t\t\tif (ma-mi!=d*(r[i]-l[i]))continue;\n\t\t\tif (d==0){ans[i]=1; continue;}\n\t\t\td=exp(R,d);\n\t\t\tint s0=(ll)exp(R,mi)*(1-exp(d,r[i]-l[i]+1))%P*exp(1-d,P-2)%P;\n\t\t\tans[i]=(s[r[i]]-s[l[i]-1]-s0)%P==0;\n\t\t}\n\t\treturn ans;\n\t}\n};\n```
[]