#include<bits/stdc++.h> usingnamespace std; #define ll long long constint maxn = 1e5 + 10; typedef pair<int, int> pii; int n, m; int pos[maxn]; ll sum[maxn]; structX { int l, r; int ask; }; boolcmp(X a, X b){ return a.l != b.l ? a.l > b.l:a.ask < b.ask; } vector<X>vc; ll ans[maxn]; intlowbit(int x){ return x & -x; } voidadd(int x){ for (int i = x; i <= n; i += lowbit(i)) { sum[i]++; } } ll query(int r){ ll res = 0; for (int i = r; i > 0; i -= lowbit(i)) { res += sum[i]; } return res; } intmain(){ cin.sync_with_stdio(false); cout.sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++) { int u; cin >> u; pos[u] = i; } for (int i = 1; i <= n; i++) { int tmp = 2 * i; while (tmp <= n) { vc.push_back(X{ min(pos[i],pos[tmp]),max(pos[i],pos[tmp]),0 }); tmp += i; } } for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; vc.push_back(X{ l,r,i }); } sort(vc.begin(), vc.end(), cmp); for (int i = 0; i < vc.size(); i++) { X p = vc[i]; if (p.ask == 0) { add(p.r); } else { ans[p.ask] = query(p.r); } } for (int i = 1; i <= m; i++) { cout << ans[i] << endl; } return0; }
#include<bits/stdc++.h> usingnamespace std; #define ll long long typedef pair<ll, int> pii; constint maxn = 1e6 + 5; char s[maxn], t[maxn]; int n, m, ans; int a[maxn][26]; intmain(){ cin.sync_with_stdio(false); cout.tie(0); cin >> n >> m; cin >> (s + 1) >> (t + 1); for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < 26; j++) { if (s[i + 1] == 'a' + j) a[i][j] = i + 1; else a[i][j] = a[i + 1][j]; } } int pos = 0; bool flg = 0; for (int i = 1; i <= m; i++) { int c = t[i] - 'a'; for (int j = c + 1; j < 26; j++) { if (a[pos][j] == 0)continue; ans = max(ans, i + n - a[pos][j]); } pos = a[pos][c]; if (pos == 0) { flg = 1; break; } } if (!flg&&pos!=n)ans = max(ans, m + n - pos); if (ans == 0)cout << -1 << endl; else cout << ans << endl; return0; }