考慮枚舉左端點i，則隨著右端點的右移，一共只有$O(\log n)$種不同的gcd取值。所以首先通過ST表+二分查找預處理出$O(n\log n)$個四元組(x,i,l,r)，表示左端點為i，右端點取值范圍在[l,r]內，且這一段的gcd都為x。

將四元組按照x為第一關鍵字，i為第二關鍵字排序，對于相同的x一起處理。

當x相同時，顯然所有的i互不相同。設f[i]為恰好以位置i為結尾的最優解，則對于一個四元組(x,i,l,r)，能更新它的最優解為區間[1,i-1]的最優值+1，然后用它更新區間[l,r]的f[]。用支持打標記的線段樹維護即可。時間復雜度$O(n\log^2n)$。

比賽的時候TLE不止，賽后什么都沒改交了一發居然直接就過了。

?

#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; const int N=100010,K=17,P=998244353,M=262145; int T,n,m,i,j,x,y,l,r,mid,Log[N],val,f[K][N]; struct PI{int x,i,l,r;PI(){}PI(int _x,int _i,int _l,int _r){x=_x,i=_i,l=_l,r=_r;} }a[3000000]; inline bool cmp(PI a,PI b){return a.x==b.x?a.i<b.i:a.x<b.x;} struct Num{int x,y;Num(){x=y=0;}Num(int _x,int _y){x=_x,y=_y;}inline Num operator+(Num b){if(x<b.x)return b;if(x>b.x)return Num(x,y);return Num(x,(y+b.y)%P);}inline Num operator+(int _x){return Num(x+_x,y);}inline Num operator-(int b){return Num(x,(long long)y*b%P);}inline void operator+=(Num b){*this=*this+b;} }tmp,v[M],tag[M],ans; int pos[M]; inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10LL)+=c-'0';} inline int askgcd(int y){int k=Log[y-i+1];return __gcd(f[k][i],f[k][y-(1<<k)+1]);} inline void clean(int x){if(pos[x]<T)pos[x]=T,v[x]=tag[x]=Num(); } inline void tag1(int x,Num y){clean(x);v[x]+=y;tag[x]+=y; } inline void pb(int x){if(tag[x].x){tag1(x<<1,tag[x]);tag1(x<<1|1,tag[x]);tag[x]=Num();} } inline void up(int x){clean(x<<1),clean(x<<1|1);v[x]=v[x<<1]+v[x<<1|1]; } void change(int x,int a,int b,int c,int d){clean(x);if(c<=a&&b<=d){tag1(x,tmp);return;}pb(x);int mid=(a+b)>>1;if(c<=mid)change(x<<1,a,mid,c,d);if(d>mid)change(x<<1|1,mid+1,b,c,d);up(x); } void ask(int x,int a,int b,int c,int d){clean(x);if(c<=a&&b<=d){tmp+=v[x];return;}pb(x);int mid=(a+b)>>1;if(c<=mid)ask(x<<1,a,mid,c,d);if(d>mid)ask(x<<1|1,mid+1,b,c,d);up(x); } int main(){for(i=2;i<=100000;i++)Log[i]=Log[i>>1]+1;while(~scanf("%d",&n)){m=0;ans=Num();for(i=1;i<=n;i++)read(f[0][i]);int flag=0;for(i=2;i<=n;i++)if(f[0][i]!=f[0][i-1]){flag=1;break;}if(!flag){printf("%d 1\n",n);continue;}for(j=1;j<K;j++)for(i=1;i+(1<<j-1)<=n;i++)f[j][i]=__gcd(f[j-1][i],f[j-1][i+(1<<j-1)]);for(i=1;i<=n;i++)for(x=i;x<=n;x=y+1){val=askgcd(y=x),l=x+1,r=n;while(l<=r)if(askgcd(mid=(l+r)>>1)==val)l=(y=mid)+1;else r=mid-1;a[++m]=PI(val,i,x,y);}sort(a+1,a+m+1,cmp);for(i=1;i<=m;i++){if(i==1||a[i].x!=a[i-1].x)T++;tmp=Num();if(a[i].i>1)ask(1,1,n,1,a[i].i-1);if(!tmp.x)tmp=Num(1,1);else tmp.x++;ans+=tmp-(a[i].r-a[i].l+1);change(1,1,n,a[i].l,a[i].r);}printf("%d %d\n",ans.x,ans.y);}return 0; }

　　

總結

以上是生活随笔為你收集整理的HDU5320 : Fan Li的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。