HAOI2012高速公路——子区间计算
2024-08-30 14:03:13
题目：https://www.luogu.org/problemnew/show/P2221
似乎按点来算贡献很方便，但我抱住一篇没有这样的题解磕了两天...
以下转载：
题意：维护一段数列 支持区间加和求区间所有子区间的和的和
一看就知道要用线段树 于是用sum表示区间所有子区间的和的和 但是知道两个区间的sum并不能求出这两个区间并起来之后的sum 这时我们可以手玩一下
sum(1 2 3 4)=(1)+(2)+(1 2)+(3)+(4)+(3 4)+(2 3)+(1 2 3)+(2 3 4)+(1 2 3 4)竖着写在纸上 就会发现除了sum(1 2)和sum(3 4)外 所有包含左区间右端点的区间和(rsum)恰被算了len(右区间)次 同理包含右区间左端点的区间和(lsum)被算了len(左区间)次
于是 我们得到了sum(a b)=sum(a)+sum(b)+rsum(a)·len(b)+lsum(b)·len(a)
那么如何维护lsum和rsum呢 显然lsum(a b)=lsum(a)+lsum(b)+区间和(a)*len(b) rsum同理
至此维护操作已经没问题了 pushdown操作就简单很多了 当一个区间整体加a时 它的sum增加了a(n+2(n-1)+3(n-2)+...+n)也就是a((1+...+n)n-(1^2+...+(n-1)^2)-(1+...(n-1))) lsum rsum 同理 最后注意取GCD
看样子很精妙，似乎也挺好写的；
然而因为还是理解不到位，犯了众多细节的错误，调了两天，令人疯狂：
1.线段树上的每个点是车站之间的一段，所以读入的n和r都要-1；
2.需要另外记录纯粹的区间和(s)，用于计算sum，lsum，rsum等等，而不是直接用sum一概计算；
3.采用那样的build写法，竟然一度忘记在pushup里更新len，调了半天；
*4.注意这个背景下的线段树与平常的线段树写法有所不同：
平常的线段树在修改、查询时都会传下去一个目标区间，一般来说这个目标区间不用更改，判断只需看是否在其内部就可以；
但这道题的计算是需要用到目标区间的，所以在把操作下放到子区间时，其目标区间也必须相应有所修改，否则在计算时就会大错特错；
也正因此，必须进行判断：目标区间是完全在左儿子，还是完全在右儿子，还是在中间；不同的情况中目标区间的修改也有所不同。
虽然这种写法似乎不是很优秀，但在线段树中痛苦挣扎的过程中，我认识到就算是线段树也不能不求甚解，靠习惯打板子；必须根据题目灵活调整，否则就会出现错误。
错误版本1：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=4e5+;
int n,m;
struct N{
int sum,lsum,rsum,len,lzy;
int s;//!
}t[maxn];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void yf(int x,int nn)//nn
{
int y=(+nn)*nn/;
int a=x,b=y;
if(a<b)swap(a,b);
int c=gcd(a,b);
printf("%d/%d\n",x/c,y/c);
}
int cala(int x)//add
{
int nn=t[x].len;
int n=nn-;
return (+nn)*nn/*nn-(+n)*n/-n*(n+)*(n*+)/;//
}
int calb(int x)//lsum,rsum add
{
int nn=t[x].len;
return (+nn)*nn/;
}
void pushup(int x)
{
int ls=(x<<),rs=(x<<|);
t[x].len=t[x<<].len+t[x<<|].len;
t[x].s=t[x<<].s+t[x<<|].s;
t[x].sum=t[ls].sum+t[rs].sum+t[ls].rsum*t[rs].len+t[rs].sum*t[ls].len;
t[x].lsum=t[ls].lsum+t[rs].lsum+t[ls].s*t[rs].len;//s
t[x].rsum=t[ls].rsum+t[rs].rsum+t[rs].s*t[ls].len;
}
void build(int l,int r,int x)
{
if(l==r)
{
t[x].len=;
return;
}
int mid=((l+r)>>);
build(l,mid,x<<);
build(mid+,r,x<<|);
pushup(x);
}
void pushdown(int x)
{
if(t[x].lzy)
{
int v=t[x].lzy;t[x].lzy=;
int ls=(x<<),rs=(x<<|);
t[ls].s+=t[ls].len*v;
t[ls].sum+=cala(ls)*v;
t[ls].lsum+=calb(ls)*v;
t[ls].rsum+=calb(ls)*v;
t[ls].lzy+=v;
t[rs].s+=t[rs].len*v;
t[rs].sum+=cala(rs)*v;
t[rs].lsum+=calb(rs)*v;
t[rs].rsum+=calb(rs)*v;
t[rs].lzy+=v;
}
}
void add(int l,int r,int L,int R,int v,int x)
{
if(l>=L&&r<=R)
{
t[x].s+=t[x].len*v;
t[x].sum+=cala(x)*v;
t[x].lsum+=calb(x)*v;
t[x].rsum+=calb(x)*v;
t[x].lzy+=v;
return;
}
pushdown(x);
int mid=((l+r)>>);
if(L<=mid)add(l,mid,L,R,v,x<<);
if(R>mid)add(mid+,r,L,R,v,x<<|);
pushup(x);
}
int qs(int l,int r,int L,int R,int x)
{
if(l>=L&&r<=R)return t[x].s;
pushdown(x);
int ret=;
int mid=((l+r)>>);
if(L<=mid)ret+=qs(l,mid,L,R,x<<);
if(R>mid)ret+=qs(mid+,r,L,R,x<<|);
return ret;
}
int qls(int l,int r,int L,int R,int x)
{
if(l>=L&&r<=R)return t[x].lsum;
pushdown(x);
int mid=((l+r)>>);
if(L>mid)return qls(mid+,r,L,R,x<<|);
if(R<=mid)return qls(l,mid,L,R,x<<);
return qls(mid+,r,L,R,x<<|)+qls(l,mid,L,R,x<<)+qs(l,mid,L,R,x<<)*t[x<<|].len;
}
int qrs(int l,int r,int L,int R,int x)
{
if(l>=L&&r<=R)return t[x].rsum;
pushdown(x);
int mid=((l+r)>>);
if(L>mid)return qrs(mid+,r,L,R,x<<|);
if(R<=mid)return qrs(l,mid,L,R,x<<);
return qrs(mid+,r,L,R,x<<|)+qrs(l,mid,L,R,x<<)+qs(mid+,r,L,R,x<<|)*t[x<<].len;
}
int query(int l,int r,int L,int R,int x)
{
if(l>=L&&r<=R)return t[x].sum;
pushdown(x);
int mid=((l+r)>>);
if(L>mid)return query(mid+,r,L,R,x<<|);
if(R<=mid)return query(l,mid,L,R,x<<);
return query(mid+,r,L,R,x<<|)+query(l,mid,L,R,x<<)
// +qrs(l,mid,L,R,x<<1)*t[x<<1|1].len+qls(mid+1,r,L,R,x<<1|1)*t[x<<1].len;
+qrs(l,mid,L,R,x<<)*(R-mid)+qls(mid+,r,L,R,x<<|)*(mid-L+);
}
int main()
{
scanf("%d%d",&n,&m);
n--;//
build(,n,);
for(int i=,l,r,v;i<=m;i++)
{
char dc;
cin>>dc;
scanf("%d%d",&l,&r);//车站而非间距
r--;
if(dc=='C')
{
scanf("%d",&v);
add(,n,l,r,v,);
}
if(dc=='Q')
{
int k=query(,n,l,r,);
yf(k,r-l+);
}
}
return ;
}
囧
错误版本2：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll const maxn=5e5+;
ll n,m;
struct N{
ll sum,lsum,rsum,len,lzy;
ll s;//!
}t[maxn];
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
void yf(ll x,ll nn)//nn
{
ll y=(+nn)*nn/;
ll a=x,b=y;
if(a<b)swap(a,b);
ll c=gcd(a,b);
printf("%lld/%lld\n",x/c,y/c);
}
ll cala(ll x)//add
{
ll nn=t[x].len;
ll n=nn-;
return (+nn)*nn/*nn-(+n)*n/-n*(n+)*(n*+)/;//
}
ll calb(ll x)//lsum,rsum add
{
ll nn=t[x].len;
return (+nn)*nn/;
}
void pushup(ll x)
{
ll ls=(x<<),rs=(x<<|);
// t[x].len=t[x<<1].len+t[x<<1|1].len;
t[x].s=t[x<<].s+t[x<<|].s;
t[x].sum=t[ls].sum+t[rs].sum+t[ls].rsum*t[rs].len+t[rs].lsum*t[ls].len;
t[x].lsum=t[ls].lsum+t[rs].lsum+t[ls].s*t[rs].len;//s
t[x].rsum=t[ls].rsum+t[rs].rsum+t[rs].s*t[ls].len;
}
void build(ll l,ll r,ll x)
{
t[x].len=r-l+;
if(l==r)
{
// t[x].len=1;
return;
}
ll mid=((l+r)>>);
build(l,mid,x<<);
build(mid+,r,x<<|);
pushup(x);
}
void pushdown(ll x)
{
if(t[x].lzy)
{
ll v=t[x].lzy;t[x].lzy=;
ll ls=(x<<),rs=(x<<|);
t[ls].s+=t[ls].len*v;
t[ls].sum+=cala(ls)*v;
t[ls].lsum+=calb(ls)*v;
t[ls].rsum+=calb(ls)*v;
t[ls].lzy+=v;
t[rs].s+=t[rs].len*v;
t[rs].sum+=cala(rs)*v;
t[rs].lsum+=calb(rs)*v;
t[rs].rsum+=calb(rs)*v;
t[rs].lzy+=v;
}
}
void add(ll l,ll r,ll L,ll R,ll v,ll x)
{
if(l>=L&&r<=R)//
{
t[x].s+=t[x].len*v;
t[x].sum+=cala(x)*v;
t[x].lsum+=calb(x)*v;
t[x].rsum+=calb(x)*v;
t[x].lzy+=v;
return;
}
pushdown(x);
ll mid=((l+r)>>);
if(R<=mid)add(l,mid,L,R,v,x<<);
else if(L>mid)add(mid+,r,L,R,v,x<<|);
else
{
add(l,mid,L,R,v,x<<);
add(mid+,r,L,R,v,x<<|);
}
pushup(x);
}
ll qs(ll l,ll r,ll L,ll R,ll x)
{
if(l>=L&&r<=R)return t[x].s;//
pushdown(x);
ll mid=((l+r)>>);
if(R<=mid)return qs(l,mid,L,R,x<<);
if(L>mid)return qs(mid+,r,L,R,x<<|);
return qs(l,mid,L,R,x<<)+qs(mid+,r,L,R,x<<|);
}
ll qls(ll l,ll r,ll L,ll R,ll x)
{
if(l>=L&&r<=R)return t[x].lsum;//
pushdown(x);
ll mid=((l+r)>>);
if(L>mid)return qls(mid+,r,L,R,x<<|);
if(R<=mid)return qls(l,mid,L,R,x<<);
return qls(mid+,r,L,R,x<<|)+qls(l,mid,L,R,x<<)+qs(l,mid,L,R,x<<)*(R-mid);
}
ll qrs(ll l,ll r,ll L,ll R,ll x)
{
if(l>=L&&r<=R)return t[x].rsum;//
pushdown(x);
ll mid=((l+r)>>);
if(L>mid)return qrs(mid+,r,L,R,x<<|);
if(R<=mid)return qrs(l,mid,L,R,x<<);
return qrs(mid+,r,L,R,x<<|)+qrs(l,mid,L,R,x<<)+qs(mid+,r,L,R,x<<|)*(mid-L+);
}
ll query(ll l,ll r,ll L,ll R,ll x)
{
// cout<<l<<" "<<r<<endl;
// printf("*%lld %lld\n",L,R);
if(l>=L&&r<=R)return t[x].sum;//
pushdown(x);
ll mid=((l+r)>>);
if(L>mid)return query(mid+,r,L,R,x<<|);
if(R<=mid)return query(l,mid,L,R,x<<);
return query(mid+,r,L,R,x<<|)+query(l,mid,L,R,x<<)
+qrs(l,mid,L,R,x<<)*(R-mid)+qls(mid+,r,L,R,x<<|)*(mid-L+);
}
int main()
{
scanf("%lld%lld",&n,&m);
n--;//
build(,n,);
for(ll i=,l,r,v;i<=m;i++)
{
char dc;
cin>>dc;
scanf("%lld%lld",&l,&r);//车站而非间距
r--;
if(dc=='C')
{
scanf("%lld",&v);
add(,n,l,r,v,);
}
if(dc=='Q')
{
ll k=query(,n,l,r,);
yf(k,r-l+);
}
}
return ;
}
囧
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll const maxn=5e5+;
ll n,m;
struct N{
ll sum,lsum,rsum,len,lzy;
ll s;//!
}t[maxn];
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
void yf(ll x,ll nn)//nn
{
ll y=(+nn)*nn/;
ll a=x,b=y;
if(a<b)swap(a,b);
ll c=gcd(a,b);
printf("%lld/%lld\n",x/c,y/c);
}
ll cala(ll x)//add
{
ll nn=t[x].len;
ll n=nn-;
return (+nn)*nn/*nn-(+n)*n/-n*(n+)*(n*+)/;//
}
ll calb(ll x)//lsum,rsum add
{
ll nn=t[x].len;
return (+nn)*nn/;
}
void pushup(ll x)
{
ll ls=(x<<),rs=(x<<|);
t[x].len=t[x<<].len+t[x<<|].len;
t[x].s=t[x<<].s+t[x<<|].s;
t[x].sum=t[ls].sum+t[rs].sum+t[ls].rsum*t[rs].len+t[rs].lsum*t[ls].len;
t[x].lsum=t[ls].lsum+t[rs].lsum+t[ls].s*t[rs].len;//s
t[x].rsum=t[ls].rsum+t[rs].rsum+t[rs].s*t[ls].len;
}
void build(ll l,ll r,ll x)
{
// t[x].len=r-l+1;
if(l==r)
{
t[x].len=;
return;
}
ll mid=((l+r)>>);
build(l,mid,x<<);
build(mid+,r,x<<|);
pushup(x);
}
void pushdown(ll x)
{
if(t[x].lzy)
{
ll v=t[x].lzy;t[x].lzy=;
ll ls=(x<<),rs=(x<<|);
t[ls].s+=t[ls].len*v;
t[ls].sum+=cala(ls)*v;
t[ls].lsum+=calb(ls)*v;
t[ls].rsum+=calb(ls)*v;
t[ls].lzy+=v;
t[rs].s+=t[rs].len*v;
t[rs].sum+=cala(rs)*v;
t[rs].lsum+=calb(rs)*v;
t[rs].rsum+=calb(rs)*v;
t[rs].lzy+=v;
}
}
void add(ll l,ll r,ll L,ll R,ll v,ll x)
{
if(l>=L&&r<=R)//
{
t[x].s+=t[x].len*v;
t[x].sum+=cala(x)*v;
t[x].lsum+=calb(x)*v;
t[x].rsum+=calb(x)*v;
t[x].lzy+=v;
return;
}
pushdown(x);
ll mid=((l+r)>>);
if(R<=mid)add(l,mid,L,R,v,x<<);
else if(L>mid)add(mid+,r,L,R,v,x<<|);
else
{
add(l,mid,L,mid,v,x<<);
add(mid+,r,mid+,R,v,x<<|);
}
pushup(x);
}
ll qs(ll l,ll r,ll L,ll R,ll x)
{
if(l==L&&r==R)return t[x].s;//
pushdown(x);
ll mid=((l+r)>>);
if(R<=mid)return qs(l,mid,L,R,x<<);
if(L>mid)return qs(mid+,r,L,R,x<<|);
return qs(l,mid,L,mid,x<<)+qs(mid+,r,mid+,R,x<<|);
}
ll qls(ll l,ll r,ll L,ll R,ll x)
{
if(l==L&&r==R)return t[x].lsum;//
pushdown(x);
ll mid=((l+r)>>);
if(L>mid)return qls(mid+,r,L,R,x<<|);
if(R<=mid)return qls(l,mid,L,R,x<<);
return qls(mid+,r,mid+,R,x<<|)+qls(l,mid,L,mid,x<<)
+qs(l,mid,L,mid,x<<)*(R-mid);
}
ll qrs(ll l,ll r,ll L,ll R,ll x)
{
if(l==L&&r==R)return t[x].rsum;//
pushdown(x);
ll mid=((l+r)>>);
if(L>mid)return qrs(mid+,r,L,R,x<<|);
if(R<=mid)return qrs(l,mid,L,R,x<<);
return qrs(mid+,r,mid+,R,x<<|)+qrs(l,mid,L,mid,x<<)
+qs(mid+,r,mid+,R,x<<|)*(mid-L+);
}
ll query(ll l,ll r,ll L,ll R,ll x)//注意L,R要纳入计算
{
// cout<<l<<" "<<r<<endl;
// printf("*%lld %lld\n",L,R);
if(l==L&&r==R)return t[x].sum;//
pushdown(x);
ll mid=((l+r)>>);
if(L>mid)return query(mid+,r,L,R,x<<|);
if(R<=mid)return query(l,mid,L,R,x<<);
return query(mid+,r,mid+,R,x<<|)+query(l,mid,L,mid,x<<)
+qrs(l,mid,L,mid,x<<)*(R-mid)+qls(mid+,r,mid+,R,x<<|)*(mid-L+);//!
}
int main()
{
scanf("%lld%lld",&n,&m);
n--;//
build(,n,);
for(ll i=,l,r,v;i<=m;i++)
{
char dc;
cin>>dc;
scanf("%lld%lld",&l,&r);//车站而非间距
r--;
if(dc=='C')
{
scanf("%lld",&v);
add(,n,l,r,v,);
}
if(dc=='Q')
{
ll k=query(,n,l,r,);
yf(k,r-l+);
}
}
return ;
}
最新文章
- PHP Datatype Conversion Safety Risk、Floating Point Precision、Operator Security Risk、Safety Coding Principle
- PHP 知识点链接
- Jquery 复习练习（02）Javascript 与jquery 互转 onclick 与click区别
- openstack cinder-volume 的高可用（HA）
- 用ASP.NET Core 1.0中实现邮件发送功能-阿里云邮件推送篇
- win8， VS2013 .NET 4.5在哪找svcutil.exe？
- reveal 1.6.3 本机破解及使用
- UWP 调用outlook邮箱反馈
- 自学Zabbix1.2-zabbix特性
- CNN中的卷积操作的参数数计算
- 20165305 苏振龙 《Java 程序设计》第一次测试总结
- CF-503div2-A/B/C
- android http json请求3种不同写法
- 冒泡排序(Bubble Sort)，比较次数优化改进
- MySQL存储过程使用实例详解
- ONTAK2010 Peaks加强版(离线&在线)
- 关于webstorm启动后闪退
- js经典试题之运算符的优先级
- 微信公众号开发java框架：wx4j（入门篇）
- 【转载】SQL server connection KeepAlive
热门文章
- C# 打印日志
- Mysql数据库中CURRENT_TIMESTAMP和ON UPDATE CURRENT_TIMESTAMP区别
- 软件系统架构 https://www.lanhusoft.com/Article/349.html
- Web优化 --利用css sprites降低图片请求
- iOS提交应用至App Store流程及真机调试 一，证书、配置文件
- chrome自带的调试工具
- java类加载机制的代码实例
- Service Mesh vs SideCar
- ubuntu git ssh不通
- Iterator && Iterable Collection && Map