2019牛客暑期多校训练营（第一场）

题目链接：https://ac.nowcoder.com/acm/contest/881#question

A Equivalent Prefixes

给定2个数组a、b，求这两个数组的最长前m串，使得 i n d e x [ r m q m i n ( a , l , r ) ] = i n d e x [ r m q m i n ( b , l , r ) ] index[rmqmin(a,l,r)]=index[rmqmin(b,l,r)] index[rmqmin(a,l,r)]=index[rmqmin(b,l,r)],对于任意的 1 < = l < = r < = m 1rights = next; next->parent = now; break; } last = S.top(); S.pop(); } if (S.empty() && last) { // 这里为了特判一种可能出现的情况，就是当前节点把栈全部弹空了，就要把原先的根节点作为当前节点的左子节点 next->lefts = last; last->parent = next; } S.push(next); } while (!S.empty()) now = S.top(), S.pop(); return now; } bool ok(int m) { Node *rt[2]; rt[0]=build(a,m); rt[1]=build(b,m); //printf("m:%d over\n",m); dfs(rt[0],0,1); dfs(rt[1],1,1); for(int i=1;i=mod) val-=mod; } ll ex_gcd(ll a,ll b,ll &x,ll &y)//不要求mod是素数 { if(b==0){ x=1; y=0; return a; } ll r=ex_gcd(b,a%b,x,y); ll t=x; x=y; y=t-a/b*y; return r; } ll mod_reverse(ll a) {// 求a关于mod的逆元x ll d,x,y; d=ex_gcd(a,mod,x,y); if(d==1) return (x%mod+mod)%mod; else return -1; } int main() { while(~scanf("%d",&n)){ for(int i=1;i