单点修改直接改下去,区间修改懒标记
sin(a+w)=sina* cosw - cosa* sinw
cos(a+w)=cosa* cosw - sina* sinw
线段树做题方式:
先判断是否是线段树(边改边查,区间修改...)
再思考tr[N]维护什么
若单点修改,则无懒标记
区间修改,ly[N]为待操作数(再思考待操作数是什么)
注意:变量在操作后会改变值,不能乘当前的变量,要乘原来的
#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define low(x) x&(-x)
int const N=2e5+7;
int n,m,az[N];
double trs[N<<2],trc[N<<2];
double ly[N<<2];
double a,b,c,d;
void bulid(int p,int l,int r){
if(l==r) {
trs[p]=sin(az[l]),trc[p]=cos(az[l]);
return ;
}
int mid=(l+r)>>1;
bulid(p*2,l,mid);
bulid(p*2+1,mid+1,r);
trs[p]=trs[p*2]+trs[p*2+1];
trc[p]=trc[p*2]+trc[p*2+1];
}
void pushdown(int p){
ly[p*2]+=ly[p];ly[p*2+1]+=ly[p];
a=trs[p*2];b=trs[p*2+1];c=trc[p*2];d=trc[p*2+1];
trs[p*2]=a*cos(ly[p])+c*sin(ly[p]);
trs[p*2+1]=b*cos(ly[p])+d*sin(ly[p]);
trc[p*2]=c*cos(ly[p])-sin(ly[p])*a;
trc[p*2+1]=cos(ly[p])*d-sin(ly[p])*b;
ly[p]=0;
}
void add(int p,int l,int r,int x,int y,int w){
if(x<=l&&r<=y){
ly[p]+=w;
a=trs[p];b=trc[p];
trs[p]=a*cos(w)+b*sin(w);
trc[p]=b*cos(w)-a*sin(w);
return ;
}
if(ly[p]) pushdown(p);
int mid=(l+r) >> 1;
if(x<=mid) add(p*2,l,mid,x,y,w);
if(y>=mid+1) add(p*2+1,mid+1,r,x,y,w);
trs[p]=trs[p*2]+trs[p*2+1];
trc[p]=trc[p*2]+trc[p*2+1];
}
double ask(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) return trs[p];
if(ly[p]) pushdown(p);
double res=0;
int mid=(l+r) >> 1;
if(x<=mid) res+=ask(p*2,l,mid,x,y);
if(y>=mid+1) res+=ask(p*2+1,mid+1,r,x,y);
return res;
}
int main(){
cin >> n;
for(int i=1;i<=n;++i) cin >> az[i];
bulid(1,1,n);
cin >> m;
int op,l,r,w;
double z=0;
while(m--){
cin >> op;
if(op==1){
cin >> l >> r >> w;
add(1,1,n,l,r,w);
}
else{
cin >> l >> r;
z=ask(1,1,n,l,r);
printf("%.1lf\n",z);
}
}
return 0;
}线段树和数状数组经典例题 文章被收录于专栏
线段树和数状数组经典例题