单点修改直接改下去,区间修改懒标记
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; }
线段树和数状数组经典例题 文章被收录于专栏
线段树和数状数组经典例题