JZOJ(GMOJ)1495. 宝石[扫描线]

今天滚回提高,感觉挺不舒服的,

然后突然想起来写篇博客

随便水一篇吧

Description

见上帝动了恻隐之心，天后也想显示一下慈悲之怀，随即从口袋中取出一块魔术方巾，让身边的美神维纳斯拿到后堂的屏风上去试试，屏风是正方形的，高和宽方向上各划有m条鱼屏风的边平行的直线，平行直线间的距离为1厘米。这2m条直线共有m*m个交点，在某些交点上镶嵌着宝石。如果魔术方巾的边与屏风的边平行且魔术方巾触碰到屏风上镶嵌着的宝石，就将与这些宝石等值的金银送给人们。维纳斯想让魔术方巾触碰到的宝石的价值最多，可要在短短的1秒钟之内解决问题，也感到力不从心，你能帮帮她吗？

Input

输入文件gem.in的第一行有三个正整数m,n,k，数与数之间用一个空格分隔。其中m为屏风在高和宽方向上被划分出的直线数。魔术方巾为正方形的，它的边长为k厘米。N为屏风上宝石的个数。

接下来的n行，每行三个正整数，依次表示宝石所在直线的行号、列号、宝石的价值，数与数之间用一个空格分隔。

Output

输出文件gem.out只有一个正整数，为魔术方巾触碰到的宝石的最大价值总数。

Sample Input

10 4 4

1 1 9

2 3 5

6 2 12

4 5 6

Sample Output

23

【输入样例2】

10 4 3

1 1 9

2 3 5

6 2 12

4 5 6

【输出样例2】

18

Data Constraint

30%的数据，1≤m≤500,1≤n≤10000,1≤k≤100;

60%的数据，1≤m≤3000,1≤n≤10000,1≤k≤1000;

100%的数据，1≤m≤50000,1≤n≤50000,1≤k≤10000;

比较容易想到是扫描线

不过部分水法能过.

#include <cstdio>
#include <cstring>
#define np 65536
using namespace std;
long long max(long long x,long long y){return (x>y?x:y);}
long long min(long long x,long long y){return (x<y?x:y);}
int cn[50010],ln[50010];
long long val[50010];
void qsort(int l,int r)
{
	int i=l,j=r,m1=cn[(l+r)/2],m2=ln[(l+r)/2];
	long long t;
	while(i<=j)
	{
		while(cn[i]<m1||(cn[i]==m1&&ln[i]<m2)) i++;
		while(cn[j]>m1||(cn[j]==m1&&ln[j]>m2)) j--;
		if(i<=j)
		{
			t=cn[i];cn[i]=cn[j];cn[j]=t;
			t=ln[i];ln[i]=ln[j];ln[j]=t;
			t=val[i];val[i]=val[j];val[j]=t;
			i++;j--;
		}
	}
	if(i<r) qsort(i,r);
	if(l<j) qsort(l,j);
}
long long no[200000],lz[200000];
void lzdown(int x,int nl,int nr)
{
	no[x]+=lz[x];
	if(nl!=nr)
	{
		lz[x*2]+=lz[x];
		lz[x*2+1]+=lz[x];
	}
	lz[x]=0;
}
void change(int x,int nl,int nr,int l,int r,int v)
{
	lzdown(x,nl,nr);
	if(nl==l&&nr==r) {lz[x]+=v;return ;}
	int mid=(nl+nr)/2;
	if(l<=mid) change(x*2,nl,mid,l,min(mid,r),v);
	if(r>mid) change(x*2+1,mid+1,nr,max(mid+1,l),r,v);
	no[x]=max(no[x*2]+lz[x*2],no[x*2+1]+lz[x*2+1]);
}
int m;
int main()
{
	freopen("gem.in","r",stdin);
	freopen("gem.out","w",stdout);
	memset(no,0,sizeof(no));
	memset(lz,0,sizeof(lz));
	int n,K,st,i,j;
	scanf("%d%d%d",&m,&n,&K);
	for(i=1;i<=n;i++)
		scanf("%d%d%lld",&cn[i],&ln[i],&val[i]);
	qsort(1,n);
	st=1;j=1;
	long long ans=0;
	for(i=1;i<=n;i++)
	{
		while(cn[j]==cn[i]&&j<=n)
		{
			change(1,1,m,ln[j],min(ln[j]+K,m),val[j]);
			j++;
		}
		while(cn[st]<cn[i]-K&&st<=n)
		{
			change(1,1,m,ln[st],min(ln[st]+K,m),-val[st]);
			st++;
		}
		lzdown(1,1,m);
		ans=max(ans,no[1]+lz[1]);
	}
	printf("%lld\n",ans);
	return 0;
}