自动搬运

查看原文

来自洛谷，原作者为

	紫妹只有17岁 **

搬运于2025-08-24 21:48:02，当前版本为作者最后更新于2018-10-22 19:42:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目好甜啊……虽然是个女孩子可是还是被甜到了呢……（话说要是有这么个小哥哥追我就好了……）

↑以上为题解作者的幻想

下面开始正题

话说这题真的甜，这道题的题意就是给定一条数轴，我们把数轴简化为一个数组，然后求规定大小的区间内的最大和

一看到就是树状数组码码码

这里的添加星星的操作就对应树状数组的update操作，求区间最大值就对应树状数组的sum操作

顺便安利一下树状数组

树状数组

一听到有树就很牛逼对不对，其实树状数组是一种很接地气的数据结构，然后比线段树好码多了

树状数组一般有三种操作（算上lowbit）

1.lowbit操作

也就是一层一层往下找的操作，然后具体为什么这么写请问度娘

树状数组

2.update操作

也就是更新节点的值的操作，注意这里的更新指的是加上一个数，也就是如果要变为0那么就要update原数的相反数

3.sum操作

也就是区间求和操作，当然这里的sum指的是从下标为1到下标为n进行求值，树状数组能够高效的求sum的原因就是因为有lowbit操作的存在

注意！前方丑能！

蒟蒻我自己用画图画的图

初学树状数组的话，可以先写模板

树状数组模板1

树状数组模板2

然后巩固可以写写逆序对

逆序对

红色的幻想乡

然后给一发代码，代码中值得注意的地方是

1.区间求值的时候边界不要写错了……（咕了一次）

2.树状数组代码一定要记牢（咕了一次）

代码太过简单所以注释比较少

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int c[N];//树状数组，这道题只是区间求和，不用存星星，所以不用再开一个星星数组
int n;
int w;
int Max=-1;//等下区间求和的时候比较最大值用
int x,y,z;
int lowbit(int x)//lowbit操作
{
	return x&(-x);
}
void update(int x,int v)//update操作
{
	while(x<=n)
	{
		c[x]+=v;
		x+=lowbit(x);
	}
}
int sum(int x)//区间求和操作
{
	int res=0;
	while(x>0)
	{
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
int main()
{
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++)//读入
		scanf("%d%d",&x,&y),update(x,y);
	for(int i=w;i<=100000;i++)//因为这里不想写n，于是我写了100000
	{
		Max=max(Max,sum(i-1)-sum(i-w-1));//区间最大值
	}
	printf("%d\n",Max);//输出
	return 0;
}