{"id":14,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-09-23-%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-09-23-%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-09-23-%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84\/","title":{"rendered":"2020-09-23 \u6811\u72b6\u6570\u7ec4"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2586&pid=3<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

We define B(x) as the number of digit 1 in the binary representation of x. For example, B(7) =B((111) 2 ) = 3, B(8) = B((1000) 2 ) = 1, B(9) = B((1001) 2 ) = 2.
We define F(x) = min{y j (y > x)\u2227(B(y)\u2264B(x))}. For example, F(4) = 8, F(5) = 6, F(6) = 8.
Zayin has a forest (a set of trees), whose nodes are numbered from 1 to n. For each node (e.g. node x),if F(x) is not greater than n, then the father of node x is F(x), else, node x is the root of a tree.
We use A [ i ] to denote the number of apples on the node i. Initially, all the A [ i ] (1\u2264i\u2264n) are equal to zero. In order to make his girlfriend happy, Zayin is going to perform magic on the tree. The magic consists of two types of operations:<\/p>\n

    \n
  1. Add x v : For every ancestor of node x (including itself), put v more apples on it. In other words, for every node (e.g. node y) on the path between node x and the root of its tree, let A[y] = A[y] + v.<\/li>\n
  2. Sum L R : Count the total number of apples on the nodes whose index is between L and R. In other words, you need to calculate .\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/li>\n<\/ol>\n
    <\/a>\u8f93\u5165<\/h5>\n

    The first line contains two integers n and m (1\u2264n\u22641018 , 1\u2264m\u2264105 ), where n is the number of nodes and m is the number of operations.
    The next m lines describe the m operations in order. Each line contains three integers. The first of them is op. If op = 1, then the next two integers will be x and v, representing an Add operation. If op = 2, then the next two integers will be L and R, representing a Sum operation. (1\u2264x\u2264n, 1\u2264v\u2264109 , 1\u2264L\u2264R\u2264n)<\/p>\n

    <\/a>\u8f93\u51fa<\/h5>\n

    For each Sum operation, output one line including one number, denoting the corresponding result.<\/p>\n

    <\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
    8 6\n1 1 1\n1 3 2\n1 5 3\n1 7 4\n2 1 5\n2 4 8\n<\/code><\/pre>\n
    <\/a>\u6837\u4f8b\u8f93\u51fa<\/h6>\n
    10\n23\n<\/code><\/pre>\n
    \u6811\u72b6\u6570\u7ec4<\/p>\n
    #pragma<\/span> GCC optimize(3)<\/span>\n#pragma<\/span> GCC optimize(\"Ofast\",\"uroll-loops\",\"omit-frame-pointer\",\"inline\")<\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nll n;<\/span>\nunordered_map<<\/span>ll,<\/span>ll><\/span>w;<\/span>\nvoid<\/span> add<\/span>(<\/span>ll k,<\/span>ll m)<\/span>\n{<\/span>\n    for<\/span>(<\/span>ll d=<\/span>m,<\/span>i=<\/span>k;<\/span>i<=<\/span>n;<\/span>i+<\/span>=<\/span>i&<\/span>(<\/span>-<\/span>i)<\/span>,<\/span>d+<\/span>=<\/span>m)<\/span>\n        w[<\/span>i]<\/span>+<\/span>=<\/span>d;<\/span>\n}<\/span>\nll query<\/span>(<\/span>ll n)<\/span>\n{<\/span>\n    ll sum=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>n;<\/span>i;<\/span>i-<\/span>=<\/span>i&<\/span>(<\/span>-<\/span>i)<\/span>)<\/span>\n        if<\/span>(<\/span>w.<\/span>count<\/span>(<\/span>i)<\/span>)<\/span>\n            sum+<\/span>=<\/span>w[<\/span>i]<\/span>;<\/span>\n    return<\/span> sum;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    std::<\/span>ios::<\/span>sync_with_stdio<\/span>(<\/span>false<\/span>)<\/span>;<\/span>\n    std::<\/span>cin.<\/span>tie<\/span>(<\/span>0<\/span>)<\/span>;<\/span>\n    int<\/span> k;<\/span>\n    cin>><\/span>n>><\/span>k;<\/span>\n    ll a,<\/span>b,<\/span>c;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>k;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        cin>><\/span>a>><\/span>b>><\/span>c;<\/span>\n        if<\/span>(<\/span>a==<\/span>1<\/span>)<\/span>\n        {<\/span>\n            add<\/span>(<\/span>b,<\/span>c)<\/span>;<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            printf<\/span>(<\/span>\"%lldn\"<\/span>,<\/span>-<\/span>query<\/span>(<\/span>b-<\/span>1<\/span>)<\/span>+<\/span>query<\/span>(<\/span>c)<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-14","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/14","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=14"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/14\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=14"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=14"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=14"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}