唯一一道赛场上a掉的题……

首先考虑第一种贡献。先不考虑两个相邻的情况，这个我们可以查询的时候直接加。首先预处理出第i个数左边离他最近的比他大的数的位置l[i]，以及右边的r[i]（这个可以用单调栈做，我用的树状数组），如果l[i]和r[i]存在，那么以第i个数为为他们最大值的点对只有(l[i],r[i])。这样的话点对数量是O(n)的，我们每次查询区间[L,R]的第一类贡献，除了相邻的情况，就是查询有多少个点对在[L ,R]之间，这个是个二维矩形求值可以主席树来轻松的维护。

对于第二种贡献，考虑一开始求出的l[i],r[i]数组。那么如果有l[i]<x<i，那么(x,r[i])一定是满足第二类贡献且他们之间最大值为a[i]（因为显然有x<a[i],a[i]<a[r[i]]）。对于i<x<r[i]也是一样的情况。那么我们单考虑r[i]的情况，对于查询[L,R]，就是查询所有l<=r[i]<=r的min(r[i],R)-max(l[i],L)，就是说对于我们每一个枚举的最大值，找到l[i],r[i]，在二维空间中覆盖两条线段(r[i],l[i]+1)到（r[i],i-1)和(l[i],i+1)到(l[i],r[i]-1)，查询的时候也是做一个二维矩形求值，这个也可可以主席树来做，相当于打个tag，不过最好不要下传做个标记永久化

然后就没有了，时间复杂度O(nlogn)，我没开int64也过了，数据都是随机的吧2333没有卡真是万幸

然后代码非常丑……考场上写了一半觉得写得不简洁就改改改……结果还是一大坨……

1 //orz lzz,you are our red sun  2 program j01;  3 const maxn=200086;  4 type node=record l,r,tag,sum:longint; end;  5      opr=record l,r,ps:longint; end;  6      opr1=record l,r,id:longint;end;  7 var f:array[0..80*maxn]of node;  8     root1,root2:array[0..maxn]of longint;  9     op1:array[0..maxn]of opr1; 10     op:array[0..2*maxn]of opr; 11     p,c:array[0..maxn]of longint; 12     n,m,p1,p2,l,r,i,tt,inf,j,tot,ll,rr:longint; 13     ans:int64; 14     a:array[0..maxn]of longint; 15  16 function max(a,b:longint):longint;inline; 17 begin 18     if a>b then exit(a) else exit(b); 19 end; 20  21 function min(a,b:longint):longint;inline; 22 begin 23     if a0 do 39     begin 40         tmp:=max(tmp,c[i]);i:=i-(i and(-i)); 41     end; 42     exit(tmp); 43 end; 44  45 procedure insmn(i,dd:longint); 46 begin 47     while i<=n do 48     begin 49         c[i]:=min(c[i],dd);i:=i+(i and(-i)); 50     end; 51 end; 52  53 function askmn(i:longint):longint; 54 var tmp:longint; 55 begin 56     tmp:=inf; 57     while i>0 do 58     begin 59         tmp:=min(tmp,c[i]);i:=i-(i and(-i)); 60     end; 61     exit(tmp); 62 end; 63      64 procedure sort1(l,r:longint); 65 var i,j,x:longint;y:opr1; 66 begin 67     i:=l;j:=r;x:=op1[(i+j)div 2].l; 68     repeat 69         while op1[i].l
       
        j; 77     if i
        
         j; 94     if i
         
          0) then176         begin177             inc(tot);op[tot].ps:=op1[i].l;178             op[tot].l:=l;op[tot].r:=r;179         end;180     end;181     sort(1,tot);182     j:=1;183     for i:=1 to n do184     begin185         root2[i]:=root2[i-1];186         while(j<=n)and(op[j].ps=i)do187         begin188             ins(root2[i],1,n,op[j].l,op[j].r);189             inc(j);190         end;191     end;192     for i:=1 to m do193     begin194         readln(l,r);195         ans:=int64(p1)*(ask(root1[r],1,n,l,r)-ask(root1[l-1],1,n,l,r)+(r-l));196         ans:=ans+int64(p2)*(ask(root2[r],1,n,l,r)-ask(root2[l-1],1,n,l,r));197         writeln(ans);198     end;199     close(input);close(output);200 end.