无题

大常数 $O(log n)\approx$ 小常数 $O(\sqrt n)$
🤔
🤓👆

#include <iostream>
#include <cstdio>
#include <cmath>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
using namespace std;
char *p1, *p2, buf[(1 << 25)];
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 25), stdin), p1 == p2)? EOF : *p1++)
int read(){
	char c = getchar();
	int x = 0, f = 1;
	while(!isdigit(c)){
		if(c == '-') f = -f;
		c = getchar();
	}
	while(isdigit(c)){
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x * f;
}
void _write(int n){//快写
	if(n == 0) return;
	_write(n / 10);
	putchar(n % 10 + '0');
}
void write(int n){//快写，增加了输出0和负数并附带换行
	if(n < 0) putchar('-'), n = -n;
	_write(n), putchar('\n');
}
int a[1000005];
int blocks[1005];
int len, tmp, l, r, idx, val;
void modify(int idx, int val){
	a[idx] = val;
	int iidx = idx / len;
	blocks[iidx] = 0;
	for(int i = idx / len * len; i < idx / len * len + len; i++){
		blocks[iidx] = max(blocks[iidx], a[i]);
	}
}
int query(int l, int r){
	int mx = 0;
	if(r - l < len){
		for(int i = l; i <= r; i++){
			mx = max(mx, a[i]);
		}
		return mx;
	}
	for(int i = l / len + 1; i < r / len; i++){//整块 
		mx = max(mx, blocks[i]);
	}
	for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块 
		mx = max(mx, a[i]);
	}
	for(int i = max(r / len * len, l + 1); i <= r; i++){
		mx = max(mx, a[i]);
	}
	return mx;
}
int get(int l, int r, int val){
	if(r - l < len){
		for(int i = l; i <= r; i++){
			if(a[i] >= val) return i;
		}
		return -1;
	}
	for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块 
		if(a[i] >= val) return i;
	}
	for(int i = l / len + 1; i < r / len; i++){//整块 
		if(blocks[i] >= val){
			for(int j = i * len; j < i * len + len; j++){
				if(a[j] >= val) return j;
			}
		}
	}
	for(int i = max(r / len * len, l + 1); i <= r; i++){
		if(a[i] >= val) return i;
	}
	return -1;
}
signed main(){
	int n = read(), m = read(); 
	len = sqrt(n);
	for(int i = 1; i <= n; i++){
		a[i] = read();
		blocks[i / len] = max(blocks[i / len], a[i]);
	}
	while(m--){
		tmp = read();
		if(tmp == 1){
			idx = read(), val = read();
			modify(idx, val);
		}else if(tmp == 2){
			l = read(), r = read();
			swap(a[l], a[r]);
			modify(l, a[l]), modify(r, a[r]); 
		}else if(tmp == 3){
			l = read(), r = read();
			write(query(l, r));
		}else{
			val = read(), l = read(), r = read();
			int ans = get(l, r, val);
			write(ans == 0x3f3f3f3f ? -1 : ans);
		}
	}

	return 0;
}