Topic link

Train of thought

Obviously with a line tree, but how do you maintain the modification operation?

Let ts[p]ts[p]ts[p] ts[p] be the sum of the sin⁡\sinsin values of the interval [L,R][L,R][L,R] maintained by PPP nodes in the line segment tree, Have ts [p] = ∑ I = LRsin ⁡ (a [I]) ts = \ sum \ [p] limits_} {I = L ^ R \ sin [p], a [I]) ts = I = ∑ L Rsin (a [I]), given interval with a digital VVV, into the original type


∑ i = L R sin ⁡ ( a [ i ] + v ) = ∑ i = L R [ sin ⁡ ( a [ i ] ) cos ⁡ ( v ) + sin ⁡ ( v ) cos ⁡ ( a [ i ] ) ] = cos ⁡ ( v ) ∑ i = L R sin ⁡ ( a [ i ] ) + sin ⁡ ( v ) ∑ i = L R cos ⁡ ( a [ i ] ) \begin{aligned} &\sum\limits_{i=L}^R\sin(a[i]+v)\\ =&\sum\limits_{i=L}^R[\sin(a[i])\cos(v)+\sin(v)\cos(a[i])]\\ =&\cos(v)\sum\limits_{i=L}^R\sin(a[i])+\sin(v)\sum\limits_{i=L}^R\cos(a[i]) \end{aligned}

So it is possible to maintain the intervals sin⁡,cos⁡\sin,\cossin,cos and, and maintain a mark indicating how much the interval is added. The child node is maintained with the marked values of sin⁡,cos⁡\sin,\cossin,cos.

code

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define en puts("")
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void OP(a) {}
void op(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
    int__ =0; _ =0;
    char ch=getchar(a);while(!isdigit(ch))
    {
        if(ch==The '-') __ =1;
        ch=getchar(a); }while(isdigit(ch))
    {
        _=_*10+ch- 48;
        ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
    if(_ <0)
    {
        putchar(The '-'); _ = - _; }if(_ > =10)
       Out(_ /10);
    putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void OP(T _, T2... oth)
{
	Out(_).putchar('\n');
	OP(oth...) ; }template <typename T, typename. T2>inline void op(T _, T2... oth)
{
	Out(_).putchar(' ');
	op(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
const ll N=2E5+10;
ll n,q;
ll a[N],tag[4*N];
db sinx,cosx;
db ts[4*N],tc[4*N];
void update(ll p)
{
	ts[p]=ts[lc]+ts[rc];
	tc[p]=tc[lc]+tc[rc];
}
void build(ll p,ll l,ll r)
{
	if(l==r)
	{
		ts[p]=sin(a[l]);
		tc[p]=cos(a[l]);
		return;
	}
	ll mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	update(p);
}
void flag(ll p,ll val,db sx,db cx)
{
	db si=ts[p],co=tc[p];
	ts[p]=(cx*si+sx*co);
	tc[p]=(cx*co-sx*si);
	tag[p]+=val;
}
void push_down(ll p)
{
	db tmps=sin(tag[p]),tmpc=cos(tag[p]);
	flag(lc,tag[p],tmps,tmpc);
	flag(rc,tag[p],tmps,tmpc);
	tag[p]=0;
}
void modify(ll p,ll l,ll r,ll al,ll ar,ll val)
{
	if(al<=l && ar>=r)
	{
		flag(p,val,sinx,cosx);
		return;
	}
	ll mid=(l+r)>>1;
	if(tag[p])
		push_down(p);
	if(al<=mid)
		modify(lc,l,mid,al,ar,val);
	if(ar>mid)
		modify(rc,mid+1,r,al,ar,val);
	update(p);
}
db query(ll p,ll l,ll r,ll al,ll ar)
{
	if(al<=l && ar>=r)
		return ts[p];
	ll mid=(l+r)>>1;
	db ret=0;
	if(tag[p])
		push_down(p);
	if(al<=mid)
		ret+=query(lc,l,mid,al,ar);
	if(ar>mid)
		ret+=query(rc,mid+1,r,al,ar);
	return ret;
}
int main(a)
{
	read(n);
	rep(i,1,n)
		read(a[i]);
	read(q);
	build(1.1,n);
	ll ty,l,r,x;
	while(q--)
	{
		read(ty,l,r);
		if(ty==1)
		{
			read(x);
			sinx=sin(x);
			cosx=cos(x);
			modify(1.1,n,l,r,x);
		}
		else
		{
			printf("%.1lf\n".query(1.1,n,l,r)); }}}Copy the code