考虑每个值作为最大值的区间实际上可以用单调栈求出来，即找到左边第一个比它大的数l[i],右边第一个比它大的r[i]，那就是左端点在[l[i],i]右端点在[i,r[i]]的区间是以第i个数作为最大值。

　　这样的话可以看成二维平面上一个矩形区域,每个矩形区域有着一样的最大值，如果我们把最大值相同的矩形放在一起考虑，问题就变成了：最大值相同的a产生的矩形和b产生的矩形交的面积之和。

　　用一个扫描线去做，维护当前线上矩形交的长度now。具体是这样的：开2n个线段树，对于每一种最大值开线段树，分别用roota[i]和rootb[i]维护a和b的最大值为i的矩形在当前扫描线上覆盖情况。每次一个值为w的a产生的左上角[x1,y1],右下角[x2,y2]的矩形在x1处加入，now+=rootb[w]在[y1,y2]覆盖了多少，再在roota[w]的线段树修改。删除把+改成-就行了。这样最后ans+=now。

　　写着非常简单。

1 program j01; 2 const maxn=350086; 3 var a,b:array[0..maxn]of longint; 4     roota,rootb:array[0..maxn]of longint; 5     la,lb:array[0..maxn]of longint; 6     sta,stb:array[0..maxn]of longint; 7     f:array[0..40*maxn]of record l,r,tag,w:longint; end; 8     topa,topb,cnt,n,i:longint; 9     ll,rr,dd:longint;10     sum,now:int64;11     12 function min(a,b:longint):longint;inline;begin if ab then exit(a) else exit(b); end;14     15 function ask(i,l,r:longint):longint;16 var mid,res:longint;17 begin18     if i=0 then exit(0);19     if(ll<=l)and(r<=rr)then exit(f[i].w);20     mid:=(l+r)div 2;res:=f[i].tag*(min(rr,r)-max(ll,l)+1);21     if ll<=mid then res:=res+ask(f[i].l,l,mid);22     if mid+1<=rr then res:=res+ask(f[i].r,mid+1,r);23     exit(res);24 end;25 26 procedure change(var i:longint;l,r:longint);27 var mid:longint;28 begin29     if i=0 then30     begin31         inc(cnt);i:=cnt;32     end;33     if(ll<=l)and(r<=rr)then34     begin35         inc(f[i].tag,dd);inc(f[i].w,dd*(r-l+1));exit;36     end;37     mid:=(l+r)div 2;38     if ll<=mid then change(f[i].l,l,mid);39     if mid+1<=rr then change(f[i].r,mid+1,r);40     f[i].w:=f[i].tag*(r-l+1)+f[f[i].l].w+f[f[i].r].w;41 end;42     43 begin44     readln(n);45     for i:=1 to n do read(a[i]);46     for i:=1 to n do read(b[i]);47     fillchar(la,sizeof(la),0);fillchar(lb,sizeof(lb),0);48     fillchar(roota,sizeof(roota),0);fillchar(rootb,sizeof(rootb),0);49     a[0]:=maxlongint;b[0]:=maxlongint;topa:=0;topb:=0;sta[0]:=0;stb[0]:=0;50     sum:=0;now:=0;51     for i:=1 to n do52     begin53         while a[sta[topa]]<=a[i] do54         begin55             ll:=la[sta[topa]];rr:=sta[topa];dd:=-1;56             now:=now-ask(rootb[a[sta[topa]]],1,n);57             change(roota[a[sta[topa]]],1,n);58             dec(topa);59         end;60         while b[stb[topb]]<=b[i] do61         begin62             ll:=lb[stb[topb]];rr:=stb[topb];dd:=-1;63             now:=now-ask(roota[b[stb[topb]]],1,n);64             change(rootb[b[stb[topb]]],1,n);65             dec(topb);66         end;67         la[i]:=sta[topa]+1;ll:=la[i];rr:=i;dd:=1;68         now:=now+ask(rootb[a[i]],1,n);change(roota[a[i]],1,n);69         inc(topa);sta[topa]:=i;70         lb[i]:=stb[topb]+1;ll:=lb[i];rr:=i;dd:=1;71         now:=now+ask(roota[b[i]],1,n);change(rootb[b[i]],1,n);72         inc(topb);stb[topb]:=i;73         sum:=sum+now;//writeln(now,' ',sum);74     end;75     writeln(sum);76 end.77         78