分块模板

#include <iostream> #include <cstdio> #include <stack> #include <sstream> #include <vector> #include <map> #include <cstring> #include <deque> #include <cmath> #include <iomanip> #include <queue> #include <algorithm> #include <set> #define mid ((l + r) >> 1) #define Lson rt << 1, l , mid #define Rson rt << 1|1, mid + 1, r #define ms(a,al) memset(a,al,sizeof(a)) #define log2(a) log(a)/log(2) #define _for(i,a,b) for( int i = (a); i < (b); ++i) #define _rep(i,a,b) for( int i = (a); i <= (b); ++i) #define for_(i,a,b) for( int i = (a); i >= (b); -- i) #define rep_(i,a,b) for( int i = (a); i > (b); -- i) #define lowbit(x) ((-x) & x) #define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define INF 0x3f3f3f3f #define hash Hash #define next Next #define count Count #define pb push_back #define f first #define s second using namespace std; const int N = 2e5 + 10, mod = 1e9 + 7; const double eps = 1e-10; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> PII; template<typename T> void read(T &x) { x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } template<typename T, typename... Args> void read(T &first, Args& ... args) { read(first); read(args...); } int belong[N],l[N],r[N],block,num; //每个点在哪个块,每个块的左右边界,每个块的长度，块的个数； int Max[N];//不同的题目不同 int a[N]; int n,m; inline void build() { memset(Max,0,sizeof(Max)); block = sqrt(n); num = n/block; if(n%block) num++; for(int i = 1; i <= num; ++ i) l[i] = (i - 1) * block + 1, r[i] = i * block; r[num] = n; for(int i = 1; i <= n; ++ i) belong[i] = (i - 1)/block+1; for(int i = 1; i <= num; ++ i) for(int j = l[i]; j <= r[i]; ++ j) Max[i] = max(Max[i],a[j]); } inline void update(int x, int y) { a[x] = y; Max[belong[x]] = max(a[x],Max[belong[x]]); } inline int query(int x, int y) { int ans = 0; if(belong[x] == belong[y]) { for(int i = x; i <= y; ++ i) ans = max(ans,a[i]); return ans; } for(int i = x; i <= r[belong[x]]; ++ i) ans = max(ans,a[i]); for(int i = belong[x]+1 ; i < belong[y]; ++ i) ans = max(ans,Max[i]); for(int i = l[belong[y]]; i <= y; ++ i) ans = max(ans,a[i]); return ans; } int main() { while(cin >> n >> m) { for(int i = 1; i <= n; ++ i) read(a[i]); build(); while(m --) { char op; int x, y; cin >> op >> x >> y; if(op == 'Q') cout << query(x,y) << endl; else update(x,y); } } return 0; }