#include #include #include using namespace std; typedef long long llong; /** Assumed constraints: L <= 500 000 N,M <= 100 000 wins <= 1 000 000 K <= 500 000 first/last row/column are empty no two leths on the same row touch **/ struct leth { int L,R; int row; int right; }; leth leths[500111]; int leftHit[500111]; int rightHit[500111]; int L=0; int n,m; int K; int ball[500111]; int win[500111]; int LEAFOFFSET=1; pair IT[1000111]; int startHit[500111]; int startOFFSET=10000000; int endOFFSET=20000000; pair MAX(pair a,pair b) { if (a>b) return a; else return b; } void Upd(int ind,pair val) { ind+=LEAFOFFSET; IT[ind]=val; ind/=2; while(ind>0) { IT[ind]=MAX(IT[2*ind],IT[2*ind+1]); ind/=2; } return; } pair recMax(int ver,int L,int R,int l,int r) { if (L>r || R=l && R<=r) return IT[ver]; else return MAX( recMax(2*ver,L,(L+R)/2,l,r), recMax(2*ver+1,(L+R)/2+1,R,l,r) ); } pair getMax(int L,int R) { return recMax(1,1,LEAFOFFSET+1,L,R); } int getVal(int ind) { return IT[ind+LEAFOFFSET].first; } bool SL(leth a,leth b) { return a.row0) return val; else { val=-val; if (val>startOFFSET) return startHit[val-startOFFSET]; else if (val>L) { val-=L; leftHit[val] = unchain(leftHit[val]); return leftHit[val]; } else { rightHit[val] = unchain(rightHit[val]); return rightHit[val]; } } } int counters[500111]; llong ans=0; int main() { freopen("machine.in","r",stdin); freopen("machine.out","w",stdout); int i,j; pair tp; int toLeft,toRight; scanf("%d %d",&n,&m); while(LEAFOFFSETstartOFFSET) { startHit[tp.first-startOFFSET] = i; } else if (tp.first>L) { leftHit[tp.first-L] = i; } else { rightHit[tp.first] = i; } tp=getMax(leths[i].L,leths[i].R); } if (getVal(leths[i].L-1)!=0) leftHit[i] = -getVal(leths[i].L-1); else Upd(leths[i].L-1,make_pair(i+L,leths[i].L-1)); if (getVal(leths[i].R+1)!=0) rightHit[i] = -getVal(leths[i].R+1); else Upd(leths[i].R+1,make_pair(i,leths[i].R+1)); } for (i=1;i<=m;i++) { if (getVal(i)!=0) { if (getVal(i)>startOFFSET) startHit[getVal(i)-startOFFSET] = i+endOFFSET; else if (getVal(i)>L) leftHit[getVal(i)-L] = i+endOFFSET; else rightHit[getVal(i)] = i+endOFFSET; } } for (i=1;i<=L;i++) { leftHit[i] = unchain(leftHit[i]); rightHit[i] = unchain(rightHit[i]); } for (i=1;i<=K;i++) { if (startHit[ ball[i] ]>endOFFSET) ans += (llong)win[ startHit[ ball[i] ]-endOFFSET ]; else counters[ startHit[ ball[i] ] ]++; } for (i=1;i<=L;i++) { if (leths[i].right==1) { toLeft=counters[i]/2; toRight=counters[i]-toLeft; } else { toRight=counters[i]/2; toLeft=counters[i]-toRight; } if (leftHit[i]>endOFFSET) ans += (llong)win[ leftHit[i]-endOFFSET ]*(llong)toLeft; else counters[ leftHit[i] ]+=toLeft; if (rightHit[i]>endOFFSET) ans += (llong)win[ rightHit[i]-endOFFSET ]*(llong)toRight; else counters[ rightHit[i] ]+=toRight; } printf("%lld\n",ans); return 0; }