22-07-16 personal training match 3 competition experience

notes ： Read what the senior wrote blog Just found that you can use the directory , It seems convenient for me , Take the time to fill in the directory of the previous blog .

The game went well ahead , The back was caught by three cows （doge） 

I'm so happy to make up the question today , I passed a line segment tree （ Although it is still very stiff ）

The intranet address is still posted

Catalog

N: The pain of Antarctica snails

---

 A: violence map

B: routine BFS

C: Thinking greedy + bucket

D: Water problem

E: Complex simulation （ Simulation is not needed ）

F: Water problem

G: Two points ( How can I forget sort   wa+8)

J: Water problem

K: Thinking simulation

L: thinking

M: Sign in prime ( But I didn't see the question clearly and rushed over )

N: Line segment tree board variant

N: The pain of Antarctica snails

Questions that cannot be found

  Ideas ： Because ask and sum , So we must let ai*ki Maintain as a whole to add , Otherwise, if you separate , Interval fetching ai*ki And i The value obtained when maintaining an interval is incorrect . Because the value at this time should be al*kl+a(l+1)*k(l+2)+.......+ar*kr Instead of being maintained now （al+a(l+1)+...ar)*(kl+k(l+1)+...kr), Because separate maintenance will lead to a or k As a whole , instead of a*k.

So maintenance ai*ki, Define a... In the structure alone sum, We found that , When a Section +w When ,sum In fact, the change is +(k*w）,k The same goes for interval addition , So as long as pushdown Add an extra pair in sum Just pass it on , See the code for details .

#include <bits/stdc++.h>
//#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
struct tree{
	int a,k,sum;
}tr[4*N];
int num[N],laza[4*N],lazk[4*N];
void builda(int p,int l,int r){
    if (l==r){
        tr[p].a=num[l];
        return;
    }
    int mid=l+r>>1;
    builda(2*p,l,mid);
    builda(2*p+1,mid+1,r);
    tr[p].a=tr[2*p].a+tr[2*p+1].a;
}
void buildk(int p,int l,int r){
    if (l==r){
        tr[p].k=num[l];
        tr[p].sum=tr[p].k*tr[p].a;
        return;
    }
    int mid=l+r>>1;
    buildk(2*p,l,mid);
    buildk(2*p+1,mid+1,r);
    tr[p].k=tr[2*p].k+tr[2*p+1].k;
    tr[p].sum=tr[2*p].sum+tr[2*p+1].sum;
}
void pushdown(int p,int l,int r){
    int mid=l+r>>1;
    laza[2*p]+=laza[p];
    laza[2*p+1]+=laza[p];
    tr[2*p].sum+=laza[p]*tr[2*p].k;
    tr[2*p+1].sum+=laza[p]*tr[2*p+1].k;
    tr[2*p].a+=laza[p]*(mid-l+1);
    tr[2*p+1].a+=laza[p]*(r-mid);
    lazk[2*p]+=lazk[p];
    lazk[2*p+1]+=lazk[p];
    tr[2*p].sum+=lazk[p]*tr[2*p].a;
    tr[2*p+1].sum+=lazk[p]*tr[2*p+1].a;
    tr[2*p].k+=lazk[p]*(mid-l+1);
    tr[2*p+1].k+=lazk[p]*(r-mid);
    lazk[p]=0;
    laza[p]=0;
}
int query(int p,int l,int r,int x,int y){
	if (x<=l&&r<=y){
		return tr[p].sum;
	}
    pushdown(p,l,r);
	int mid=l+r>>1,ans=0;
	if (x<=mid)ans+=query(2*p,l,mid,x,y);
	if (mid<y)ans+=query(2*p+1,mid+1,r,x,y);
	return ans;
}
void updatea(int p,int l,int r,int x,int y,int w){
    if (x<=l&&r<=y){
        tr[p].sum+=w*tr[p].k;
        tr[p].a+=w*(r-l+1);
        laza[p]+=w;
        return;
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    if (x<=mid)updatea(2*p,l,mid,x,y,w);
    if (mid<y)updatea(2*p+1,mid+1,r,x,y,w);
    tr[p].a=tr[2*p].a+tr[2*p+1].a;
    tr[p].sum=tr[2*p].sum+tr[2*p+1].sum;
}
void updatek(int p,int l,int r,int x,int y,int w){
    if (x<=l&&r<=y){
    	tr[p].sum+=w*tr[p].a;
        tr[p].k+=w*(r-l+1);
        lazk[p]+=w;
        return;
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    if (x<=mid)updatek(2*p,l,mid,x,y,w);
    if (mid<y)updatek(2*p+1,mid+1,r,x,y,w);
    tr[p].k=tr[2*p].k+tr[2*p+1].k;
    tr[p].sum=tr[2*p].sum+tr[2*p+1].sum;
}
void work(){
	int n,q;
	cin>>n>>q;
	rep(i,1,n){
		cin>>num[i];
	}
	builda(1,1,n);
	rep(i,1,n){
		cin>>num[i];
	}
	buildk(1,1,n);
	int op,l,r,w;
	rep(i,1,q){
		cin>>op;
		if (op==1){
			cin>>l>>r>>w;
			updatea(1,1,n,l,r,w);
		}
		else if (op==2){
			cin>>l>>r>>w;
			updatek(1,1,n,l,r,w);
		}
		else{
			cin>>l>>r;
			cout<<query(1,1,n,l,r)<<endl;
		}
	}
}
signed main(){
	CIO;
	work();
	return 0;
}