网站优化企业排名,东莞排名seo网站关键词优化,广东省网站集约化建设方案,网页已改版BZOJ4516: [Sdoi2016]生成魔咒 Description 魔咒串由许多魔咒字符组成#xff0c;魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。例如 S[1,2,1] 时#xff0c;它的生成魔咒有 [1]、[2]…BZOJ4516: [Sdoi2016]生成魔咒 Description 魔咒串由许多魔咒字符组成魔咒字符可以用数字表示。 例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。 一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。 例如 S[1,2,1] 时它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。 S[1,1,1] 时它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。 最初 S 为空串。共进行 n 次操作每次操作是在 S 的结尾加入一个魔咒字符。 每次操作后都需要求出当前的魔咒串 S 共有多少种生成魔咒。 Input 第一行一个整数 n。 第二行 n 个数第 i 个数表示第 i 次操作加入的魔咒字符。 1≤n≤100000。 用来表示魔咒字符的数字 x 满足 1≤x≤10^9 Output 输出 n 行每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量 Sample Input 7 1 2 3 3 3 1 2 Sample Output 1 3 6 9 12 17 22 题解Here! 据说这题可以被$SAM$秒杀然而本蒟蒻只会$SA$。。。 题目要求出每一个前缀本质不同的后缀的个数。 那么我们可以把原序列倒过来然后实际上就是对于每一个后缀求与其它后缀不重复的前缀个数也即是后缀长度减去$height$。 求出某一个后缀对答案的贡献之后他不应该停留在元序列中对后续答案的求解产生影响所以应该把它删除。 这个可以用平衡树来完成。 但是考虑到每一个位置只与前后有关我们可以用链表来代替。 还有要离散化。。。 附代码 #includeiostream
#includealgorithm
#includecstdio
#includecstring
#define MAXN 100010
using namespace std;
int n;
int val[MAXN],num[MAXN],SBT_front[MAXN],SBT_next[MAXN];
long long ans[MAXN];
int top,sa[MAXN],rk[MAXN],height[MAXN],tax[MAXN],tp[MAXN];
inline int read(){int date0,w1;char c0;while(c0||c9){if(c-)w-1;cgetchar();}while(c0c9){datedate*10c-0;cgetchar();}return date*w;
}
void radixsort(){for(int i0;itop;i)tax[i]0;for(int i1;in;i)tax[rk[i]];for(int i1;itop;i)tax[i]tax[i-1];for(int in;i1;i--)sa[tax[rk[tp[i]]]--]tp[i];
}
void suffixsort(int x){topx;for(int i1;in;i){rk[i]val[i];tp[i]i;}radixsort();for(int w1,p0;pn;topp,w1){p0;for(int i1;iw;i)tp[p]n-wi;for(int i1;in;i)if(sa[i]w)tp[p]sa[i]-w;radixsort();swap(tp,rk);rk[sa[1]]p1;for(int i2;in;i)rk[sa[i]](tp[sa[i-1]]tp[sa[i]]tp[sa[i-1]w]tp[sa[i]w])?p:p;}
}
void getheight(){for(int i1,j,k0;in;i){if(k)k--;jsa[rk[i]-1];while(val[ik]val[jk])k;height[rk[i]]k;}
}
void work(){for(int i1;in;i){SBT_front[i]i-1;SBT_next[i]i1;}for(int i1;in;i){int nown-i1-max(height[rk[i]],height[SBT_next[rk[i]]]);ans[i](long long)now;height[SBT_next[rk[i]]]min(height[rk[i]],height[SBT_next[rk[i]]]);height[rk[i]]0;if(rk[i]!1)SBT_next[SBT_front[rk[i]]]SBT_next[rk[i]];SBT_front[SBT_next[rk[i]]]SBT_front[rk[i]];}for(int in;i1;i--)ans[i]ans[i1];for(int in;i1;i--)printf(%lld\n,ans[i]);
}
void init(){nread();for(int i1;in;i)num[i]val[n-i1]read();sort(num1,numn1);int kunique(num1,numn1)-num-1;for(int i1;in;i)val[i]lower_bound(num1,numk1,val[i])-num;suffixsort(k1);getheight();
}
int main(){init();work();return 0;
}转载于:https://www.cnblogs.com/Yangrui-Blog/p/9447643.html
