3228: [Sdoi2008]棋盘控制
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 23 Solved: 9
[Submit][Status][Discuss]
Description
在一个N * M的棋盘上，摆放着K个棋子，一个棋子占据一个格子(可能有多个棋子占据同一个格子)，控制棋盘上所有与它相距不超过R的格子。两个格子(X1,Y1)、(X2,Y2)间的距离定义为|X1-X2|+|Y1-Y2|。
试设计一个算法，计算出K个棋子控制的格子总数。
Input
第一行共三个正整数N，M，K。
以下K行，每行三个正整数X，Y，R，分别表示棋子的所在行，所在列和控制范围。
Output
共一个数，即控制的格子总数。
Sample Input
4 4 3
1 1 1
3 1 1
3 3 1
Sample Output
10
HINT
在 100% 的数据中，1≤N,M≤100000000，1≤K≤100000
Source
线段树+扫描线（一维），鬼畜的处理。。。恶心人
学了发扫描线的姿势。。真恶心。。。
code：（看着就难受）
#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;
}