{"id":12,"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-10-04-%e7%ba%bf%e6%ae%b5%e6%a0%91%e6%89%ab%e6%8f%8f%e7%ba%bf\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-10-04-%e7%ba%bf%e6%ae%b5%e6%a0%91%e6%89%ab%e6%8f%8f%e7%ba%bf","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-10-04-%e7%ba%bf%e6%ae%b5%e6%a0%91%e6%89%ab%e6%8f%8f%e7%ba%bf\/","title":{"rendered":"2020-10-04 \u7ebf\u6bb5\u6811+\u626b\u63cf\u7ebf"},"content":{"rendered":"

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

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

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

Consider a square map with N \u00d7 N cells. We indicate the coordinate of a cell by (i, j), where 1 \u2264 i, j \u2264 N . Each cell has a color either white or black. The color of each cell is initialized to white. The map supports the operation
flip([xlow , xhigh], [ylow , yhigh]), which flips the color of each cell in the rectangle [xlow , xhigh] \u00d7 [ylow , yhigh]. Given
a sequence of flip operations, our problem is to count the number of black cells in the final map. We illustrate this in the following example. Figure (a) shows the initial map. Next, we call flip([2, 4], [1, 3]) and obtain Figure (b). Then, we call flip([1, 5], [3, 5]) and obtain Figure \u00a9. This map contains 18 black cells.
\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n

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

The first line contains the number of test cases T (T < 10). Each test case begins with a line containing two integers N and K (1 < N, K < 10000), where N is the parameter of the map size and K is the number of flip operations. Each subsequent line corresponds to a flip operation, with four integers: xlow , xhigh, ylow , yhigh.<\/p>\n

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

For each test case, output the answer in a line.<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h6>\n
1   \n5 2  \n2 4 1 3\n1 5 3 5\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h6>\n
18\n<\/code><\/pre>\n
\u7ebf\u6bb5\u6811+\u626b\u63cf\u7ebf<\/p>\n
#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nstruct<\/span> node\n{<\/span>\n    int<\/span> h,<\/span>a,<\/span>b,<\/span>num;<\/span>\n}<\/span>;<\/span>\nint<\/span> mark[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> sum[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nnode edge[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nbool<\/span> cmp<\/span>(<\/span>node a,<\/span>node b)<\/span>\n{<\/span>\n    if<\/span>(<\/span>a.<\/span>h==<\/span>b.<\/span>h)<\/span>\n        return<\/span> a.<\/span>num><\/span>b.<\/span>num;<\/span>\n    else<\/span>\n        return<\/span> a.<\/span>h<<\/span>b.<\/span>h;<\/span>\n}<\/span>\nint<\/span> nodeupdate<\/span>(<\/span>int<\/span> root,<\/span>int<\/span> l,<\/span>int<\/span> r,<\/span>ll num)<\/span>\n{<\/span>\n    mark[<\/span>root]<\/span>^<\/span>=<\/span>1<\/span>;<\/span>\n    sum[<\/span>root]<\/span>=<\/span>r-<\/span>l+<\/span>1<\/span>-<\/span>sum[<\/span>root]<\/span>;<\/span>\n}<\/span>\nint<\/span> pushdown<\/span>(<\/span>int<\/span> root,<\/span>int<\/span> l,<\/span>int<\/span> r)<\/span>\n{<\/span>\n    if<\/span>(<\/span>mark[<\/span>root]<\/span>==<\/span>0<\/span>)<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    int<\/span> mid=<\/span>(<\/span>l+<\/span>r)<\/span>\/<\/span>2<\/span>;<\/span>\n    nodeupdate<\/span>(<\/span>2<\/span>*<\/span>root,<\/span>l,<\/span>mid,<\/span>mark[<\/span>root]<\/span>)<\/span>;<\/span>\n    nodeupdate<\/span>(<\/span>2<\/span>*<\/span>root+<\/span>1<\/span>,<\/span>mid+<\/span>1<\/span>,<\/span>r,<\/span>mark[<\/span>root]<\/span>)<\/span>;<\/span>\n    mark[<\/span>root]<\/span>=<\/span>0<\/span>;<\/span>\n}<\/span>\nint<\/span> update<\/span>(<\/span>int<\/span> root,<\/span>int<\/span> l,<\/span>int<\/span> r,<\/span>int<\/span> L,<\/span>int<\/span> R,<\/span>ll num)<\/span>\n{<\/span>\n    if<\/span>(<\/span>l>=<\/span>L&&<\/span>r<=<\/span>R)<\/span>\n    {<\/span>\n        nodeupdate<\/span>(<\/span>root,<\/span>l,<\/span>r,<\/span>num)<\/span>;<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    }<\/span>\n    pushdown<\/span>(<\/span>root,<\/span>l,<\/span>r)<\/span>;<\/span>\n    int<\/span> mid=<\/span>(<\/span>l+<\/span>r)<\/span>\/<\/span>2<\/span>;<\/span>\n    if<\/span>(<\/span>mid>=<\/span>L)<\/span>\n        update<\/span>(<\/span>root*<\/span>2<\/span>,<\/span>l,<\/span>mid,<\/span>L,<\/span>R,<\/span>num)<\/span>;<\/span>\n    if<\/span>(<\/span>mid<<\/span>R)<\/span>\n        update<\/span>(<\/span>root*<\/span>2<\/span>+<\/span>1<\/span>,<\/span>mid+<\/span>1<\/span>,<\/span>r,<\/span>L,<\/span>R,<\/span>num)<\/span>;<\/span>\n    sum[<\/span>root]<\/span>=<\/span>sum[<\/span>2<\/span>*<\/span>root]<\/span>+<\/span>sum[<\/span>2<\/span>*<\/span>root+<\/span>1<\/span>]<\/span>;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t,<\/span>cnt;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>;<\/span>\n    while<\/span>(<\/span>t--<\/span>)<\/span>\n    {<\/span>\n        memset<\/span>(<\/span>sum,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>sum)<\/span>)<\/span>;<\/span>\n        memset<\/span>(<\/span>mark,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>mark)<\/span>)<\/span>;<\/span>\n        int<\/span> n,<\/span>m,<\/span>ans=<\/span>0<\/span>;<\/span>\n        cnt=<\/span>0<\/span>;<\/span>\n        scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m)<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>m;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            int<\/span> x1,<\/span>y1,<\/span>x2,<\/span>y2;<\/span>\n            scanf<\/span>(<\/span>\"%d%d%d%d\"<\/span>,<\/span>&<\/span>x1,<\/span>&<\/span>x2,<\/span>&<\/span>y1,<\/span>&<\/span>y2)<\/span>;<\/span>\n            edge[<\/span>cnt++<\/span>]<\/span>=<\/span>node{<\/span>y1,<\/span>x1,<\/span>x2,<\/span>1<\/span>}<\/span>;<\/span>\n            edge[<\/span>cnt++<\/span>]<\/span>=<\/span>node{<\/span>y2,<\/span>x1,<\/span>x2,<\/span>-<\/span>1<\/span>}<\/span>;<\/span>\n        }<\/span>\n        sort<\/span>(<\/span>edge,<\/span>edge+<\/span>cnt,<\/span>cmp)<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>,<\/span>j=<\/span>0<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            while<\/span>(<\/span>j<<\/span>cnt&&<\/span>edge[<\/span>j]<\/span>.<\/span>h<=<\/span>i&&<\/span>edge[<\/span>j]<\/span>.<\/span>num==<\/span>1<\/span>)<\/span>\n            {<\/span>\n                update<\/span>(<\/span>1<\/span>,<\/span>1<\/span>,<\/span>n,<\/span>edge[<\/span>j]<\/span>.<\/span>a,<\/span>edge[<\/span>j]<\/span>.<\/span>b,<\/span>1<\/span>)<\/span>;<\/span>\n                j++<\/span>;<\/span>\n            }<\/span>\n            ans+<\/span>=<\/span>sum[<\/span>1<\/span>]<\/span>;<\/span>\n            while<\/span>(<\/span>j<<\/span>cnt&&<\/span>edge[<\/span>j]<\/span>.<\/span>h<=<\/span>i)<\/span>\n            {<\/span>\n                update<\/span>(<\/span>1<\/span>,<\/span>1<\/span>,<\/span>n,<\/span>edge[<\/span>j]<\/span>.<\/span>a,<\/span>edge[<\/span>j]<\/span>.<\/span>b,<\/span>1<\/span>)<\/span>;<\/span>\n                j++<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        cout<<<\/span>ans<<<\/span>endl;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
\u6c42\u7531\u591a\u4e2a\u77e9\u5f62\u6240\u56f4\u6210\u7684\u9762\u79ef\uff0c\u4ee3\u7801\u5f85\u9a8c\u8bc1<\/p>\n
#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nstruct<\/span> node\n{<\/span>\n    int<\/span> h,<\/span>a,<\/span>b,<\/span>num;<\/span>\n}<\/span>;<\/span>\nint<\/span> mark[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> sum[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nnode edge[<\/span>100500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nbool<\/span> cmp<\/span>(<\/span>node a,<\/span>node b)<\/span>\n{<\/span>\n    if<\/span>(<\/span>a.<\/span>h==<\/span>b.<\/span>h)<\/span>\n        return<\/span> a.<\/span>num><\/span>b.<\/span>num;<\/span>\n    else<\/span>\n        return<\/span> a.<\/span>h<<\/span>b.<\/span>h;<\/span>\n}<\/span>\nint<\/span> pushup<\/span>(<\/span>int<\/span> root,<\/span>int<\/span> l,<\/span>int<\/span> r,<\/span>ll num)<\/span>\n{<\/span>\n    mark[<\/span>root]<\/span>^<\/span>=<\/span>num;<\/span>\n    if<\/span>(<\/span>mark[<\/span>root]<\/span>)<\/span>\n        sum[<\/span>root]<\/span>=<\/span>r-<\/span>l+<\/span>1<\/span>;<\/span>\n    else<\/span> if<\/span>(<\/span>l==<\/span>r)<\/span>\n        sum[<\/span>root]<\/span>=<\/span>0<\/span>;<\/span>\n    else<\/span>\n        sum[<\/span>root]<\/span>=<\/span>sum[<\/span>2<\/span>*<\/span>root]<\/span>+<\/span>sum[<\/span>2<\/span>*<\/span>root+<\/span>1<\/span>]<\/span>;<\/span>\n}<\/span>\nint<\/span> pushdown<\/span>(<\/span>int<\/span> root,<\/span>int<\/span> l,<\/span>int<\/span> r)<\/span>\n{<\/span>\n    if<\/span>(<\/span>mark[<\/span>root]<\/span>==<\/span>0<\/span>)<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    int<\/span> mid=<\/span>(<\/span>l+<\/span>r)<\/span>\/<\/span>2<\/span>;<\/span>\n    pushup<\/span>(<\/span>2<\/span>*<\/span>root,<\/span>l,<\/span>mid,<\/span>mark[<\/span>root]<\/span>)<\/span>;<\/span>\n    pushup<\/span>(<\/span>2<\/span>*<\/span>root+<\/span>1<\/span>,<\/span>mid+<\/span>1<\/span>,<\/span>r,<\/span>mark[<\/span>root]<\/span>)<\/span>;<\/span>\n    mark[<\/span>root]<\/span>=<\/span>0<\/span>;<\/span>\n}<\/span>\nint<\/span> update<\/span>(<\/span>int<\/span> root,<\/span>int<\/span> l,<\/span>int<\/span> r,<\/span>int<\/span> L,<\/span>int<\/span> R,<\/span>ll num)<\/span>\n{<\/span>\n    if<\/span>(<\/span>l>=<\/span>L&&<\/span>r<=<\/span>R)<\/span>\n    {<\/span>\n        pushup<\/span>(<\/span>root,<\/span>l,<\/span>r,<\/span>num)<\/span>;<\/span>\n        return<\/span> 0<\/span>;<\/span>\n    }<\/span>\n    pushdown<\/span>(<\/span>root,<\/span>l,<\/span>r)<\/span>;<\/span>\n    int<\/span> mid=<\/span>(<\/span>l+<\/span>r)<\/span>\/<\/span>2<\/span>;<\/span>\n    if<\/span>(<\/span>mid>=<\/span>L)<\/span>\n        update<\/span>(<\/span>root*<\/span>2<\/span>,<\/span>l,<\/span>mid,<\/span>L,<\/span>R,<\/span>num)<\/span>;<\/span>\n    if<\/span>(<\/span>mid<<\/span>R)<\/span>\n        update<\/span>(<\/span>root*<\/span>2<\/span>+<\/span>1<\/span>,<\/span>mid+<\/span>1<\/span>,<\/span>r,<\/span>L,<\/span>R,<\/span>num)<\/span>;<\/span>\n    sum[<\/span>root]<\/span>=<\/span>sum[<\/span>2<\/span>*<\/span>root]<\/span>+<\/span>sum[<\/span>2<\/span>*<\/span>root+<\/span>1<\/span>]<\/span>;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t,<\/span>cnt;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>;<\/span>\n    while<\/span>(<\/span>t--<\/span>)<\/span>\n    {<\/span>\n        memset<\/span>(<\/span>sum,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>sum)<\/span>)<\/span>;<\/span>\n        memset<\/span>(<\/span>mark,<\/span>0<\/span>,<\/span>sizeof<\/span>(<\/span>mark)<\/span>)<\/span>;<\/span>\n        int<\/span> n,<\/span>m,<\/span>ans=<\/span>0<\/span>;<\/span>\n        cnt=<\/span>0<\/span>;<\/span>\n        scanf<\/span>(<\/span>\"%d%d\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m)<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>m;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            int<\/span> x1,<\/span>y1,<\/span>x2,<\/span>y2;<\/span>\n            scanf<\/span>(<\/span>\"%d%d%d%d\"<\/span>,<\/span>&<\/span>x1,<\/span>&<\/span>x2,<\/span>&<\/span>y1,<\/span>&<\/span>y2)<\/span>;<\/span>\n            edge[<\/span>cnt++<\/span>]<\/span>=<\/span>node{<\/span>y1,<\/span>x1,<\/span>x2,<\/span>1<\/span>}<\/span>;<\/span>\n            edge[<\/span>cnt++<\/span>]<\/span>=<\/span>node{<\/span>y2,<\/span>x1,<\/span>x2,<\/span>-<\/span>1<\/span>}<\/span>;<\/span>\n        }<\/span>\n        sort<\/span>(<\/span>edge,<\/span>edge+<\/span>cnt,<\/span>cmp)<\/span>;<\/span>\n        for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>,<\/span>j=<\/span>0<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n        {<\/span>\n            while<\/span>(<\/span>j<<\/span>cnt&&<\/span>edge[<\/span>j]<\/span>.<\/span>h<=<\/span>i&&<\/span>edge[<\/span>j]<\/span>.<\/span>num==<\/span>1<\/span>)<\/span>\n            {<\/span>\n                update<\/span>(<\/span>1<\/span>,<\/span>1<\/span>,<\/span>n,<\/span>edge[<\/span>j]<\/span>.<\/span>a,<\/span>edge[<\/span>j]<\/span>.<\/span>b,<\/span>1<\/span>)<\/span>;<\/span>\n                j++<\/span>;<\/span>\n            }<\/span>\n            ans+<\/span>=<\/span>sum[<\/span>1<\/span>]<\/span>;<\/span>\n            while<\/span>(<\/span>j<<\/span>cnt&&<\/span>edge[<\/span>j]<\/span>.<\/span>h<=<\/span>i)<\/span>\n            {<\/span>\n                update<\/span>(<\/span>1<\/span>,<\/span>1<\/span>,<\/span>n,<\/span>edge[<\/span>j]<\/span>.<\/span>a,<\/span>edge[<\/span>j]<\/span>.<\/span>b,<\/span>1<\/span>)<\/span>;<\/span>\n                j++<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        cout<<<\/span>ans<<<\/span>endl;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
\u53e6\uff1a\u5982\u679c\u6570\u636e\u91cf\u6bd4\u8f83\u5927\u6216\u8005\u51fa\u73b0\u5c0f\u6570\u53ef\u4ee5\u52a0\u79bb\u6563\u5316\u5904\u7406\u3002
 https:\/\/www.cnblogs.com\/heya\/p\/11315849.html<\/a><\/p>\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-12","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\/12","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=12"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/12\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=12"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=12"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=12"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}