题解 P4231 【三步必杀】
这样好的 线段树 题，居然没有一篇关于线段树的题解？
(事先声明一下，本蒟蒻用线段树AC不了这题，本题解只是讲一下线段树的思路)
先看一道很像的题：P1438 无聊的数列
很明显，都是加一个等差数列，但它们是区间修改，单点询问，怎么转化为区间修改，区间询问呢？
可以建立一个sum数组记录差分，则有：损伤度[i]=sum[1]+sum[2]+...+sum[i]
显然，我们已经将这题转化为区间修改，区间询问，可以用线段树了：
用差分修改区间，加法标记用lazytag，一道线段树模板题！
上代码(再次声明线段树代码不能AC)：
#include<cstdio>
typedef long long ll;
ll n,m,add[40000005],l,r,s,e,o,x,y,sum[40000005];
void build(int k,int l,int r)
{
if(l==r){sum[k]=0;return;}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
void Add(int k,int l,int r,int v)
{
add[k]+=v;
sum[k]+=(ll)v*(r-l+1);
}
void pushdown(int k,int l,int r,int mid)
{
if(!add[k])return;
Add(k<<1,l,mid,add[k]);
Add(k<<1|1,mid+1,r,add[k]);
add[k]=0;
}
void modify(int k,int l,int r,int x,int y,int v)
{
if(x<=l&&y>=r)return Add(k,l,r,v);
int mid=l+r>>1;
pushdown(k,l,r,mid);
if(x<=mid)modify(k<<1,l,mid,x,y,v);
if(y>mid)modify(k<<1|1,mid+1,r,x,y,v);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
ll query(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)return sum[k];
int mid=l+r>>1;
ll s=0;
pushdown(k,l,r,mid);
if(x<=mid)s+=query(k<<1,l,mid,x,y);
if(y>mid)s+=query(k<<1|1,mid+1,r,x,y);
return s;
}//上面全是线段树模板
int main()
{
scanf("%lld%lld",&n,&m);
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld%lld",&l,&r,&s,&e);
o=(e-s)/(r-l);//计算公差
modify(1,1,n,l,l,s);//加上首项
modify(1,1,n,l+1,r,o);//后面分别加上公差
modify(1,1,n,r+1,r+1,-s-(r-l)*o);//把多余部分减去
}
for(int i=1;i<=n;i++)
{
ll now=query(1,1,n,1,i);//now=损伤度[i]
x^=now;
y=now>y?now:y;
}
printf("%lld %lld",x,y);
return 0;
}然而，由于线段树的特性，数组不得不开到4 n，所以愉快的MLE了
特判变成2 n还是不行
甚至吸了氧也没用
本题正解还是差分数组(反正本蒟蒻用线段树不行)，但线段树的思路也很实用，可以用来AC很多类似的题目
管理大大求过