1 条题解

  • 0
    @ 2025-12-21 0:01:15
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include <cstdlib>
    using namespace std;
    #define maxk 300005
    long long read()
    {
        long long x=0,f=1; char ch=getchar();
        while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
        while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
        return x*f; 
    }
    
    long long max(long long a,int b)
    {
        if (a>b) return a;
        return b;
    }
    struct data{long long x,y,r;}in[maxk];
    struct dat{
        long long x,y1,y2,k;
        bool operator < (const dat & A) const
            {
                return x<A.x;
            }
    };
    struct da{
        long long st,ed;
        long long sqr()
            {
                if ((ed-st+1)&1) return (ed-st+2)*((ed-st+1)/2+1)/2;
                else return (ed-st+1+2)*((ed-st+1-2)/2+1)/2;
            }
        bool operator < (const da A) const
            {
                return st<A.st;
            }
    };
    int n,m,k;
    #define maxn 1200005
    struct SegmentTree{
        int del[maxn],tree[maxn];
        int Y[maxk];
        void clear()
            {
                memset(del,0,sizeof(del));
                memset(tree,0,sizeof(tree));
            }
        void updata(int now,long long l,long long r)
            {
                if (del[now]>0) tree[now]=r-l;
                else tree[now]=tree[now<<1]+tree[now<<1|1];
            }
        void insert(int now,int l,int r,int L,int R,int num)
            {
                int mid=(l+r)>>1;
                if (L<=Y[l] && R>=Y[r]) del[now]+=num; else
                    {
                        if (L<Y[mid]) insert(now<<1,l,mid,L,R,num);
                        if (R>Y[mid]) insert(now<<1|1,mid,r,L,R,num);
                    }
                updata(now,Y[l],Y[r]);
            }
        long long query()
            {
                return tree[1];
            }
    }T;
    
    struct cal{
        dat line[maxk];
        int tot,n;
        long long x1[maxk],x2[maxk],y1[maxk],y2[maxk];
        long long calc()
            {
                T.clear();
                for (int i=1; i<=n; i++) T.Y[i*2-1]=y1[i],T.Y[i*2]=y2[i];
                sort(T.Y+1,T.Y+2*n+1); tot=1;
                for (int i=2; i<=2*n; i++) if (T.Y[i]!=T.Y[i-1]) T.Y[++tot]=T.Y[i];
                for (int i=1; i<=n; i++)
                    {
                        line[i*2-1].x=x1[i]; line[i*2-1].y1=y1[i]; line[i*2-1].y2=y2[i];
                        line[i*2].x=x2[i]; line[i*2].y1=y1[i]; line[i*2].y2=y2[i];
                        line[i*2-1].k=1; line[i*2].k=-1;
                    }
                sort(line+1,line+2*n+1);
                long long ans=0,last=0;
                for (int i=1; i<=2*n; i++)
                    {
                        if (i!=1) ans=ans+last*(long long)((long long)(line[i].x)-(long long)line[i - 1].x);
                        if (last<0) {int a;a+=1;}
                        if (line[i].y1!=line[i].y2) T.insert(1,1,tot,line[i].y1,line[i].y2,line[i].k);
                        last=T.query();
                    }
            return ans;
        }
    }calc1, calc2;
    struct calcc{
        int n;
        da tri[maxk],tmp;
        long long cal()
            {
                if (n==0) return 0ll;
                long long ans=0; da tmp;
                sort(tri+1,tri+n+1);
                ans=tri[1].sqr(); int now=1;
                for (int i=2; i<=n; i++)
                    {
                        if (tri[i].st>=tri[now].st && tri[i].ed<=tri[now].ed) continue;
                        if (tri[i].st>tri[now].ed)
                            {
                                ans+=tri[i].sqr(); now=i; continue;
                            }
                        ans+=tri[i].sqr();tmp.st=tri[i].st; tmp.ed=tri[now].ed;
                        ans-=tmp.sqr(); now=i;
                    }
                return ans;
            }
    }tc[5];
    
    int main()
    {
        n=read(),m=read(),k=read();
        for (int i=1; i<=k; i++) in[i].x=read(),in[i].y=read(),in[i].r=read();
        calc1.n=calc2.n=k;
        for (int i=1; i<=k; i++)
            {
                int tmp=in[i].r-((in[i].x+in[i].y+in[i].r)&1);
                calc1.x1[i]=(in[i].x+in[i].y-tmp)>>1;
                calc1.y1[i]=(in[i].y-tmp-in[i].x)>>1;
                calc1.x2[i]=((in[i].x+in[i].y+ tmp)>>1)+1;
                calc1.y2[i]=((in[i].y+tmp-in[i].x)>>1)+1;
            }
        for (int i=1; i<=k; i++)
            {
                int tmp=in[i].r-(!((in[i].x+in[i].y+in[i].r)&1));
                calc2.x1[i]=(in[i].x+in[i].y-tmp-1)>>1;
                calc2.y1[i]=(in[i].y-tmp-in[i].x-1)>>1;
                calc2.x2[i]=((in[i].x+in[i].y+tmp-1)>>1)+1;
                calc2.y2[i]=((in[i].y+tmp-in[i].x-1)>>1)+1;
            }
        long long ans=0;
        ans=calc1.calc()+calc2.calc();
        for (int i=1; i<=k; i++) if (in[i].r>=in[i].x)
            {
                ++tc[1].n; 
                tc[1].tri[tc[1].n].st=in[i].y-(in[i].r-in[i].x);
                tc[1].tri[tc[1].n].ed=in[i].y+(in[i].r-in[i].x);
            }
        for (int i=1; i<=k; i++) if (in[i].r>=in[i].y)
            {
                ++tc[2].n; 
                tc[2].tri[tc[2].n].st=in[i].x-(in[i].r-in[i].y);
                tc[2].tri[tc[2].n].ed=in[i].x+(in[i].r-in[i].y);
            }
        for (int i=1; i<=k; i++) if (in[i].r>=n+1-in[i].x)
            {
                ++tc[3].n; 
                tc[3].tri[tc[3].n].st=in[i].y-(in[i].r-(n+1-in[i].x));
                tc[3].tri[tc[3].n].ed=in[i].y+(in[i].r-(n+1-in[i].x));
            }
        for (int i=1; i<=k; i++) if (in[i].r>=m+1-in[i].y)
            {
                ++tc[4].n; 
                tc[4].tri[tc[4].n].st=in[i].x-(in[i].r-(m+1-in[i].y));
                tc[4].tri[tc[4].n].ed=in[i].x+(in[i].r-(m+1-in[i].y));
            }
        for (int i=1; i<=4; i++)
            ans-=tc[i].cal();
        long long m1=0,m2=0,m3=0,m4=0;
        for (int i=1; i<=k; i++)
            {
                if (in[i].r>=in[i].x+in[i].y) m1=max(m1,1+in[i].r-in[i].x-in[i].y);
                if (in[i].r>=in[i].x+(m+1-in[i].y)) m2=max(m2, 1+in[i].r-in[i].x-(m+1-in[i].y));
                if (in[i].r>=in[i].y+(n+1-in[i].x)) m3=max(m3, 1+in[i].r-in[i].y-(n+1-in[i].x));
                if (in[i].r>=(m+1-in[i].y)+(n+1-in[i].x)) m4=max(m4,1+in[i].r-((m+1-in[i].y)+(n+1-in[i].x)));
            }
        ans+=m1*(m1+1)/2+m2*(m2+1)/2+m3*(m3+1)/2+m4*(m4+1)/2;
        printf("%lld\n",ans);
        return 0;
    }
    
    
    • 1

    信息

    ID
    4893
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者