{"id":584,"date":"2024-11-17T18:29:06","date_gmt":"2024-11-17T10:29:06","guid":{"rendered":"https:\/\/womeifei.cn\/?p=584"},"modified":"2024-11-18T20:59:39","modified_gmt":"2024-11-18T12:59:39","slug":"%e5%ad%97%e8%8a%82%e8%b7%b3%e5%8a%a8%e5%89%8d%e7%ab%af%e6%a0%a1%e6%8b%9b%e7%ae%97%e6%b3%95-%e7%94%a8%e6%88%b7%e5%96%9c%e5%a5%bd","status":"publish","type":"post","link":"https:\/\/womeifei.cn\/index.php\/2024\/11\/17\/%e5%ad%97%e8%8a%82%e8%b7%b3%e5%8a%a8%e5%89%8d%e7%ab%af%e6%a0%a1%e6%8b%9b%e7%ae%97%e6%b3%95-%e7%94%a8%e6%88%b7%e5%96%9c%e5%a5%bd\/","title":{"rendered":"\u5b57\u8282\u8df3\u52a8\u524d\u7aef\u6821\u62db\u7b97\u6cd5-\u7528\u6237\u559c\u597d"},"content":{"rendered":"\n
\"\"<\/div><\/figure>\n\n\n\n

\u8fd9\u4e2a\u9898\u5176\u5b9e\u60f3\u8981\u5b9e\u73b0\u5e76\u4e0d\u590d\u6742 \u6211\u53ea\u82b1\u4e86\u51e0\u5206\u949f\u5c31\u641e\u6e05\u695a\u4e86\u6b65\u9aa4<\/p>\n\n\n\n

\u7528\u4e00\u4e2a\u6570\u7ec4\u6807\u8bb0\u5bf9\u5e94\u7684\u7528\u6237\u559c\u597d\u503c \u6700\u540e\u904d\u5386 \u82e5\u4e0e\u6307\u5b9a\u559c\u597d\u503c\u76f8\u7b49 res++<\/p>\n\n\n\n

#include<iostream>\nusing namespace std;\nint a[300001];\nint main(){\n    int n;\n    cin>>n;\n    for(int i=1;i<=n;i++){\n        cin>>a[i];\n    }\n    int q;\n    cin>>q;\n    while(q--){\n        int res=0;\n        int l,r,k;\n        cin>>l>>r>>k;\n        for(int j=l;j<=r;j++){\n            if(a[j]==k)res++;\n        }\n        cout<<res<<endl;\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u8fd9\u4e48\u7b80\u5355? \u6211\u611f\u5230\u5b57\u8282\u8fd9\u6837\u7684\u5927\u5382\u4e5f\u6ca1\u90a3\u4e48\u9065\u8fdc…… <\/p>\n\n\n\n
       \u4f46\u8fd9\u6837\u505a\u662f\u8d85\u65f6\u7684 \u56e0\u4e3a\u5728\u67e5\u627e\u65f6\u4ece\u5934\u5230\u5c3e\u904d\u5386\u8017\u8d39\u4e86\u5927\u91cf\u65f6\u95f4 \u6240\u4ee5\u6211\u4eec\u5fc5\u987b\u8fdb\u884c\u4f18\u5316<\/p>\n\n\n\n
\u4f18\u5316\u601d\u8def\u4e00—\u524d\u7f00\u548c<\/p>\n\n\n\n
       \u521b\u5efa\u4e00\u4e2a\u4e8c\u7ef4\u7684\u524d\u7f00\u548c\u6570\u7ec4 prefix[k][i]<\/code>\uff0c\u8868\u793a\u5728\u524d i<\/code> \u4e2a\u5143\u7d20\u4e2d\uff0c\u503c\u4e3a k<\/code> \u7684\u5143\u7d20\u51fa\u73b0\u7684\u6b21\u6570<\/strong>\u3002\u8fd9\u6837\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u67e5\u8be2 [l, r, k]<\/code>\uff0c\u53ef\u4ee5\u901a\u8fc7\u8ba1\u7b97 prefix[k][r] - prefix[k][l-1]<\/code> \u6765\u5feb\u901f\u5f97\u5230\u7b54\u6848<\/p>\n\n\n\n
    \u8fd9\u79cd\u65b9\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(n)<\/code> \u6765\u6784\u5efa\u524d\u7f00\u548c<\/strong>\uff0c\u67e5\u8be2\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(1)<\/code><\/strong><\/p>\n\n\n\n
\u4ee3\u7801\u5982\u4e0b:<\/p>\n\n\n\n
#include<iostream>\n#include<unordered_map>\nusing namespace std;\nint a[300001];\nunordered_map<int, int> prefix[300001];  \nint main() {\n    int n;\n    cin >> n;\n    \n    for (int i = 1; i <= n; i++) {\n        cin >> a[i];\n    }\n    \n    for (int i = 1; i <= n; i++) {\n        for (int j = 1; j <= i; j++) {\n            prefix[i][a[j]]++;\n        }\n    }\n    int q;\n    cin >> q;\n    \n    while (q--) {\n        int l, r, k;\n        cin >> l >> r >> k;  \n        int res = prefix[r][k] - prefix[l-1][k];\n        cout << res << endl;\n    }\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
\u4f18\u5316\u601d\u8def\u4e8c—\u54c8\u5e0c\u8868+\u4e8c\u5206\u67e5\u627e<\/p>\n\n\n\n
       \u8fd9\u4e2a\u601d\u8def\u548c\u521a\u521a\u7684\u524d\u7f00\u548c\u5dee\u4e0d\u591a \u9884\u5904\u7406\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n) \u67e5\u8be2\u7684\u590d\u6742\u5ea6\u4e3aO(log k)<\/strong><\/p>\n\n\n\n
       \u8bf4\u5b9e\u8bdd\u6211\u5bf9\u8fd9\u4e2aC++\u81ea\u5e26\u7684unordered_map\u5f88\u4e0d\u719f\u6089 \u800c\u8fd9\u51e0\u5929\u505a\u5230\u7684\u7b97\u6cd5\u9898\u90fd\u6216\u591a\u6216\u5c11\u7528\u5230\u4e86\u8fd9\u4e2a\u4e1c\u897f \u6240\u4ee5\u6211\u5e94\u7528\u8d77\u6765\u5f88\u96be\u53d7 \u540e\u9762\u6211\u4f1a\u4e13\u95e8\u4ecb\u7ecd\u4e00\u4e0bunordered_map\u7684\u4f7f\u7528 <\/p>\n\n\n\n
\u4ee3\u7801\u8d34\u5728\u4e0b\u9762<\/p>\n\n\n\n
#include <iostream>\n#include <algorithm>\n#include <unordered_map>\nusing namespace std;\n\nint main(){\n\tint n; cin >> n;\n\tvector<int> like(n+1, 0);\n\tfor (int i = 1; i <= n; ++i)    cin >> like[i];\n\tunordered_map<int, vector<int>> m;\n\tfor (int i = 1; i <= n; ++i)          m[like[i]].push_back(i);\n\tint q; \n\tcin >> q;\n\tfor (int i = 0; i < q; ++i){\n\t\tint l, r, num;\n\t\tcin >> l >> r >> num;\n\t\tif (m.count(num) == 0){\n\t\t\tcout << 0 << endl;\n\t\t\tcontinue;\n\t\t}\n\t\tauto l_it = lower_bound(m[num].begin(), m[num].end(), l);\n\t\tauto r_it = upper_bound(m[num].begin(), m[num].end(), r);\n\t\tcout << r_it - l_it << endl;\n\t}\n\treturn 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u4e2a\u9898\u5176\u5b9e\u60f3\u8981\u5b9e\u73b0\u5e76\u4e0d\u590d\u6742 \u6211\u53ea\u82b1\u4e86\u51e0\u5206\u949f\u5c31\u641e\u6e05\u695a\u4e86\u6b65\u9aa4 \u7528\u4e00\u4e2a\u6570\u7ec4\u6807\u8bb0\u5bf9\u5e94\u7684\u7528\u6237\u559c\u597d\u503c \u6700\u540e\u904d\u5386 \u82e5\u4e0e\u6307\u5b9a\u559c […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,7],"tags":[],"class_list":["post-584","post","type-post","status-publish","format-standard","hentry","category-4","category-7"],"_links":{"self":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/584","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/comments?post=584"}],"version-history":[{"count":4,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/584\/revisions"}],"predecessor-version":[{"id":604,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/584\/revisions\/604"}],"wp:attachment":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/media?parent=584"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/categories?post=584"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/tags?post=584"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}