个人常用模板
2020-03-29
8 min read
**常规模板 **
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define zy -2147382637
#define bql 2147483647
#define ll long long
#define ull unsigned long long
#define ld long double
#define il inline
#define sz(x) x.size()
#define maxn 100010
#define rp(i, l, r) for (int i = l; i <= r; i++)
#define rb(i, r, l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll min(ll a,ll b){if(a<b)return a;else return b;}
ll lowbit(ll x){return x&(-x);}
ll prime(ll x){
if(x<=1)return false;
for(int i=2;i<=int(sqrt(x));i++){
if(x%i==0)return false;
}return true;
}bool cmp(ll a,ll b){return a>b;}
ll gcd(ll a,ll b){ll r;while(b>0){r=a%b;a=b;b=r;}return a;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline int readint() {
int f=1,x=0; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
return f*x;
}
inline ll readll() {
ll f=1,x=0; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
return f*x;
}
void fl(string name){
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
const int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1},
dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int main(){
}
/* stuff to remember
* int overflow, array bounds
* special cases (n=1? n=0?)
* do something instead of nothing and stay organized
* USE STATIC ARRAYS
* DEFINING ARRAYS BEFORE main()
* DO NOT DEFINE ARRAYS IN main()
* USE INT INSTEAD OF LL,NOTICE THE MLE
*/
线段树模板
带区间覆盖、区间加、区间求和、区间最大值、区间最小值
#define MAXN 200010
struct SegmentTree{
ll l,r,sum,lazy,maxv,minv;
}tree[MAXN<<1];
ll n,m,a[MAXN];
void push_up(ll p){
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
tree[p].maxv=max(tree[p<<1].maxv,tree[p<<1|1].maxv);
tree[p].minv=min(tree[p<<1].minv,tree[p<<1|1].minv);
}
void update(ll p){
if(tree[p].lazy){
tree[p<<1].sum+=(tree[p<<1].r-tree[p<<1].l+1)*tree[p].lazy;
tree[p<<1].lazy+=tree[p].lazy;
tree[p<<1|1].sum+=(tree[p<<1|1].r-tree[p<<1|1].l+1)*tree[p].lazy;
tree[p<<1|1].lazy+=tree[p].lazy;
tree[p<<1].maxv+=tree[p].lazy;
tree[p<<1|1].maxv+=tree[p].lazy;
tree[p<<1].minv+=tree[p].lazy;
tree[p<<1|1].minv+=tree[p].lazy;
tree[p].lazy=0;
}
}
void build(ll p,ll l,ll r){
tree[p].l=l;tree[p].r=r;
if(l==r){
tree[p].sum=a[l];
tree[p].maxv=a[l];
tree[p].minv=a[l];
return;
}
ll mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p);
}
void modify_cover(ll p,ll l,ll r,ll k){
if(l<=tree[p].l&&tree[p].r<=r){
tree[p].sum=(tree[p].r-tree[p].l+1)*k;
tree[p].lazy=k;
tree[p].maxv=k;
tree[p].minv=k;
return;
}
update(p);
ll mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid)modify_cover(p<<1,l,r,k);
if(r>mid)modify_cover(p<<1|1,l,r,k);
push_up(p);
}
void modify_add(ll p,ll l,ll r,ll k){
if(l<=tree[p].l&&tree[p].r<=r){
tree[p].sum+=(tree[p].r-tree[p].l+1)*k;
tree[p].lazy+=k;
tree[p].maxv+=k;
tree[p].minv+=k;
return;
}
update(p);
ll mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid)modify_add(p<<1,l,r,k);
if(r>mid)modify_add(p<<1|1,l,r,k);
push_up(p);
}
ll sum(ll p,ll l,ll r){
if(l<=tree[p].l&&tree[p].r<=r){
return tree[p].sum;
}
update(p);
ll mid=(tree[p].l+tree[p].r)>>1,ans=0;
if(l<=mid)ans+=sum(p<<1,l,r);
if(r>mid)ans+=sum(p<<1|1,l,r);
return ans;
}
ll maxx(ll p,ll l,ll r){
if(l<=tree[p].l&&tree[p].r<=r){
return tree[p].maxv;
}
update(p);
ll mid=(tree[p].l+tree[p].r)>>1,ans=zy;
if(l<=mid)ans=max(ans,maxx(p<<1,l,r));
if(r>mid)ans=max(ans,maxx(p<<1|1,l,r));
return ans;
}
ll minn(ll p,ll l,ll r){
if(l<=tree[p].l&&tree[p].r<=r){
return tree[p].minv;
}
update(p);
ll mid=(tree[p].l+tree[p].r)>>1,ans=bql;
if(l<=mid)ans=min(ans,minn(p<<1,l,r));
if(r>mid)ans=min(ans,minn(p<<1|1,l,r));
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(m--){
int opt;
cin>>opt;
if(opt==1){
ll x,y,k;
cin>>x>>y>>k;
modify_cover(1,x,y,k);
}
if(opt==2){
ll x,y,k;
cin>>x>>y>>k;
modify_add(1,x,y,k);
}
if(opt==3){
ll x,y;
cin>>x>>y;
cout<<sum(1,x,y)<<endl;
}
if(opt==4){
ll x,y;
cin>>x>>y;
cout<<maxx(1,x,y)<<endl;
}
if(opt==5){
ll x,y;
cin>>x>>y;
cout<<minn(1,x,y)<<endl;
}
}
return 0;
}