记录编号	261744	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]棋盘上的士兵	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.453 s
提交时间	2016-05-18 15:08:23	内存使用	17.07 MiB

#define maxn 200010ul
   
#include <stdio.h>
#include <assert.h>
#include <algorithm>
   
typedef long long ll;
   
inline void read(int &x){
    x=0;int c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+(c^48);
    return;
}
   
struct point{int x,y;};
struct node{int cnt,len;};
struct polygon{point l,r;};
struct segment{int l,r,h,type;};
struct Trangle{int x,r;};
struct pdd{
    int x,y,r;
    void scan(){read(x),read(y),read(r);}
};
   
namespace compute{
      
    #define cson l,r,rt
    #define lson l,mid,t
    #define rson mid+1,r,t|1
   
    node tree[maxn<<2];
    segment pt[maxn];
      
    int m,cnt,posl,posr,upv,pos[maxn];
   
    bool cmp_segment(const segment &a,const segment &b){
        return a.h<b.h;
    }
   
    void upd(int l,int r,int rt){
        if(tree[rt].cnt) tree[rt].len=pos[r+1]-pos[l]; else
        if(l==r) tree[rt].len=0; else
        tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
        return;
    }
   
    void update(int l,int r,int rt){
        if(posl<=l&&posr>=r){tree[rt].cnt+=upv,upd(cson);return;}
        int mid=(l+r)>>1,t=rt<<1;
        if(posl<=mid) update(lson);
        if(posr>mid) update(rson);
        upd(cson);return;
    }
   
    void build(int l,int r,int rt){
        tree[rt]=(node){0,0};
        if(l==r) return;
        int mid=(l+r)>>1,t=rt<<1;
        build(lson),build(rson);
        return;
    }
      
    int binary_search(int v){
        int l=1,r=m,mid;
        while(l<=r){
            mid=(l+r)>>1;
            if(pos[mid]==v) return mid;
            else if(pos[mid]>v) r=mid-1;
            else l=mid+1; 
        }
        return 0;
    }
   
    int get_ray(const polygon &x,int p){
        if(p==0) return x.l.x;
        else return x.r.x;
    }
   
    segment convert_to_segment(const polygon &x,int p){
        if(p==0) return (segment){x.l.x,x.r.x,x.l.y,-1};
        else return (segment){x.l.x,x.r.x,x.r.y,1};
    }
   
    void print(const polygon &x){
        printf("ltop : %d %d \n",x.l.x,x.l.y);
        printf("rtop : %d %d \n",x.r.x,x.r.y);
        puts("");return;
    }
      
    void arrange(polygon *st,polygon *ed){
        for(;st!=ed;++st){
            if((*st).l.x>(*st).r.x) std::swap((*st).l.x,(*st).r.x);
            if((*st).l.y<(*st).r.y) std::swap((*st).l.y,(*st).r.y);
            (*st).r.y--,(*st).r.x++;
        }
        return;
    }
   
    ll rectangle_cross_area(int n,polygon *py){
        ll ans=0;m=cnt=0;
        for(int i=1;i<=n;i++){
            pt[++cnt]=convert_to_segment(py[i],0),pos[cnt]=get_ray(py[i],0);
            pt[++cnt]=convert_to_segment(py[i],1),pos[cnt]=get_ray(py[i],1);
        }
        std::sort(pt+1,pt+cnt+1,cmp_segment);
        std::sort(pos+1,pos+cnt+1);
        pos[0]=-0x7fffffff;
        for(int i=1;i<=cnt;i++) if(pos[i]!=pos[i-1]) pos[++m]=pos[i];
        build(1,m,1);
        for(int i=1;i<=cnt;i++){
            posl=binary_search(pt[i].l),posr=binary_search(pt[i].r)-1;
            if(posl<=posr) upv=pt[i].type,update(1,m,1);
            ans+=1ll*tree[1].len*(pt[i+1].h-pt[i].h);
        }
        return ans;
    }
}
   
namespace compute2{
   
    using std::abs;
    Trangle tmp[maxn];
      
    void upd(ll &x,ll y){
        if(y>x) x=y;return;
    }
      
    bool cmp_Trangle(const Trangle &x,const Trangle &y){
        return x.x-x.r<y.x-y.r;
    }
      
    int dist(const pdd &p,int x,int y){
        return abs(p.x-x)+abs(p.y-y);
    }
      
    bool inRange(const pdd &p,int x,int y){
        return dist(p,x,y)<=p.r;
    }
      
    ll area(ll x){
        return (1ll+x)*x>>1ll;
    }
      
    ll outA(int N,int M,const pdd &x){
        return area(x.r-dist(x,  0,M+1)+1);
    }
      
    ll outC(int N,int M,const pdd &x){
        return area(x.r-dist(x,N+1,M+1)+1);
    }   
      
    ll outF(int N,int M,const pdd &x){
        return area(x.r-dist(x,  0,  0)+1);
    }
      
    ll outH(int N,int M,const pdd &x){
        return area(x.r-dist(x,N+1,  0)+1);
    }
      
    ll exceed_ACFH(int N,int M,int n,pdd *data){
        ll maxA=0,maxC=0,maxF=0,maxH=0;
        for(int i=1;i<=n;i++){
            if(inRange(data[i],0  ,M+1)) upd(maxA,outA(N,M,data[i]));
            if(inRange(data[i],N+1,M+1)) upd(maxC,outC(N,M,data[i]));
            if(inRange(data[i],0  ,  0)) upd(maxF,outF(N,M,data[i]));
            if(inRange(data[i],N+1,  0)) upd(maxH,outH(N,M,data[i]));
        }
        return maxA+maxC+maxF+maxH;
    }
      
    ll calRi(int r){
        return 1ll*((r<<1)+2)*(r+1)>>1ll;
    }
      
    ll calRi2(int r){
        return 1ll*((r<<1)+2)*r>>1ll;
    }
      
    ll trangleArea(const Trangle &x){
        return calRi(x.r);
    }
      
    bool trangleIn(const Trangle &x,const Trangle &y){
        return x.x-x.r<=y.x-y.r&&x.x+x.r>=y.x+y.r;
    }
      
    bool notCross(const Trangle &x,const Trangle &y){
        return x.x+x.r<y.x-y.r;
    }
      
    ll sameArea(const Trangle &x,const Trangle &y){
        int l=y.x-y.r,r=x.x+x.r;
        if((r-l+1)&1) return calRi((r-l)>>1);
        return calRi2((r-l+1)>>1);
    }
      
    ll dp_trangle(int n,Trangle *pt){
        if(!n) return 0;
        int T=1;
        std::sort(pt+1,pt+n+1,cmp_Trangle);
        ll ans=trangleArea(pt[1]);
        for(int i=2;i<=n;i++){
            if(trangleIn(pt[T],pt[i])) continue;
            else if(notCross(pt[T],pt[i])) ans+=trangleArea(pt[i]),T=i;
            else ans+=trangleArea(pt[i])-sameArea(pt[T],pt[i]),T=i;
        }
        return ans;
    }
      
    ll exceed_Line(int N,int M,int n,pdd *data){
        int tot;
        ll ans=0;
        //Part I - ABC
        tot=0;
        for(int i=1;i<=n;i++){
            if(inRange(data[i],data[i].x,M+1))
                tmp[++tot]=(Trangle){data[i].x,data[i].r-dist(data[i],data[i].x,M+1)};
        }
        ans+=dp_trangle(tot,tmp);
   
        //Part II - CEH
        tot=0;
        for(int i=1;i<=n;i++){
            if(inRange(data[i],N+1,data[i].y))
                tmp[++tot]=(Trangle){data[i].y,data[i].r-dist(data[i],N+1,data[i].y)};          
        }
        ans+=dp_trangle(tot,tmp);
   
        //Part III - FGH
        tot=0;
        for(int i=1;i<=n;i++){
            if(inRange(data[i],data[i].x,0))
                tmp[++tot]=(Trangle){data[i].x,data[i].r-dist(data[i],data[i].x,0)};        
        }
        ans+=dp_trangle(tot,tmp);
   
        //Part IV - ADF
        tot=0;
        for(int i=1;i<=n;i++){
            if(inRange(data[i],0,data[i].y))
                tmp[++tot]=(Trangle){data[i].y,data[i].r-dist(data[i],0,data[i].y)};            
        }
        ans+=dp_trangle(tot,tmp);
        return ans;
    }
}
   
pdd data[maxn];
int N,M,n,tot;
polygon sd[maxn];
   
point cp1(int x,int y){
//  assert(!((x+y)&1));
    return (point){(x+y)>>1,(y-x)>>1};
}
   
point cp2(int x,int y){
//  assert((x+y)&1);
    return cp1(x-1,y);
}
   
ll part_Unlimited(){
    ll ans=0;
    //on diagonal
    tot=0;
    for(int i=1,rb,rc;i<=n;i++){
        rb=data[i].r>>1,rc=(data[i].r-1)>>1;
        if((data[i].x+data[i].y)&1^1) sd[++tot]=(polygon){cp1(data[i].x-(rb<<1),data[i].y),cp1(data[i].x+(rb<<1),data[i].y)};
        else if(data[i].r>0) sd[++tot]=(polygon){cp1(data[i].x-(rc<<1)-1,data[i].y),cp1(data[i].x+(rc<<1)+1,data[i].y)};
    }
    compute::arrange(sd+1,sd+tot+1);
    ans+=compute::rectangle_cross_area(tot,sd);
    //not on diagonal
    tot=0;
    for(int i=1,rb,rc;i<=n;i++){
        rb=data[i].r>>1,rc=(data[i].r-1)>>1;
        if((data[i].x+data[i].y)&1) sd[++tot]=(polygon){cp2(data[i].x-(rb<<1),data[i].y),cp2(data[i].x+(rb<<1),data[i].y)};
        else if(data[i].r>0) sd[++tot]=(polygon){cp2(data[i].x-(rc<<1)-1,data[i].y),cp2(data[i].x+(rc<<1)+1,data[i].y)};
    }
    compute::arrange(sd+1,sd+tot+1);
    ans+=compute::rectangle_cross_area(tot,sd);
    return ans;
}
   
ll part_Exceed(){
    ll ans=0;
    ans-=compute2::exceed_ACFH(N,M,n,data);
    ans+=compute2::exceed_Line(N,M,n,data);
    return ans;
}
   
int main(){
	freopen("soldier.in","r",stdin);
	freopen("soldier.out","w",stdout);
    read(N),read(M),read(n);
    for(int i=1;i<=n;i++) data[i].scan();
    printf("%lld\n",part_Unlimited()-part_Exceed());
    return 0;
}