Today, I will share with you a few topics about the violent modification of simple line segment trees ~hh

1. Section excavation
Luo Gu p4145 flower god travels all over the world

Input format

An integer n in the first row represents the number of numbers in the sequence.

The second line contains n positive integers, representing the number in the number series in the initial state.

An integer m in the third line indicates that there are m operations.

The next m lines are three integers k l r per line.

• k=0 represents the square of each number in [l,r] (rounded down).

• k=1 means the sum of all numbers in the query [l,r].

There may be l>r in the data, so please exchange L and R in this case.

Output format

For query operations, output one answer per line.

Input and output samples

Enter #1 copy

10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

Output #1 copy

19
7
6

Idea: first of all, because I just learned the line segment tree, when I saw the interval modification, I thought it must be to write a lazy, but when I think that opening the square and then adding and then opening the square is not equal, so what should I do? I think the senior mentioned a potential line segment tree. First of all, the setting of lazy is really to optimize our modification operation into logn, But when we look at the square operation, a number (1e12) can be opened to 1 soon. It is meaningless to open it again and again. Therefore, this inspires us to maintain the maximum value of the interval. As long as the maximum value of the interval is 1, we can jump out directly without continuing to open the square, so our complexity comes to n logn* a small constant. The only thing to pay attention to is to open longlong in the starting array.

The code is as follows:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
struct Node{
	int l,r;
	LL sum;
	LL tmax;
}tr[N<<2];
int n,m;
LL w[N];
void pushup(int u)
{
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	tr[u].tmax=max(tr[u<<1].tmax,tr[u<<1|1].tmax);
}
void build(int u,int l,int r)
{
	if(l==r)tr[u]={l,r,w[l],w[l]};
	else
	{
		tr[u]={l,r};
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	} 
}
void modify(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	  if(tr[u].tmax<=1)return;
	  
	if(tr[u].l==tr[u].r)tr[u].sum=tr[u].tmax=sqrt(tr[u].sum);
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid)modify(u<<1,l,r);
		if(r>mid)modify(u<<1|1,l,r);
		pushup(u);
	}
}
LL query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
	int mid=tr[u].l+tr[u].r>>1;
	if(r<=mid)return query(u<<1,l,r);
	else if(l>mid)return query(u<<1|1,l,r);
	else return query(u<<1,l,r)+query(u<<1|1,l,r);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
	cin>>m;
	build(1,1,n);
	while(m--)
	{
		LL k,l,r,d;
		scanf("%lld%lld%lld",&k,&l,&r);
		if(l>r)swap(l,r);
		if(!k)
          modify(1,l,r);
        else
         printf("%lld\n",query(1,l,r));
	}
}

2. Section mold taking
CF438D
 D. The Child and Sequence

Input

The first line of input contains two integer: n, m (1 ≤ n, m ≤ 105). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — initial value of array elements.

Each of the next m lines begins with a number type 

.

• If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n), which correspond the operation 1.
• If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109), which correspond the operation 2.
• If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109), which correspond the operation 3.

Output

For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

Examples

input

Copy

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

output
8
5




Idea: with the foreshadowing of the previous question, this question becomes very naked, mainly because the idea of violent modification and the applicable scene are more important
Here is the code:

 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,m;
int w[N];
struct Node
{
	int l,r;
	LL tmax;
	LL sum;
}tr[4*N];
void pushup(int u)
{
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	tr[u].tmax=max(tr[u<<1].tmax,tr[u<<1|1].tmax);
}
void build(int u,int l,int r)
{
	if(l==r)tr[u]={l,l,w[l],w[l]};
	else 
	{
		tr[u]={l,r};
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
	
}
void modify1(int u,int l,int r,LL p)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	 if(tr[u].tmax<p)return;
	 //Violence to leaf node 
	if(tr[u].l==tr[u].r)
	{
		tr[u].sum%=p;
		tr[u].tmax%=p;
	}
	else 
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid)modify1(u<<1,l,r,p);
		if(r>mid)modify1(u<<1|1,l,r,p);
		pushup(u);
	}
}
void modify2(int u,int x,LL v)
{
	
	if(tr[u].l==x&&tr[u].r==x)tr[u].sum=tr[u].tmax=v;
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid)modify2(u<<1,x,v);
		else modify2(u<<1|1,x,v);
		pushup(u);
	}
}
LL query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
	int mid=tr[u].l+tr[u].r>>1;
	if(r<=mid)return query(u<<1,l,r);
	else if(l>mid)return query(u<<1|1,l,r);
	else  return query(u<<1,l,r)+query(u<<1|1,l,r);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	build(1,1,n);
	while(m--)
	{
		LL k,l,r,c;
		scanf("%lld%lld%lld",&k,&l,&r);
		if(k==1)printf("%lld\n",query(1,l,r));
		else if(k==2)
		{
			scanf("%lld",&c);
			modify1(1,l,r,c);
		}
		else modify2(1,l,r);
	}
	
}