#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcount(x) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL clock_t start=clock(); #endif int testcase=1; //cin>>testcase; for(int i=0;i>h>>w; ll ans=0; vector>no(h); vector>a(h,vector(w,false)); int n; cin>>n; rep(i,n){ int x,y; cin>>x>>y; x--,y--; a[x][y]=1; } rep(i,h){ rep(j,w)if(a[i][j])no[i].push_back(j); no[i].push_back(w); } rep(j,w){ vectordat(w,{1,0}); lazy_segtreeseg(dat); vectorb(h); rep(i,h){ b[i]=*lower_bound(all(no[i]),j)-j; } seg.apply(0,w,-1); rep(i,h){ ans+=i*b[i]-seg.prod(0,b[i]).sum; seg.apply(b[i],w,i); } continue; stack>st; st.push({-1,-1}); vector>lftrht(h); rep(i,h){ while(st.top().second>=b[i]){ assert(!st.empty()); st.pop(); } lftrht[i].first=st.top().first+1; ans+=(i-st.top().first)*b[i]; st.push({i,b[i]}); } while(!st.empty())st.pop(); st.push({h,-1}); for(int i=h-1;i>=0;i--){ while(st.top().second>=b[i]){ assert(!st.empty()); st.pop(); } lftrht[i].second=st.top().first-1; ans+=(st.top().first-i)*b[i]; st.push({i,b[i]}); } } cout<