个人网站建设法律规定,字体在线设计网站,企业宣传视频制作公司,深圳网站建设-猴王网络正题 题目大意
一个序列aaa 对于[L..R][L..R][L..R]若ak∈[L..R]∣ai∈[L..R]a_k \in [L..R]|a_i\in[L..R]ak∈[L..R]∣ai∈[L..R]则这个一个特殊区间。 求最长特殊区间。 解题思路
先RMQRMQRMQ求区间GCDGCDGCD#xff0c;然后二分答案。
之后aka_kak肯定是这个区间最…正题 题目大意
一个序列aaa 对于[L..R][L..R][L..R]若ak∈[L..R]∣ai∈[L..R]a_k \in [L..R]|a_i\in[L..R]ak∈[L..R]∣ai∈[L..R]则这个一个特殊区间。 求最长特殊区间。 解题思路
先RMQRMQRMQ求区间GCDGCDGCD然后二分答案。
之后aka_kak肯定是这个区间最小的单调队列维护一下(或者RMQRMQRMQ维护)然后判断区间GCDGCDGCD是否等于aka_kak codecodecode
#includecstdio
#includequeue
#includecmath
#includecctype
#includealgorithm
#define N 500010
using namespace std;
dequeint q;
int n,a[N],ans[N],tot,f[N][23],lg[N];
int read() {int x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
void print(int x){if (x9) print(x/10); putchar(x%1048); return;
}
void Keep(int x){while(!q.empty()q.front()x)q.pop_front();
}
void Push(int x){while(!q.empty()a[q.back()]a[x])q.pop_back();q.push_back(x);
}
int Gcd(int l,int r){int zlg[r-l1];return __gcd(f[l][z],f[r1-(1z)][z]);
}
int check(int x){int ans0;while(!q.empty())q.pop_front();for(int i1;ix;i)Push(i);for(int ix1;in;i){Keep(i-x);Push(i);int wa[q.front()];if(Gcd(i-x,i)w)ans;}return ans;
}
void write(int x){while(!q.empty())q.pop_front();for(int i1;ix;i)Push(i);for(int ix1;in;i){Keep(i-x);Push(i);int wa[q.front()];if(Gcd(i-x,i)w)print(i-x),putchar( );}
}
int main()
{nread();lg[0]-1;for(int i1;in;i)a[i]read(),f[i][0]a[i],lg[i]lg[i/2]1;for(int j1;(1j)n;j)for(int i1;i(1j)-1n;i)f[i][j]__gcd(f[i][j-1],f[i(1j-1)][j-1]);int l0,rn;while(lr){int mid(lr)/2;if(check(mid)) lmid1;else rmid-1;}print(check(r));putchar( );print(r);putchar(\n);write(r);
}
