Line tree from entry to advanced

What is a line tree?? How to write line tree??

If you ask this question the day before the test, you will lose the first prize; if you are still hitting the first prize of popularization group, this blog will waste 5-20 minutes of your life.

It is obvious from the above two sentences that the data structure of line segment tree is a transition from Mengxin to formal OI players, a very important algorithm, and also a more difficult algorithm for Mengxin. I have to say that I learned this algorithm about 5 times before I had the courage to write this blog.

However, for the official OI players, line tree is not an algorithm, it should be a tool. She can change the time complexity of O(N) into o (logN) for the modification and maintenance of interval (or line segment).

Needless to say, this blog will be divided into four parts:

Part one: introduction of the concept of line tree

Part two: simple (no pushdown) line segment tree

Part three: interval + / - modification and query

Part four: interval multiplication and division modification and query

Sum up

Part I introduction of concept

Line tree is a kind of binary tree, that is, for a line, we will use a binary tree to express. For example, a line segment with a length of 4 can be expressed as follows:

 

What does that mean? If you want to represent the sum of line segments, the weight of the top root node represents the sum of line segments 1 to 4. The two sons of the root represent the sum of 1-2 and 3-4 in this line segment respectively. and so on.

Then we can also get a property: the weight of node i = the weight of her left son + the weight of her right son. Because the sum of 1-4 is the sum of 1-2 and + 2-3.

According to this idea, we can build a tree. Let's set a structure tree. tree[i].l and tree[i].r represent the left and right subscripts of the line segment represented by this point, and tree[i].sum represents the line segment and the node.

We know that, a binary tree, her left son and right son number are her * 2 and her * 2 + 1 respectively

Then according to the properties just now, we get the formula: tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; then we can build a line tree! The code is as follows:

inline void build(int i,int l,int r){//Recursive tree building
    tree[i].l=l;tree[i].r=r;
    if(l==r){//If this node is a leaf node
        tree[i].sum=input[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);//Construct left subtree and right subtree respectively
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//The nature we just discoveredreturn ;
}

Well, this is the construction of line segment tree. You may ask why you need to open multiple times of memory to store a line segment. This is because we haven't let this large array do some practical work, so what is practical? Let's go to the next one (when you understand this one)

The second simple (no pushdown) segment tree

1. Single point modification, interval query

In fact, the beginning of this chapter is the real line tree. What should we use the line trunk? The answer is to maintain a line segment (or interval), for example, if you want to find the sum of 4-67 elements in a 1-100 interval, what would you do? The simple way is for (I = 4; I < = 67; I + +) sum+=a[i], which is good, but too slow.

Let's think of a new method. First, we need to think of a better drawing data, for example, an interval with a length of 4, which is 1, 2, 3 and 4 respectively. We want to find the sum of items 1 to 3. According to the previous part, we want to build a line segment tree, in which point weight (that is, red) represents and:

 

Then we ask for the sum of 1-3. We start from the root node and find that her left son 1-2 intersects with her answer 1-3. Then we run to the left son.

Then, we find that the interval 1-2 is completely included in the interval 1-3 of the answer, so we return her value 3.

We go back to the 1-4 range and find that her right son's 3-4 range and answer range 1-3 intersect, so we go to the 3-4 range

In the 3-4 range, we find that she is not completely included in the answer range 1-3, but we find that her left son's 3-3 range and 1-3 range intersect again, so long as she goes to the 3-3 range

When you reach the 3-3 range, you find that it is completely contained by the answer range, and you return her value 3 until the beginning

3 = 6 of 3 + 1 ~ 2 of 3 ~ 3 interval, we know that the sum of 1 ~ 3 interval is 6

Some people may say that you are crazy. I can work out 1 + 2 + 3 = 6 with that foot. Why is it so troublesome?!

Because these are only a few. If there are a million, the time will be greatly increased.

Let's summarize the query method of line tree:

1. If this interval is completely included in the target interval, return the value of this interval directly

2. If there is intersection between the left son of this interval and the target interval, then search for the left son

3. If there is an intersection between the right son of this range and the target range, search for the right son

When it is written into code, it will be like this:

inline int search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)//If this interval is completely included in the target interval, return the value of this interval directly
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;//If this interval has nothing to do with the target interval, return 0
    int s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);//If the left son of this interval intersects the target interval, search for the left son
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);//If the right son of this interval and the target interval intersect again, then search for the right son
    return s;
}

The conditions of those if must be seen clearly. It's better to recite them to prevent brain pumping and pushing in the examination room.

Then, how can we modify the single point of this interval? In fact, this is a lot simpler. You need to add k to the dis of the interval.

So you can start from the root node to see whether the dis is on the left or the right, where to run,

When returning, all the passing points will be updated according to the principle of tree[i].sum=tree[i*2].sum+tree[i*2+1].sum

If I don't understand, I'd better draw a picture, where dark blue is the path to go, light blue is the path to return, and the red + mark is to add this point to the value.

Turn this process into code, just like this:

inline void add(int i,int dis,int k){
    if(tree[i].l==tree[i].r){//If it is a leaf node, then it is found
        tree[i].sum+=k;
        return ;
    }
    if(dis<=tree[i*2].r)  add(i*2,dis,k);//Where to run
    else  add(i*2+1,dis,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//Return to update
    return ;
}

 

2. Interval modification, single point query

For interval modification and single point query, our idea is: if we add k to this interval, it is equivalent to applying a mark of k to this interval, and then when we do single point query, we can add up the marks along the road from up to down the runway.

The way to label an interval is similar to the way to find the above interval. The principle is still those three, but the first one: if the interval is completely included in the target interval, directly return the value of the interval to if the interval is completely included in the target interval, say that the interval is marked with k

The specific method is very similar. Here is the code:

 

inline void add(int i,int l,int r,int k){
    if(tree[i].l>=l && tree[i].r<=r){//If the interval is completely included in the target interval, say the interval marker k
        tree[i].sum+=k;
        return ;
    }
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
}

 

Then it's a single point query. It's a better understanding. It's where the dis goes. Just add all the price tags on the path:

void search(int i,int dis){
    ans+=tree[i].num;//All the way together
    if(tree[i].l==tree[i].r)
        return ;
    if(dis<=tree[i*2].r)
        search(i*2,dis);
    if(dis>=tree[i*2+1].l)
        search(i*2+1,dis);
}

Unconsciously, the second chapter is over. Such a simple (forgive me for using this word) line tree can not only sum, but also find the minimum and maximum value of the interval, and can also dye the interval.

But! Such a line tree does not show her charm, because the interval sum, tree array is less than her a big Changshu. The best of the two ranges, ST's amazing O (n) query can also blow her up. Why is that? Because the charm of the line tree hasn't been shown yet, her most beautiful place: pushdown hasn't been shown in the world. If you have a good understanding of this chapter and can write out the tree array templates 1 and 2 on Luogu without looking at the blog, please go to the next one.

 

The third advanced line segment tree

Interval modification and interval query, you may think that it's good to add the two modules in the previous chapter together, and then you will find that you are very wrong.

Because if you add 1-3 + 1 to 1-4, it's equivalent to labeling nodes 1-2 and 3. But if you query 2-4, you will find that you add 2 nodes without labels and 3-4 nodes without labels. The result is certainly wrong.

So what should we do? At this time, the function of pushdown is shown.

You will think that when we only need to query, if the two nodes we want to query are in the range 1-2, then we can push down the + 1 marked by the range 1-2 so that we can add them smoothly.
How to record this mark? We need to record a lazy tag, lazytage, to record this interval

During interval modification, we shall follow the following principles:

1. If the current interval is completely covered in the target interval, sum+k*(tree[i].r-tree[i].l+1)

2. If it is not completely covered, the lazy flag will be passed down first

3. If there is intersection between the left son of this interval and the target interval, then search for the left son

4. If there is an intersection between the right son of this range and the target range, search for the right son

 

Then, when querying, just pass down the lazy mark. The following illustration is as follows:

As shown in the figure, intervals 1-4 are 1, 2, 3 and 4 respectively. We need to add 1-3 intervals + 1. Because the 1 ~ 2 interval is completely covered, we can use the same principle as the purple lazytage+1,3 interval

Note that after we finish processing these, we still need to follow the principle of tree[i].sum=tree[i*2].sum+tree[i*2+1].sum. The code is as follows:

void add(int i,int l,int r,int k)
{
    if(tree[i].r<=r && tree[i].l>=l)//If the current interval is completely covered in the target interval, the sum+k*(tree[i].r-tree[i].l+1)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;//Record lazytage
        return ;
    }
    push_down(i);//Downward transmission
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}

One of the pushdown s is to reset your lazytage to zero, add it to your son, and add k*(r-l+1) to your son

void push_down(int i)
{
    if(tree[i].lz!=0)
    {
        tree[i*2].lz+=tree[i].lz;//Left and right sons plus their father's lz
        tree[i*2+1].lz+=tree[i].lz;
        init mid=(tree[i].l+tree[i].r)/2;
        tree[i*2].data+=tree[i].lz*(mid-tree[i*2].l+1);//Sum left and right separately
        tree[i*2+1].data+=tree[i].lz*(tree[i*2+1].r-mid);
        tree[i].lz=0;//Father lz to zero
    }
    return ;
}

When querying, it is almost the same as that in the previous chapter, that is to say, you need to add pushdown like modification. Here, use the graph to simulate it. We want to query the sum of 2-4 intervals. This is the situation before the query. All the purple ones represent the lazytage

Then, when we find the interval 1 ~ 2, we find that this interval is not completely included in the target interval, so we push down and lazytage down, and let sum of each interval add (r-l) * lazytage.

Then find the 2-2 interval and find that it is completely contained, so go back to 3, then search to the 3-4 interval and find that it is completely contained, then go back to 8 directly, and finally 3 + 8 = 11 is the answer

Here is the code implementation:

inline int search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;
    push_down(i);
    int s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);
    return s;
}

Well, here, we have learned to use the line tree for interval addition and subtraction. You can complete the line tree template 1 of Luogu

 

The fourth multiplication (root sign) line tree

1. Multiplication line tree

If the line tree only has multiplication, add lazytage directly to become multiplication, and then tree[i].sum*=k will be fine. But if we add and multiply, it's not the same.

When the lazy page subscript is passed, we need to consider whether to add and multiply first or to multiply and add first. We just need to do this with lazytage.

lazytage can be divided into two types, plz of addition and mlz of multiplication.

mlz is very simple to handle. When you pull down, you can just * your father's. what about adding?

We need to add the original plz * father's mlz to the father's plz

 

inline void pushdown(long long i){//Note that this level of data must be long long
    long long k1=tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;//
    tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
    tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
    tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
    tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
    tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
    tree[i].plz=0;
    tree[i].mlz=1;
    return ;
}

 

Then the addition and subtraction functions are the same. When maintaining the lazytage, the addition mark must remember to multiply and add.

It's worth mentioning that when calculating * 2, we must change it to I < < 1, which can solve a lot of problems. We also need to open long long. In addition, when I hand in the problem with inline in front of the function, because I'm stuck without inline, it's too late.

2. Root line tree

In fact, the root sign line tree is the same as the division line tree. At first glance, they feel that they can directly use lazytage to mark the number of exceptions, but in fact, there will be precision problems.

The division of c + + is round down, obviously, (a+b)/k! =a/k+b/k (in the case of rounding down), and root sign, it is obvious that root sign (a) + root sign (b)! = root sign (a+b), so what?

The first idea is violence. For every interval l~r that needs to be changed, every point in the interval should be divided separately. But in this way, the time complexity will be slower than that of large violence (because of multiple constants). So how to optimize?

For each interval, we maintain its maximum and minimum values, and then if the maximum root number of this interval is the same as the minimum root number, it means that the overall root number of this interval will not produce errors, so we modify it directly (the same as division)

Among them, lazytage regards division as subtraction, and records the subtraction value of each element in this interval.

The following is the modification process of the root line segment tree:

 

inline void Sqrt(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r && (tree[i].minn-(long long)sqrt(tree[i].minn))==(tree[i].maxx-(long long)sqrt(tree[i].maxx))){//If the maximum value and the minimum value of this interval are the same
        long long u=tree[i].minn-(long long)sqrt(tree[i].minn);//To calculate the subtraction of each element in the interval
        tree[i].lz+=u;
        tree[i].sum-=(tree[i].r-tree[i].l+1)*u;
        tree[i].minn-=u;
        tree[i].maxx-=u;
            //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
        return ;
    }
    if(tree[i].r<l || tree[i].l>r)  return ;
    push_down(i);
    if(tree[i*2].r>=l)  Sqrt(i*2,l,r);
    if(tree[i*2+1].l<=r)  Sqrt(i*2+1,l,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);//Maintenance Max and min
    tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
    //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
    return ;
}

 

Then there is no change in pushdown, just remember tree[i].minn, tree[i].maxx and - lazytage.

Template title and code:

Finally, we give several template questions, and then paste the code:

Single point modification, interval query: Luogu tree array template 1

 

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define INF 10000009
#define MOD 10000007
#define LL long long
#define in(a) a=read()
#define REP(i,k,n) for(long long i=k;i<=n;i++)
#define DREP(i,k,n) for(long long i=k;i>=n;i--)
#define cl(a) memset(a,0,sizeof(a))
inline long long read(){
    long long x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
inline void out(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
long long n,m,p;
long long input[MAXN];
struct node{
    long long l,r;
    long long sum,mlz,plz;
}tree[4*MAXN];
inline void build(long long i,long long l,long long r){
    tree[i].l=l;
    tree[i].r=r;
    tree[i].mlz=1;
    if(l==r){
        tree[i].sum=input[l]%p;
        return ;
    }
    long long mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline void pushdown(long long i){
    long long k1=tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;
    tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
    tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
    tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
    tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
    tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
    tree[i].plz=0;
    tree[i].mlz=1;
    return ;
}
inline void mul(long long i,long long l,long long r,long long k){
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum=(tree[i].sum*k)%p;
        tree[i].mlz=(tree[i].mlz*k)%p;
        tree[i].plz=(tree[i].plz*k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  mul(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)  mul(i<<1|1,l,r,k);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline void add(long long i,long long l,long long r,long long k){
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum+=((tree[i].r-tree[i].l+1)*k)%p;
        tree[i].plz=(tree[i].plz+k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  add(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)  add(i<<1|1,l,r,k);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline long long search(long long i,long long l,long long r){
    if(tree[i].r<l || tree[i].l>r)  return 0;
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    pushdown(i);
    long long sum=0;
    if(tree[i<<1].r>=l)  sum+=search(i<<1,l,r)%p;
    if(tree[i<<1|1].l<=r)  sum+=search(i<<1|1,l,r)%p;
    return sum%p;
}
int main(){
    in(n);    in(m);in(p);
    REP(i,1,n)  in(input[i]);
    build(1,1,n); 

    REP(i,1,m){
        long long fl,a,b,c;
        in(fl);
        if(fl==1){
            in(a);in(b);in(c);
            c%=p;
            mul(1,a,b,c);
        }
        if(fl==2){
            in(a);in(b);in(c);
            c%=p;
            add(1,a,b,c);
        }
        if(fl==3){
            in(a);in(b);
            printf("%lld\n",search(1,a,b));
        }
    }
    return 0;
}
/*
5 4 1000
1 2 3 4 5
3 1 5
2 1 5 1
1 1 5 2

3 1 5
*/

Interval modification, single point query: Valley tree array template 2

 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int n,m;
int ans;
int input[500010];
struct node
{
    int left,right;
    int num;
}tree[2000010];
void build(int left,int right,int index)
{
    tree[index].num=0;
    tree[index].left=left;
    tree[index].right=right;
       if(left==right)
        return ;
    int mid=(right+left)/2;
    build(left,mid,index*2);
    build(mid+1,right,index*2+1);
}
void pls(int index,int l,int r,int k)
{
    if(tree[index].left>=l && tree[index].right<=r)
    {
        tree[index].num+=k;
        return ;
    }
    if(tree[index*2].right>=l)
       pls(index*2,l,r,k);
    if(tree[index*2+1].left<=r)
       pls(index*2+1,l,r,k);
}
void search(int index,int dis)
{
    ans+=tree[index].num;
    if(tree[index].left==tree[index].right)
        return ;
    if(dis<=tree[index*2].right)
        search(index*2,dis);
    if(dis>=tree[index*2+1].left)
        search(index*2+1,dis);
}
int main()
{
    int n,m;
    cin>>n>>m;
    build(1,n,1);
    for(int i=1;i<=n;i++)
        scanf("%d",&input[i]);
    for(int i=1;i<=m;i++)
    {
        int a;
        scanf("%d",&a);
        if(a==1)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            pls(1,x,y,z);
        }
        if(a==2)
        {
            ans=0;
            int x;
            scanf("%d",&x);
            search(1,x);
            printf("%d\n",ans+input[x]);
        }
    }
}

Interval addition, Luogu section tree template 1

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init long long
using namespace std;
init n,m;
struct node
{
    init l,r,data;
    init lt;    
}tree[1000010];
init arr[1000010];
void build(init l,init r,init index,init arr[])
{
    tree[index].lt=0;
    tree[index].l=l;
    tree[index].r=r;
    if(l==r)
    {
        tree[index].data=arr[l];
        return ;
    }
    init mid=(l+r)/2;
    build(l,mid,index*2,arr);
    build(mid+1,r,index*2+1,arr);
    tree[index].data=tree[index*2].data+tree[index*2+1].data;
    return ;
}
void push_down(init index)
{
    if(tree[index].lt!=0)
    {
        tree[index*2].lt+=tree[index].lt;
        tree[index*2+1].lt+=tree[index].lt;
        init mid=(tree[index].l+tree[index].r)/2;
        tree[index*2].data+=tree[index].lt*(mid-tree[index*2].l+1);
        tree[index*2+1].data+=tree[index].lt*(tree[index*2+1].r-mid);
        tree[index].lt=0;
    }
    return ;
}
void up_data(init index,init l,init r,init k)
{
    if(tree[index].r<=r && tree[index].l>=l)
    {
        tree[index].data+=k*(tree[index].r-tree[index].l+1);
        tree[index].lt+=k;
        return ;
    }
    push_down(index);
    if(tree[index*2].r>=l)
        up_data(index*2,l,r,k);
    if(tree[index*2+1].l<=r)
        up_data(index*2+1,l,r,k);
    tree[index].data=tree[index*2].data+tree[index*2+1].data;
    return ;
}
init search(init index,init l,init r)
{
    if(tree[index].l>=l && tree[index].r<=r)
        return tree[index].data;
    push_down(index);
    init num=0;
    if(tree[index*2].r>=l)
        num+=search(index*2,l,r);
    if(tree[index*2+1].l<=r)
        num+=search(index*2+1,l,r);
    return num;
}
int main()
{
    cin>>n>>m;
    for(init i=1;i<=n;i++)
        cin>>arr[i];
    build(1,n,1,arr);
    for(init i=1;i<=m;i++)
    {
        init f;
        cin>>f;
        if(f==1)
        {
            init a,b,c;
            cin>>a>>b>>c;
            up_data(1,a,b,c);
        }
        if(f==2)
        {
            init a,b;
            cin>>a>>b;
            printf("%lld\n",search(1,a,b));
        }
    }
}

Interval multiplication: Luogu section tree template 2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define INF 10000009
#define MOD 10000007
#define LL long long
#define in(a) a=read()
#define REP(i,k,n) for(long long i=k;i<=n;i++)
#define DREP(i,k,n) for(long long i=k;i>=n;i--)
#define cl(a) memset(a,0,sizeof(a))
inline long long read(){
    long long x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
inline void out(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) out(x/10);
    putchar(x%10+'0');
}
long long n,m,p;
long long input[MAXN];
struct node{
    long long l,r;
    long long sum,mlz,plz;
}tree[4*MAXN];
inline void build(long long i,long long l,long long r){
    tree[i].l=l;
    tree[i].r=r;
    tree[i].mlz=1;
    if(l==r){
        tree[i].sum=input[l]%p;
        return ;
    }
    long long mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline void pushdown(long long i){
    long long k1=tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;
    tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
    tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
    tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
    tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
    tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
    tree[i].plz=0;
    tree[i].mlz=1;
    return ;
}
inline void mul(long long i,long long l,long long r,long long k){
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum=(tree[i].sum*k)%p;
        tree[i].mlz=(tree[i].mlz*k)%p;
        tree[i].plz=(tree[i].plz*k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  mul(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)  mul(i<<1|1,l,r,k);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline void add(long long i,long long l,long long r,long long k){
    if(tree[i].r<l || tree[i].l>r)  return ;
    if(tree[i].l>=l && tree[i].r<=r){
        tree[i].sum+=((tree[i].r-tree[i].l+1)*k)%p;
        tree[i].plz=(tree[i].plz+k)%p;
        return ;
    }
    pushdown(i);
    if(tree[i<<1].r>=l)  add(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)  add(i<<1|1,l,r,k);
    tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
    return ;
}
inline long long search(long long i,long long l,long long r){
    if(tree[i].r<l || tree[i].l>r)  return 0;
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    pushdown(i);
    long long sum=0;
    if(tree[i<<1].r>=l)  sum+=search(i<<1,l,r)%p;
    if(tree[i<<1|1].l<=r)  sum+=search(i<<1|1,l,r)%p;
    return sum%p;
}
int main(){
    in(n);    in(m);in(p);
    REP(i,1,n)  in(input[i]);
    build(1,1,n); 

    REP(i,1,m){
        long long fl,a,b,c;
        in(fl);
        if(fl==1){
            in(a);in(b);in(c);
            c%=p;
            mul(1,a,b,c);
        }
        if(fl==2){
            in(a);in(b);in(c);
            c%=p;
            add(1,a,b,c);
        }
        if(fl==3){
            in(a);in(b);
            printf("%lld\n",search(1,a,b));
        }
    }
    return 0;
}
/*
5 4 1000
1 2 3 4 5
3 1 5
2 1 5 1
1 1 5 2

3 1 5
*/

Interval root, bzoj3211

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 1000010
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define in(a) a=read()
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')
          f=-1;
    for(;isdigit(ch);ch=getchar())
        x=x*10+ch-'0';
    return x*f;
}
struct node{
    int l,r;
    long long lz,sum,maxx,minn;
}tree[MAXN<<2];
int n,m,input[MAXN];
inline void build(int i,int l,int r){
    tree[i].l=l;tree[i].r=r;
    if(l==r){
        tree[i].sum=tree[i].minn=tree[i].maxx=input[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
    tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
    return ;
}
inline void push_down(int i){
    if(!tree[i].lz)  return ;
    long long k=tree[i].lz;
    tree[i*2].lz+=k;
    tree[i*2+1].lz+=k;
    tree[i*2].sum-=(tree[i*2].r-tree[i*2].l+1)*k;
    tree[i*2+1].sum-=(tree[i*2+1].r-tree[i*2+1].l+1)*k;
    tree[i*2].minn-=k;
    tree[i*2+1].minn-=k;
    tree[i*2].maxx-=k;
    tree[i*2+1].maxx-=k;
    tree[i].lz=0;
    return ;
}
inline void Sqrt(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r && (tree[i].minn-(long long)sqrt(tree[i].minn))==(tree[i].maxx-(long long)sqrt(tree[i].maxx))){
        long long u=tree[i].minn-(long long)sqrt(tree[i].minn);
        tree[i].lz+=u;
        tree[i].sum-=(tree[i].r-tree[i].l+1)*u;
        tree[i].minn-=u;
        tree[i].maxx-=u;
            //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
        return ;
    }
    if(tree[i].r<l || tree[i].l>r)  return ;
    push_down(i);
    if(tree[i*2].r>=l)  Sqrt(i*2,l,r);
    if(tree[i*2+1].l<=r)  Sqrt(i*2+1,l,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
    tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
    //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
    return ;
}
inline long long search(int i,int l,int r){
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;
    push_down(i);
    long long s=0;
    if(tree[i*2].r>=l)  s+=search(i*2,l,r);
    if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);
    return s;
}
int main(){
    in(n);
    REP(i,1,n)  in(input[i]);
    build(1,1,n);
    in(m);
    int a,b,c;
    REP(i,1,m){
        in(a);in(b);in(c);
        if(a==1)
            printf("%lld\n",search(1,b,c));
        if(a==2){
            Sqrt(1,b,c);
            //for(int i=1;i<=7;i++)
            //    cout<<tree[i].sum<<" ";
           // cout<<endl;
        }
    }
}

OI has a long way to go, and there is no end to learning. I wish the line trees will accompany you through half your life, and you will still be young when you come back.

Tags: less

Posted on Sat, 11 Apr 2020 22:10:58 -0700 by discombobulator