背景
买了新电脑,就想着先把这道心腹大患解决了,起步即蓝题,开个好头,顺便水一篇题解。
题目大意
给出一个长度为nnn的整数序列a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an,进行mmm次操作,操作分为两类。
操作111:给出l,r,vl,r,vl,r,v,将al,al+1,…,ara_l,a_{l+1},\ldots,a_ral,al+1,…,ar分别加上vvv。
操作222:给出l,rl,rl,r,询问∑i=lrsin(ai)\sum\limits_{i=l}^{r}\sin(a_i)i=l∑rsin(ai)。
第一行输入一个整数nnn。
接下来一行nnn个整数表示a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an。
接下来一行一个整数mmm。
接下来mmm行,每行表示一个操作,操作111表示为1 l r v,操作222表示为2 l r。
对每个操作222,输出一行,表示答案,四舍五入保留一位小数。
保证答案的绝对值大于0.10.10.1,且答案的准确值的小数点后第二位不是444或555。
保证1≤n,m,ai,v≤2×1051\leq n,m,a_i,v\leq 2\times 10^51≤n,m,ai,v≤2×105,1≤l≤r≤n1\leq l\leq r\leq n1≤l≤r≤n。保证所有输入的数都是正整数。
思路
三角函数对本初三蒟蒻很显然不是很友好,需要和差角公式:
sin(A+B)=sinAcosB+cosAsinB\sin(A+B)=\sin A \cos B+\cos A \sin Bsin(A+B)=sinAcosB+cosAsinB
cos(A+B)=cosAcosB−sinAsinB\cos(A+B)=\cos A\cos B-\sin A\sin Bcos(A+B)=cosAcosB−sinAsinB
知道公式,就要开始搓线段树。
ts[o]ts[o]ts[o]维护区间的正弦值之和,tc[o]tc[o]tc[o]维护区间的余弦值之和,lazy[o]lazy[o]lazy[o]维护区间要加的数(整数)。
有两个地方需要用到和差角公式:pushdown和update。
pushdown时,要用lazy[o]lazy[o]lazy[o]更新ts/tc[o×2]ts/tc[o\times 2]ts/tc[o×2]和ts/tc[o×2+1]ts/tc[o\times 2+1]ts/tc[o×2+1]。
update时,要用vvv更新ts/tc[o]ts/tc[o]ts/tc[o]的值。
其实就是把求和变成公式求和,除了代码麻烦点儿,思路还是很清晰。
代码
#include<bits/stdc++.h>usingnamespacestd;#defineN200005#defineintlonglong//必备intn,m,a[N],lazy[4*N];doublets[4*N],tc[4*N];//voidbuild(into,intl,intr){if(l==r){ts[o]=sin(a[l]);tc[o]=cos(a[l]);return;}intmid=(l+r)/2;build(o*2,l,mid);build(o*2+1,mid+1,r);ts[o]=ts[o*2]+ts[o*2+1];tc[o]=tc[o*2]+tc[o*2+1];}voidpushdown(into,intl,intr){if(!lazy[o])return;lazy[o*2]+=lazy[o];lazy[o*2+1]+=lazy[o];doublesinb=sin(lazy[o]),cosb=cos(lazy[o]);doublesina=ts[o*2],cosa=tc[o*2];ts[o*2]=sina*cosb+cosa*sinb;tc[o*2]=cosa*cosb-sina*sinb;sina=ts[o*2+1],cosa=tc[o*2+1];ts[o*2+1]=sina*cosb+cosa*sinb;tc[o*2+1]=cosa*cosb-sina*sinb;lazy[o]=0;}voidupdate(into,intl,intr,intx,inty,intv){if(x<=l&&r<=y){doublesina=ts[o],sinb=sin(v),cosa=tc[o],cosb=cos(v);ts[o]=sina*cosb+cosa*sinb;tc[o]=cosa*cosb-sina*sinb;lazy[o]+=v;return;}pushdown(o,l,r);intmid=(l+r)/2;if(x<=mid)update(o*2,l,mid,x,y,v);if(y>mid)update(o*2+1,mid+1,r,x,y,v);ts[o]=ts[o*2]+ts[o*2+1];tc[o]=tc[o*2]+tc[o*2+1];}doublequery(into,intl,intr,intx,inty){if(x<=l&&r<=y)returnts[o];pushdown(o,l,r);intmid=(l+r)/2;doubleans=0;if(x<=mid)ans+=query(o*2,l,mid,x,y);if(y>mid)ans+=query(o*2+1,mid+1,r,x,y);returnans;}signedmain(){scanf("%lld",&n);for(inti=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);scanf("%lld",&m);intop,l,r,v;while(m--){scanf("%lld%lld%lld",&op,&l,&r);if(op==1){scanf("%lld",&v);update(1,1,n,l,r,v);}else{doubleans=query(1,1,n,l,r);printf("%.1lf\n",ans);}}return0;}温馨提示:分割线以下内容糖分超标,谨慎观看。(但你已经看到了)😏
Conclusion
凑字数
虽然不是自己独立思考的结果,但是看见自己也能AC蓝题,还是非常有成就感。
虽然现在本蒟蒻还是有时会亖在橙题上,但我觉得努力一定会有收获,将来我也一定能切越来越多的蓝题、紫题、黑题……学无止境 ,超越自我。
谨以此篇,纪念自己的首道蓝题。\pmb{谨以此篇,纪念自己的首道蓝题。}谨以此篇,纪念自己的首道蓝题。
祝即将中考的自己和广大考生:\pmb{祝即将中考的自己和广大考生:}祝即将中考的自己和广大考生:
中考必胜!金榜题名!\pmb{中考必胜!金榜题名!}中考必胜!金榜题名!