NC17877. 整数序列
描述
输入描述
第一行一个整数n
接下来一行n个整数表示a1,a2,...,an
接下来一行一个整数m
接下来m行，每行表示一个操作，操作1表示为1 l r v，操作2表示为2 l r
保证1≤n,m,ai,v≤200000；1≤l≤r≤n，v是整数
输出描述
对每个操作2，输出一行，表示答案，四舍五入保留一位小数
保证答案的绝对值大于0.1，且答案的准确值的小数点后第二位不是4或5
数据随机生成（n,m人工指定，其余整数在数据范围内均匀选取），并去除不满足条件的操作2
示例1
输入:
4 1 2 3 4 5 2 2 4 1 1 3 1 2 2 4 1 2 4 2 2 1 3
输出:
0.3 -1.4 -0.3
C++(g++ 7.5.0) 解法, 执行用时: 680ms, 内存消耗: 18260K, 提交时间: 2023-05-04 21:42:26
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//bwjj,我真的好喜欢你啊,mua~,为了你,我要做445题
const int koishi=2e5+5;
int a[koishi];
complex<double> lazy[koishi<<2],tree[koishi<<2];
void build(int p,int l,int r)
{
lazy[p]=complex<double> (1,0);
if(l==r)
{
tree[p]={cos(a[l]),sin(a[l])};
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
tree[p]=tree[p<<1]+tree[p<<1|1];
}
void pushdown(int p)
{
lazy[p<<1]*=lazy[p],lazy[p<<1|1]*=lazy[p];
tree[p<<1]*=lazy[p],tree[p<<1|1]*=lazy[p];
lazy[p]=complex<double> (1,0);
}
void update(int p,int l,int r,int x,int y,complex<double> w)
{
if(l>y||r<x) return;
if(l>=x&&r<=y)
{
lazy[p]*=w;
tree[p]*=w;
return;
}
pushdown(p);
int mid=(l+r)>>1;
update(p<<1,l,mid,x,y,w),update(p<<1|1,mid+1,r,x,y,w);
tree[p]=tree[p<<1]+tree[p<<1|1];
}
double ask(int p,int l,int r,int x,int y)
{
if(l>y||r<x) return 0;
if(l>=x&&r<=y)
{
return tree[p].imag();
}
pushdown(p);
int mid=(l+r)>>1;
return ask(p<<1,l,mid,x,y)+ask(p<<1|1,mid+1,r,x,y);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,1,n);
int m;
cin>>m;
while(m--)
{
int op,l,r,v;
cin>>op;
if(op==1)
{
cin>>l>>r>>v;
update(1,1,n,l,r,complex<double> (cos(v),sin(v)));
}
if(op==2)
{
cin>>l>>r;
printf("%.1lf\n",ask(1,1,n,l,r));
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 536ms, 内存消耗: 18320K, 提交时间: 2018-08-21 14:46:33
#include <bits/stdc++.h>
using namespace std;
const int maxn=200003;
typedef complex<double> E;
int n,q;
int a[maxn];
E sum[maxn<<2];
E lz[maxn<<2];
void pushup(int u){
sum[u]=sum[2*u]+sum[2*u+1];
}
void pushdown(int u){
lz[2*u]*=lz[u];
sum[2*u]*=lz[u];
lz[2*u+1]*=lz[u];
sum[2*u+1]*=lz[u];
lz[u]=E(1,0);
}
void build(int u,int l,int r){
lz[u]=E(1,0);
if(l==r){
sum[u]=E(cos(a[l]),sin(a[l]));
return;
}
int mid=(l+r)/2;
build(2*u,l,mid);
build(2*u+1,mid+1,r);
pushup(u);
}
void update(int u,int l,int r,int ql,int qr,E x){
if(ql>r||qr<l)return ;
if(ql<=l&&r<=qr){
lz[u]*=x;
sum[u]*=x;
return;
}
int mid=(l+r)/2;
pushdown(u);
update(2*u,l,mid,ql,qr,x);
update(2*u+1,mid+1,r,ql,qr,x);
pushup(u);
}
double query(int u,int l,int r,int ql,int qr){
if(ql>r||qr<l)return 0;
if(ql<=l&&r<=qr){
return sum[u].imag();
}
int mid=(l+r)/2;
pushdown(u);
return query(2*u,l,mid,ql,qr)+query(2*u+1,mid+1,r,ql,qr);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++){
int typ;
scanf("%d",&typ);
if(typ==1){
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
update(1,1,n,l,r,E(cos(x),sin(x)));
}
else {
int l,r;
scanf("%d%d",&l,&r);
printf("%.1f\n",query(1,1,n,l,r));
}
}
}