\u7565<\/p>\n
\u7531\u4e8e\u8fd9\u662f\u4e00\u4e2a\u4e0d\u7528\u7ef4\u62a4\u539f\u6709\u5e8f\u5217\u7684\u64cd\u4f5c\uff0c\u6211\u4eec\u53ef\u4ee5\u8003\u8651\u7ef4\u62a4\u4e00\u4e2aST\u8868\u8fdb\u884cRMQ\u67e5\u8be2\u3002
\n\u8fd9\u4e2aRMQ\u662f\u7528\u6765\u5e72\u4ec0\u4e48\u5462\uff1f
\n\u6839\u636e\u9898\u76ee\u6570\u636e\u8303\u56f4\uff0c\u6211\u4eec\u77e5\u9053\u8fd9\u9053\u9898\u4e0d\u80fd\u5bb9\u5fcd$\\mathcal O(n^2)$\u53ca\u4ee5\u4e0a\u7684\u7b97\u6cd5
\n\u6211\u4eec\u5fc5\u987b\u8981\u5728$\\mathcal O(nlogn)$\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e0b\u5b8c\u6210\u6240\u6709\u7684\u64cd\u4f5c\u3002
\n\u7ef4\u62a4\u4e00\u4e2adp\u6570\u7ec4\uff0c$dp[cur] = dp[first_greater_than_cur] + 1$
\n\u8fd9\u4e2a\u65f6\u5019\u5c31\u9700\u8981\u6211\u4eec\u7528RMQ\u4e86\u3002\u4e8c\u5206$[cur,n]$\uff0c\u627e\u5230\u7b2c\u4e00\u4e2a\u6bd4\u5f53\u524d\u5143\u7d20\u5927\u7684\u5143\u7d20\u7684\u4f4d\u7f6e\uff0c\u8fd9\u65f6dp\u503c\u5c31\u53ef\u4ee5\u52a01.
\n\u8d2a\u5fc3\u9884\u5904\u7406\u539f\u5e8f\u5217\u7684\u9009\u62e9\u60c5\u51b5\u3001\u6bcf\u4e2a\u4f4d\u7f6e\u9009\u62e9\u7684\u957f\u5ea6\u4ee5\u53caprev\u6570\u7ec4\u7528\u4e8e\u7ef4\u62a4\u4e0a\u4e00\u4e2a\u88ab\u9009\u62e9\u7684\u5143\u7d20\u3002
\n\u63a5\u4e0b\u6765\u662f\u67e5\u8be2\u90e8\u5206
\n\u6211\u4eec\u9700\u8981\u5bf9\u67e5\u8be2\u8fdb\u884c\u5206\u7c7b\u8ba8\u8bba\u3002
\n\u67e5\u8be2\u6709\u4ee5\u4e0b\u51e0\u79cd\u60c5\u51b5\uff1a
\n1.\u4fee\u6539\u7684\u5143\u7d20\u662f\u88ab\u9009\u62e9\u7684\u5e8f\u5217\u4e2d\u7684\u5143\u7d20\u3002
\n\u8fd9\u65f6\u5019\u6211\u4eec\u8981\u8003\u8651\u8fd9\u4e2a\u6570\u76f8\u5bf9\u4e8e\u4e0a\u4e00\u4e2a\u6570\u7684\u5927\u5c0f\u7684\u60c5\u51b5
\n\u90a3\u4e48\u8fd9\u65f6\u5019\u51fa\u73b0\u4e00\u4e2a\u7279\u6b8a\u60c5\u51b5\uff0c\u5c31\u662f\u8fd9\u4e2a\u6570\u662f\u7b2c\u4e00\u4e2a\u6570\u3002
\n\u8fd9\u4e2a\u65f6\u5019$ans = 1 + dp[first_element_greater_than_cur]$<\/p>\n
\u82e5\u4e0d\u662f\u7b2c\u4e00\u4e2a\u6570\uff0c\u5219\u662f\u5206\u4e24\u79cd\u60c5\u51b5\u8003\u8651\u3002
\n – 1. \u6bd4\u5f53\u524d\u7684\u6570\u4e0a\u4e00\u4e2a\u6570\u5c0f\u6216\u76f8\u7b49
\n – 2. \u6bd4\u4e0a\u4e00\u4e2a\u6570\u5927<\/p>\n
\u5bf9\u4e8e\u7b2c\u4e00\u79cd\u60c5\u51b5\uff0c$ans = cnt[prev] + dp[first_element_greater_than_prev]$
\n\u800c\u7b2c\u4e8c\u79cd\u60c5\u51b5\u5219\u662f $ans = cnt[p] + dp[first_element_greater_than_cur]$<\/p>\n
2.\u4fee\u6539\u7684\u5143\u7d20\u4e0d\u5728\u88ab\u9009\u62e9\u7684\u5e8f\u5217\u4e2d
\n\u4e5f\u5206\u4e24\u79cd\u60c5\u51b5\u8003\u8651\u3002
\n– 1. \u6bd4\u5f53\u524d\u4f4d\u7f6e\u7684\u4e0a\u4e00\u4e2a\u88ab\u9009\u5143\u7d20\u5c0f
\n \u8fd9\u65f6\u5019\u4fee\u6539\u7684\u6570\u5bf9\u7b54\u6848\u6ca1\u6709\u8d21\u732e\uff0c\u56e0\u6b64\u4e0d\u9700\u8981\u8003\u8651
\n– 2. \u6bd4\u5f53\u524d\u4f4d\u7f6e\u7684\u4e0a\u4e00\u4e2a\u88ab\u9009\u5143\u7d20\u5927
\n \u8fd9\u65f6\u5019\u5219\u662f$ans = cnt[prev] + 1 + dp[first_element_greater_than_cur]$,\u56e0\u4e3a\u8fd9\u4e2a\u5143\u7d20\u5fc5\u9009 + \u4e0a\u4e00\u4e2a\u5143\u7d20\u4ee5\u53ca\u4e4b\u524d\u88ab\u9009\u6570\u7684\u4e2a\u6570 + \u4e0b\u4e00\u4e2a\u7b2c\u4e00\u4e2a\u6bd4\u5f53\u524d\u5143\u7d20\u5927\u7684\u5143\u7d20\u5bf9\u5e94\u7684dp\u503c\u5c31\u662f\u7b54\u6848<\/p>\n
#pragma GCC optimize(\"O3\")\n#include <iostream>\n#include <algorithm>\n#include <vector>\n#include <array>\n#include <cstring>\n#include <queue>\n#include <regex>\n\nusing namespace std;\nusing ll = long long;\nusing lll = __int128;\nusing pii = pair<int,int>;\n\nconst int maxn = 2e5+6;\nint n,m,tot;\nint h[maxn];\nint st[maxn][32-__builtin_clz(maxn)];\nint dp[maxn];\nbool select[maxn];\nint pre[maxn],cnt[maxn];\n\ninline void init_st()\n{\n int l = 31 - __builtin_clz(n);\n for(auto i = 0;i<n;++i)st[i][0] = h[i];\n for(int j = 0;j<l;++j) {\n for(int i = 0;i<(1 + n - (1 << j));++i) {\n st[i][j+1] = max(st[i][j],st[i + (1 << j)][j]);\n }\n }\n}\n\nint rmq(int l,int r)\n{\n int k = 31 - __builtin_clz(r - l + 1);\n return max(st[l][k], st[r - (1 << k) + 1][k]);\n}\n\nint first_greater_than_after(int pos,int val)\n{\n int l = pos + 1,r = n,mid;\n while(l < r) {\n mid = (l + r ) >> 1;\n if (rmq(pos + 1, mid) <= val) l = mid + 1;\n else r = mid;\n }\n return l;\n}\n\nvoid prepare() \n{\n int _cnt = 1;\n dp[n] = 0;\n for(int i = n - 1;i >= 0;--i) {\n int pos = first_greater_than_after(i,h[i]);\n dp[i] = dp[pos] + 1;\n }\n select[0] = true;\n pre[0] = -1;\n cnt[0] = 1;\n int last = 0,prevh = h[0];\n for(int i = 1;i<n;++i) {\n pre[i] = last;\n if (h[i] > prevh) {\n select[i] = true;\n last = i;\n prevh = h[i];\n ++_cnt;\n }\n else {\n select[i] = false;\n }\n cnt[i] = _cnt;\n }\n \/*\n for(int i = 0;i<n;++i)\n {\n cout << \"select[\"<<i<<\"]=\"<<select[i]<<endl;\n }\n *\/\n tot = _cnt;\n}\n\n\nint main()\n{\n ios::sync_with_stdio(false);\n cin.tie(0);\n cout.tie(0);\n int T;\n cin >> T;\n while(T--)\n {\n cin >> n >> m;\n for(int i = 0;i<n;++i) cin >> h[i];\n init_st();\n prepare();\n \/*\n for(int i = 0;i<n;++i)cout << \"dp[\"<<i<<\"]=\"<<dp[i]<<endl;\n for(int i = 0;i<n;++i)cout << \"cnt[\"<<i<<\"]=\"<<cnt[i]<<endl;\n *\/\n for(int i = 0;i<m;++i)\n {\n int p,q;\n cin >> p >> q;\n --p;\n if(select[p])\n {\n if(p == 0)\n {\n \/\/ change first element\n int ans = 1;\n ans += dp[first_greater_than_after(p,q)];\n cout << ans << '\\n';\n }\n else\n {\n \/\/ not first element\n if(h[pre[p]] >= q)\n {\n \/\/change value to smaller and \n \/\/prev high is greater than or equal q\n int ans = cnt[pre[p]];\/\/ans from start to prev\n int pos = first_greater_than_after(p,h[pre[p]]);\n \/\/ first element greater than pos\n cout << ans + dp[pos] << '\\n';\n }\n else\n {\n \/\/change value not smaller or equal than prev\n \/\/check if there exists at least one element is greater than current modify value but smaller than prev value\n int ans = cnt[p];\n int pos = first_greater_than_after(p,q);\n cout << ans + dp[pos] << '\\n';\n }\n }\n }\n else\n {\n \/\/ the element has not been selected\n if(h[pre[p]] >= q)\n {\n \/\/ if prev element is greater or equal than current modify value\n \/\/ it doesn't change the answer.\n cout << tot << '\\n';\n }\n else\n {\n \/\/cout << \"came here\" << endl;\n\n \/\/ q is greater than prev element,may have effected to next element(s)\n \/\/ search first element which greater than q\n int ans = cnt[pre[p]] + 1;\/\/select this value,so plus one\n \/\/cout << ans << endl;\n int pos = first_greater_than_after(p,q);\n \/\/cout << pos << endl;\n cout << ans + dp[pos] << '\\n';\n }\n }\n }\n }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u9898\u610f \u7565 \u9898\u89e3 \u7531\u4e8e\u8fd9\u662f\u4e00\u4e2a\u4e0d\u7528\u7ef4\u62a4\u539f\u6709\u5e8f\u5217\u7684\u64cd\u4f5c\uff0c\u6211\u4eec\u53ef\u4ee5\u8003\u8651\u7ef4\u62a4\u4e00\u4e2aST\u8868\u8fdb\u884cRMQ\u67e5\u8be2\u3002 \u8fd9\u4e2aRMQ\u662f\u7528 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[39,25,51,22],"tags":[24,55],"class_list":["post-434","post","type-post","status-publish","format-standard","hentry","category-c","category-25","category-51","category-22","tag-cpp","tag-55"],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8UC2c-70","jetpack_likes_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/434","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=434"}],"version-history":[{"count":0,"href":"https:\/\/haoyuan.info\/index.php?rest_route=\/wp\/v2\/posts\/434\/revisions"}],"wp:attachment":[{"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=434"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=434"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haoyuan.info\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=434"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}