洛谷P5524:[Ynoi2012]D1T1——题解
2024-09-05 12:54:23
https://www.luogu.org/problem/P5524
看着能做就当线段树复健题了。
根据高中知识我们有
$sin(a+b)=sin(a)cos(b)+cos(a)sin(b)$
$cos(a+b)=cos(a)cos(b)-sin(a)sin(b)$
那这题只需要维护区间$sin$和与$cos$和的线段树就好了,完后区间加的更新方法如上。
但是比较卡常,建议标记永久化,并且减少求$sincos$的次数。(反正我开O2过了就不管了233)
~~我真的是连线段树都不会敲了我乱push结果RE了debug了半天,难受555~~
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double dl;
const int N=2e5+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct tree{
dl s,c;
ll w;
}tr[N<<];
int b[N];
inline void pushup(int a){
tr[a].s=tr[a<<].s+tr[a<<|].s;
tr[a].c=tr[a<<].c+tr[a<<|].c;
return;
}
inline void upd(int a,dl S,dl C){
dl s=tr[a].s,c=tr[a].c;
tr[a].s=s*C+c*S;
tr[a].c=c*C-s*S;
return;
}
inline void pushdown(int a){
if(!tr[a].w)return;
dl s=sin(tr[a].w),c=cos(tr[a].w);
upd(a<<,s,c);upd(a<<|,s,c);
tr[a<<].w+=tr[a].w;tr[a<<|].w+=tr[a].w;
tr[a].w=;return;
}
void build(int a,int l,int r){
if(l==r){
tr[a].s=sin(b[l]);tr[a].c=cos(b[l]);return;
}
int mid=(l+r)>>;
build(a<<,l,mid);build(a<<|,mid+,r);
pushup(a);
}
void add(int a,int l,int r,int l1,int r1,int v){
if(r<l1||r1<l)return;
if(l1<=l&&r<=r1){
upd(a,sin(v),cos(v));tr[a].w+=v;return;
}
int mid=(l+r)>>;pushdown(a);
add(a<<,l,mid,l1,r1,v);add(a<<|,mid+,r,l1,r1,v);
pushup(a);
}
dl qry(int a,int l,int r,int l1,int r1){
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1)return tr[a].s;
int mid=(l+r)>>;pushdown(a);
return qry(a<<,l,mid,l1,r1)+qry(a<<|,mid+,r,l1,r1);
}
int main(){
int n=read();
for(int i=;i<=n;i++)b[i]=read();
build(,,n);
int m=read();
while(m--){
int op=read(),l=read(),r=read();
if(op==){
int v=read();
add(,,n,l,r,v);
}else printf("%.1lf\n",qry(,,n,l,r));
}
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
最新文章
- maven profile的使用
- 【Android开发实践】android.view.InflateException: Binary XML file line #12: Error inflating class fragment问题解决
- Android项目架构之业务组件化
- Codrops 教程:基于 CSS3 的精美模态窗口效果
- [Android Pro] Android 4.1 使用 Accessibility实现免Root自动批量安装功能
- error MSB6006: &ldquo;cmd.exe&rdquo;已退出,代码为 3。
- JDK和JVM
- 用Myeclipse 编写struts.xml时,自动提示
- Nunit测试工具使用实例
- Linux Supervisor的安装与使用入门
- 基于VC++的网络扫描器设计与实现
- 如何将composer设置为全局变量?
- C++中set的用法
- Python Number 类型转换
- C# 集合 特殊集合
- jQuery事件处理(六)
- test20180830
- 13_Java面向对象_第13天(static、final、匿名对象、内部类、包、修饰符、代码块)_讲义
- 关于分布式存储系统中-CAP原则(CAP定理)与BASE理论比较
- Android——SD卡工具类——SDCardUtils.java