2 条题解
-
0
分块太好用辣
#include<bits/stdc++.h> #define int long long #define PII pair<int,int> #define ULL unsigned long long #define all(v) v.begin(), v.end() #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; constexpr int N = 1 * 1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f; int n,m; int id[N],a[N],b[N],len,s[N]; int query(int l,int r) { int sid = id[l] , eid = id[r]; int res = -inf; if(sid == eid) { for(int i=l;i<=r;i++) res = max(res,a[i]); return res; } for(int i=l;id[i]==sid;i++) res = max(res,a[i]); for(int i=sid+1;i<eid;i++) res = max(res,s[i]); for(int i=r;id[i]==eid;i--) res = max(res,a[i]); return res; } void solve() { cin >> n >> m; len = sqrt(n); for(int i=1;i<=n;i++) { cin >> a[i]; id[i] = (i-1) / len + 1; s[id[i]] = max(a[i],s[id[i]]); } while (m--) { int l,r; cin >> l >> r; cout << query(l,r) << '\n'; } } signed main() { ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr); int _=1; // cin>>_; while(_--) { solve(); } return 0; } /** * author: Nijika_jia * created: 2024.10.28 13:08:13 */ -
0
NIjika_jia
LV 5
@ 2024-10-25 21:26:23
ST表
#include<bits/stdc++.h> #define ULL unsigned long long #define int long long #define endl '\n' #define debug(a) cout<<#a<<"="<<a<<endl; #define all(v) v.begin(), v.end() #define PII pair<int,int> using namespace std; constexpr int N = 2 *1e5 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f; const int MAXN = 20; int n,q; int w[N]; int f[N][MAXN]; void init() { for(int j=0;j<MAXN;j++) { for(int i=1;i + (1<<(j)) - 1 <=n;i++) { if(!j) f[i][j] = w[i]; else f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } } int query(int l,int r) { int len = r - l + 1; int k = log2(len); return max(f[l][k],f[r-(1<<k)+1][k]); } void solve() { cin >> n >> q; for(int i=1;i<=n;i++) cin >> w[i]; init(); while (q--) { int l,r; cin >> l >> r; cout << query(l,r) << endl; } } signed main() { ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr); int _=1; // cin>>_; while(_--) { solve(); } return 0; } /** * author: Nijika_jia * created: 2024.10.23 10:35:55 */
- 1