本蒟蒻在此跪谢大佬

线段树 马蜂氢气

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
template <class T>
inline void read(T &res){
	char c;bool f=0;
	while(!isdigit(c=getchar())) if(c=='-') f=1;
	res=(c^48);
	while(isdigit(c=getchar())) res=(res<<1)+(res<<3)+(c^48);
	if(f) res=~res+1;
}
int n,m,x,l,r,val,op;
int a[N],ans;
bool vis[N];
struct E{
	int u,num;
	bool F;
	E(){}
	E(const int &_u,const int &_num,const bool &_F):u(_u),num(_num),F(_F){}
	bool operator < (const E &a) const {
		return num==a.num?u>a.u:num<a.num;
	}
};
E Max(E a,E b){
	if(a.F==1) return a;
	if(b.F==1) return b;
	return max(a,b);
}
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
struct Segtree{
	struct Tree{
		E max;
		int tag_add;
	}t[N*4];
	void build(int u,int l,int r){
		if(l==r) {t[u].max=E(l,a[l],0); return ;}
		build(ls,l,mid);
		build(rs,mid+1,r);
		t[u].max=max(t[ls].max,t[rs].max);
	}
	void up(int u,int l,int r,int x) {t[u].max.num+=x; t[u].tag_add+=x;}
	void push_down(int u,int l,int r){
		if(t[u].tag_add){
			up(ls,l,mid,t[u].tag_add);
			up(rs,mid+1,r,t[u].tag_add);
			t[u].tag_add=0;
		}
	}
	void modify(int u,int l,int r,int ql,int qr,int x){
		if(l>qr||r<ql) return ;
		if(ql<=l&&r<=qr) return up(u,l,r,x);
		push_down(u,l,r);
		modify(ls,l,mid,ql,qr,x);
		modify(rs,mid+1,r,ql,qr,x);
		t[u].max=max(t[ls].max,t[rs].max);
	}
	void modify_R(int u,int l,int r,int x,int k){
		if(l>x||r<x) return ;
		if(l==r) {t[u].max.num=k-t[u].max.num; return ;}
		push_down(u,l,r);
		modify_R(ls,l,mid,x,k);
		modify_R(rs,mid+1,r,x,k);
		t[u].max=max(t[ls].max,t[rs].max);
	}
	void modify_zero(int u,int l,int r,int x){
		if(l>x||r<x) return ;
		if(l==r) {t[u].max.num=0; if(t[u].max.F==1) t[u].max.F=0; return ;}
		push_down(u,l,r);
		modify_zero(ls,l,mid,x);
		modify_zero(rs,mid+1,r,x);
		t[u].max=max(t[ls].max,t[rs].max);
	}
	void modify_Flag(int u,int l,int r,int x){
		if(l>x||r<x) return ;
		if(l==r) {t[u].max.F=1; return ;}
		push_down(u,l,r);
		modify_Flag(ls,l,mid,x);
		modify_Flag(rs,mid+1,r,x);
		t[u].max=max(t[ls].max,t[rs].max);
	}
	E query(int u,int l,int r,int ql,int qr){
		if(l>qr||r<ql) return E(n+1,INT_MIN,0);
		if(l==r) return t[u].max;
		push_down(u,l,r);
		return Max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
	}
}seg;
int main(){
	read(n);read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	seg.build(1,1,n);
	for(int i=1;i<=m;i++){
		read(op);
		if(op==1){
			read(x);read(val);
			seg.modify_R(1,1,n,x,val);
			seg.modify_Flag(1,1,n,x);
		}
		else if(op==2){
			read(l);read(r);
			E tp=seg.query(1,1,n,l,r);
			ans+=tp.num;
			cout<<tp.num<<"\n";
			seg.modify_zero(1,1,n,tp.u);
		}
		else{
			read(l);read(r);read(val);
			seg.modify(1,1,n,l,r,val);
		}
	}
	if(ans<10000) printf("QAQ");
	else if(ans<10000000) printf("Sakura");
	else printf("ice");
	return 0;
}