》》點擊進入原題《《

?

?思路：題解很有意思，適合線段樹進階

#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> using namespace std;#define lson l,m,o<<1 #define rson m+1,r,o<<1|1const int maxn = 1e5 + 10; int a[maxn], d1[maxn], d2[maxn]; int tree[maxn << 2], vis[maxn << 2]; int ans, cur;void build(int l, int r, int o){if (l == r){tree[o] = a[l];vis[o] = l;return;}int m = (l + r) >> 1;build(lson);build(rson);tree[o] = max(tree[o << 1], tree[o << 1 | 1]);if (tree[o << 1] >= tree[o << 1 | 1])vis[o] = vis[o << 1];else vis[o] = vis[o << 1 | 1];} void query(int l, int r, int o, int ql, int qr, int k){if (l == r){if (tree[o]>k)cur = min(cur, l);return;}int m = (l + r) >> 1;if (l >= ql&&r <= qr){if (tree[o << 1] > k)query(lson, ql, qr, k);else if (tree[o << 1 | 1] > k)query(rson, ql, qr, k);return;}if (ql <= m)query(lson, ql, qr, k);if (qr > m)query(rson, ql, qr, k); } void query1(int l, int r, int o, int ql, int qr){if (l >= ql&&r <= qr){if (tree[o] > a[cur])cur = vis[o];return;}int m = (l + r) >> 1;if (ql <= m)query1(lson, ql, qr);if (qr > m)query1(rson, ql, qr); } int main(){ios::sync_with_stdio(false);int t; cin >> t;while (t--){int n, m, p, q, Max = 0;cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];if (a[i] > Max)d1[i] = d1[i - 1] + 1, Max = a[i];else d1[i] = d1[i - 1];}build(1, n, 1);for (int i = n; i; i--){cur = n + 1;query(1, n, 1, i, n, a[i]);if (cur > n)cur = 0;d2[i] = d2[cur] + 1;}while (m--){cin >> p >> q;ans = cur = 0;if (p != 1){query1(1, n, 1, 1, p - 1);}ans += d1[cur];if (q > a[cur])ans++;else q = a[cur];cur = n + 1;if (p != n)query(1, n, 1, p + 1, n, q);if (cur <= n)ans += d2[cur];cout << ans << endl;}} }

?

轉載于:https://www.cnblogs.com/zengguoqiang/p/9506598.html

總結

以上是生活随笔為你收集整理的多校1010 Taotao Picks Apples的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。