https://www.cnblogs.com/leoair/articles/15933308.html

//区间最大值 
#include<iostream>
#include<map>
#include<set>
using namespace std;
const int maxn=1E5+10;
int n,k,a[maxn]; 
map<int,int> mp;//因为ai值域1E9了，不能再数组桶排序 
set<int> s;
int main(){
	cin>>n>>k;
	for(int i=0;i<k;i++){
		cin>>a[i];
//		if(mp.find(a)!=mp.end())
		mp[a[i]]++;//可以不管a是否存在，直接这样 
		if(mp[a[i]]==1){
			s.insert(a[i]);
		}else{
			s.erase(a[i]);
		}
	} 
	if(s.empty()){//对起始k窗口输出处理结果，后面窗口内的元素开始进一个出一个 
		cout<<-1<<" ";
	}else{
		cout<<*s.rbegin()<<" ";
	}
	
	for(int i=k;i<n;i++){
		cin>>a[i];
		mp[a[i]]++;//滑动窗口右指针右移
		if(mp[a[i]]==1){ 
			s.insert(a[i]);
		}else{
			s.erase(a[i]);
		}
		
		mp[a[i-k]]--;//滑动窗口左指针右移，别忘记！ 
		if(mp[a[i-k]]==1){
			s.insert(a[i-k]);
		}else{
			s.erase(a[i-k]);
		}
		 
		if(s.empty()){
			cout<<-1<<" ";
		}else{
			cout<<*s.rbegin()<<" ";
		}
	}
	return 0;
} 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1E5+10; 
struct TreeNode{
	int sum;
	int lazy;//懒标记，区间修改如果到每一个叶子节点就太浪费线段树性质了 
}node[4*maxn];
ll n,m,op,x,y,k,a[maxn];
void pushUp(int u){
	node[u].sum=node[u<<1].sum+node[u<<1|1].sum;
}
void build(int u, int l, int r){
	node[u].lazy=0;//初始化懒标记 
	if(l==r){
		node[u].sum=a[l];//注意node[u]是对叶子节点a[l]按二进制分组规律建树求区间和 
		return;
	}
	int mid=l + ((r-l)>>1);
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushUp(u);
}
int query(int u, int l, int r, int x, int y){//查询区间和 
	if(x<=l&&r<=y){//x<=l<=r<=y,[x,y]包含了[l,r] 
		return node[u].sum;
	}//else代表 x>l||r>y
	int mid=l + ((r-l)>>1);
	int res=0;
	if(x<=mid)
		res+=query(u<<1,l,mid, x,y);
	if(y>mid)//y>=mid+1
		res+=query(u<<1|1,mid+1,r, x,y);
	return res;
}
void modify(int u, int l, int r, int x, int y, int k){
	
}
void update(int u,int l,int r,int lazy){
	tr[u].sum +=(r-l+ 1)* lazy;
	tr[u].lazy += lazy; 
}
void pushdown(int u, int l, int r){// 下传结点u的懒标记
	if(tr[u].lazy==0){//判断是否有懒标记需要下传return;
	int mid =(l+r)>> 1;
	update(u<<1，l，mid，tr[u].lazy);//下传到左子树
	update(u<<1|1，mid +1，r，tr[u].lazy);// 下传到右子树
	tr[u].lazy=0;//下传懒标记后，初始化懒标记
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);//0~n-1?
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			modify(1,1,n,x,y,k); 
		}else{
			cin>>x>>y;
			if(x==y)	cout<<-1<<endl;
			else	cout<<query(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}

//这段不知道哪里query不对
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1E5+10; 
struct TreeNode{
	int sum;
	int lazy;//懒标记，区间修改如果到每一个叶子节点就太浪费线段树性质了 
}node[4*maxn];
ll a[maxn];
void pushUp(int u){
	node[u].sum=node[u<<1].sum+node[u<<1|1].sum;
}
void build(int u,int l,int r){
	if(l==r){
		node[u].sum=a[l];
		return;
	}
	int mid=l+((r-l)>>1);
	build(u<<1, l, mid);
	build(u<<1|1, mid+1, r);
	pushUp(u);
}
int query(int u,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return node[u].sum;
	}
	int res=0, mid=l+((r-l)>>1);
	if(x<=mid){
		res+=query(u<<1, l, mid, x, y);
	}
	if(mid>y){
		res+=query(u<<1|1, mid+1, r, x, y);
	}
	return res;
}
int main(){
	ll n,m,op,x,y,k;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);//0~n-1?
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
//			modify(1,1,n,x,y,k); 
		}else{
			cin>>x>>y;
			if(x==y)	cout<<-1<<endl;
			else	cout<<query(1,1,n,x,y)<<endl;
		}
	}
	return 0;
}