【bzoj1018】 SHOI2008—堵塞的交通traffic

http://www.lydsy.com/JudgeOnline/problem.php?id=1018 (题目链接)

题意

  一个2行C列的矩形网格,网格上的每个点代表一个城市,相邻的城市之间有一条道路。一开始每条道路都是堵塞的,堵塞即为不可经过。经过一些操作后,可能某些道路通畅了,也可能某些道路堵塞了。询问两个城市是否联通。

Solution

  看了题解才醒悟,线段树神题啊。

  从一座城市走到另一座城市,一共有4种方案。

  【bzoj1018】 SHOI2008—堵塞的交通traffic

  若两城市在同一行(比如说s1,s2),那么:

  1. s1-->s2
  2. s1-->s3,s3-->s2
  3. s1-->s4,s4-->s2
  4. s1-->s3,s3-->s4,s4-->s2

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAN4AAAB9CAIAAABCjUqgAAAOh0lEQVR4nO2df3AVxR3A3+CgjHUsdkZBBy0yVqXORAbqoE1LKf6gmGAYpeCkVYOxYMuIpigo4MQa8AeUkE6kGGh5gcQXgRceQjAZIhJQEtOmk0YNmWqejC+TMSTy8l7fM+EE2f5x9Hjs7u3t3t3e7R37mfsrcz/29n3y3R+3PwJAIhGSgNsJkEjwSDUlgiLVlAiKVFMiKFJNiaBINSWCwqymklZay1sjBXuqZlUbHpGCPR+89uFQfIhH0iX+hlnN5tIWGikhQROxJI/US3wMs5o75u5kVVM9mktbUn1pHu8g8SXMaprzUhb0ElbcUVM96hbvl3ZK9LCqJuHMeDS+d+Few/ApS3kJFo5qqnQfiBo252X5LkHhrqYKpaAygko0HFJTIxFLkkt5GUElKk6rqRKPxsmdUAeWN5q7szkGlbNPfvTf8bsHAtv7nDnG7x54+Ejiq6HvnHxNKzB9arElxLijJgAgHo0fXPU+4d1ay1vPKGdM398Q53X0qLWsUtoVYlxTU4MQQQ+uet/6/SGENRI6xu7qLziaPJ7i+M9Jw1B8qG7xfhNSaofp2Om+mkA/gobyauytdw4qZ3/13qDr2gkeSq2ESexhrgObTU0lrfBQUyXVl8b+g1rvmfdKpBQhlCppxWKYtKtkZ1OztbyVn5oq9UUN9tpJHynvrD95qE+x93VQuhKnb33nazHjKI2X4fza3rZewk0OLG/EXsiaGDY1oUohj7pgIpbEVj3NVagHlbOT6k66riM97SdPM1U5xu7qt0tQcrXS0EgNvf5B1roZm5rQw/o6+pgup0TvCyfrfchejn67v773FI/020Kwe4ipBmIliCpppT3YHsqr0ZPyWKSLtbckEUuiN2SKL5bUZLqWiUQsiVbDmf7nyF6O3SW0lxD0oZRJUHJzJ5RXQxkm9cCW7PSXC6omACARS5r+nxtUzs45lPC6kSiUoXRS3UkaOwn9yta9BDp1M/rLxVUTAICWCDQf2bHtnlFvnfC0lBCGcdQwfLYH261XKw2JR+PQjxhrjlFeK7SaaIkQzq81rE0XHE2iP5WfvNQwFBQbPtVyHFuzDOXVmKhWkml6+XDmI+qLGigvFFpNbI2zivh9dlA5O/rtfjSE8E6qi5B7oyA7Cd1D9UUNPNq1seYY9CDKprrQagL9viSsoNgqpuAtcbvoSpzWq4aO3z2g9dKjPdP2luBYzDXVRVcTGA1TynxJtCj3eruHCUL4vLP+ZM/Xw9hyPJxfy3UYDTDbVPeAmsBoLocWONGiXKjudGfQC5/P/7EJzbq9C/fGo3HeSTLXVPeGmoA4Blkr2Ue9deLiqWISwIbPigd2QPnG42OeHvFoHHq6YWdLgAno7vQXjh41YlPOmONPTwDFt1g5Esuy9z5YhhV0dfaa7y+rPf9jvPlZIOuXbK/nM1bszlQTyq5g7rYZmx6f8E6uXccNW+6+5tnJl1x1mV5yts4MZiZgYdYi7GlOqxnMG2tRyszjwPw1WDtX/Hx14PUPA9v7AuUfX+xeBgKBa28KlP5TU3Nrbigzr+z1UjuuW3OXXnJWTF2ZmYCtM4N6Zzqq5uDyH9moZmJZdmTORqydbO/je669acSGc3auKDjfZ1Q+bzMPL9VDNy3fu47yx3JUTRu9JJTsG6aXsb2Pf9FqUF2r77317/8IbO+79o0v1s7fXTWr+q95wfve+J3zagao/fG2mqigO3LfzLo6i+19fMroUSPqfzNOL9NGjrvi+o3ThVXzfF2TqZ1lsoWeGoAzyCJfHQNVT1xww3XZ4PMjVm/rXYaTYF8x2DDD+P95wwzbHw6pSTiTyR/+ag4nwaY5XHMn+W16VcfGaY2F0xoLl7St7T/FvaNOIOil5PYP7Fk19xXDGdRSyfRQQ55rL8vMmtymJReRnZHnqaTcMg8cb+WUBM+q+eod8D/uaZu/HE5teIRQ9fFhKGWKlK/ewbuq41k1oZzikE35R18wrJv7R1C0guR4CQ7hFzU50J3qmdZYSNl+FM1RbRaEwUosqQHQuN4gUq7L5ldqE5BqkmCyUxxNO6o7oAGp8Ggx+rJ7XTb46pgrbyHVNKA71XPvwSetdMg5bGpHdQf2g9b5M463UpXd67JBS6XtNXh6pJrMiCzrGeWM3iDU1Bc9oP4VsC7bWEoOnZQmkGqapzMRLWgpFsrR3rZerJdVs6qbH6PrDxLmK4NU0yrWg6hdjpLXyQjlVIpZcOsh1bQZ66HUhKnkdTLOZ6wYTW9KpJocsRhQpzUWdqd6DJ+iN5sxPLcKr+ard4DI86DL0QWaTSDVdBTTsurFUT0vQznb+orugzO2JEvMshuLVNM1zBX9kKP4WbYPVPQ+cz8ovgXOWIGLbxSppvuYcHRaY2HPNyeUtAJ1FYVmVx/7/eNnXrxNzRYzGSsM3lRzOOknNSE6E1GaQv+eukUVC4JQ1qnBUjukmiic1URHxPmO8Jfvkb+RLl7+IpRvBx/+E5Qt0Ane2trLm2pCI+KqnmB6nLfAtpwmV88Pzt6WmWlv5VT2Fd0H9Q1B3UnNpS1uvw0D3lQTCpmeqt1bQR2nt2jFSsjL4Oxtvy57fEnlL/pX/zizzxJaeiWUV+OhwOkLNS8aulM9y196DW2S55csPdc8iszpOVwGev6tno8uL+2hwCnV9AipAdC4fuj1nFBOJZRd5fM231ybp9fHhAZOt9+EFqmm8KQGQP0roCRLWXV73UN/hvJq47yKydXz9ZpKuU1Lvuju8WI7vf9U3INq+rrn6BzIUF+sl20Lnvpk/c8K9i8g94B6Uc2ST7dAb0E4WRg1fd9zhJum0/pYEZRL4QcqzlQuBKkBAEBnIjrpXd3Y6UU1oTmDW7v3EE4WRk1/9xylBlAvlVW378j92wVVxpxtvTt3ZV5H+KQENeebS1uUtOjrg0KvcOo7UoKFUdOXPUf6k3WwRTlhIWq0H3TlH16HLndyCUxz0Fc0gbhq+gBcpNSOtgVPmRArs4i/v2wRdIeqWdVNLx+2cW9je2FqAwGpJheGk6BxPSjJwntZkjX0r0NQx2Qor4ZyQ4nMb/GvFPwFtdPKhvdcYWoDAamm/RCDJViXrXzcBI3FNLFbWfjL9ya9Oz+rZu7a35ajdnJ6M4swtYGAVNNOyMHy/5N10LGYxyJdJp6mtZDQ2Lm06c/iLOugwdQGAlJN2yAs4ZIxmxGd62Nxu5PORPSn4UehrC4pLJ0gwJoOEEwVTSDVtAc9Ly+cGoEdu259e6jORLRy9nbottrHJHGWwpNqOo5e5RKZ+h3Or4XypG7xfluSEFkK70SztGi1JsHUhkdECJ9STQfRq1zqzCODMiScX2vXDlGJWHLno+HMmwdnb0O/bfZ8c8KWx5lDqukUhEIct05Gqi8NZYi9O+qhO8KjA0RcDJ/Jb9NSTUdg8RK70kGkwKDrxATQI8rnbcYOX8o/+oLtjzZkVcdGgdSEcspgJLaH1Pz8CH75K9y6Qnozys11GJFBNx5d+8Im7Pd32x9tCDROpaCl2PASjmpCOfXJjk91T/XEiDjC6pU6lUs9LyMFe3jsj4tuPBrKq8EOX3K+WIcS8NHAx4aXcFTzP/s/y7x1fVGD7qno8veiQei21KlcKmml6eXDWC/5TeXBbjzamYi6XqybCNsc1RyKD9HeHRoRJ46ahuv86q/L31zaAr1+KK/mWKSL937i2GlDE/c96G6xLpaaDHeHfm8xFik1+BpefAuoekId84uCrsBRZUfvOg3Y+ZbYzRUcSIyGX9R0d5FSmjX6N8wA7bsJ90BDJo8mORbsfEvstHcnuzn9oqZbkMdnEGuWEG6FTBW9+ZZQse5kJ7xU0xT0G0fQbUOmpBW3QqYK2v2u/h0t1p9rL3MmSVJNFpi2MqGuY2A7jJwMmSpQmR5rjgEAulM9UEfSxH0POhM4pZos0GzYyL4iOjq8yJUpO1C/lTaOpDMRdaVYl2rSocZLQp3Swjq/aKc35cwKe4k1x6DMVwMnwBXrDx1ZyrsHnruarEB31zsNMoP5MXSMHjViU86Y409PIEfKlsIbpo+/3NwjLh95OfTKWVdn2fsW9KzOXpOZkuK7XlL/PnLcFeNDMyFXflh57zXPTr7kqss4JQZ6HM0llPKYxJyarhxWjNRYcNsCvhnKwpQxU/QSc+mNV9646360p/OGLXdzElQ4NbfOvGCB3SljpmBPc1fK4ZU3W5dSpeKezZnv+9xPltlyW9MQft3r1tyFqunYYTHxNvDM5AsWTtHKFIjhlTd7OliqoKX5xB9MtOXOpiH8uiPHXXH9xukXr5qEMiWTQ49d72kpVYQqzVUM03PpjVe6Iqgtib8AE00zqnbWQBSUz3JISrpucxNAbXMRlnmhyXxbtjxkOgwXR6BPvAY3NX0B9Kau9BmRk0Q40zFBpzY8cvhEm72JB7aoKeyKPNYR8J9QwCTR47Sawq7IYxGGwakOImCS6OGuJroxral0ik5bRVvmOzo8nkMPT+c8dzXRuVSm0ik0SlqBlj/gMSvNBJ7Oee5q6g3Q8hPowGHesywo8XTOc1cTfYbPWkLYuRZuJ+ocYqaKEhfUVKtiH7z2oQ8cxY7OFKSiCZCc99CmbMAZNdGWkPYTJmJJc/d0HSWttJa3Rgr2oO/l/MBhPby7KRtwRk20JSRIEB2KD7UH27F6mT7ECZlAf5KQ+KCTWMjnm1QzEUva+/MLe4Tza8UJmQDXBvVKmY5OFiCfb1JNAEAilty7EF4D0k+HifXYncGLZTrasjQckGBezUzi0bjPNA3n14rwxRyLYW3KE4dh9tqjpkr3gag/SnnRCnEItEz34mH4mnaqqWWcuxE0nF/rwDpE7qLXQ+KVg6Zlab+aEgfwdJm+Y+5OmkJJqulJXC+aTB/0lSWppkRQpJoSQZFqSgRFqikRFKmmRFCkmhJBkWpKBEWqKREUqaZEUKSaEkGRakoERaopERSppkRQpJoSQZFqSgRFqikRlP8BKfUBAdnSrzoAAAAASUVORK5CYII=" alt="技术分享" />

  若两城市不在同一行(比如说s1,s4),那么:

  1. s1-->s3,s3-->s4
  2. s1-->s2,s2-->s4
  3. s1-->s3,s3-->s2,s2-->s4
  4. s1-->s4

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAQcAAAB4CAIAAABwyqBQAAAQdklEQVR4nO2df3BUxR3ADxQIhh+pVRpnUggRTAS0KcIQtRNSNBrg1MhUZaRxzmLbWDuYoVLi1DEiUFAHAyriCNOzhEAgEIgwBCE2oo1EgxwqXPyRDJWgl9xxubsELnc57rZ/PD0u+/a9e/t+7Nv32M/sf8m929v3Pu+73337di2AwWAMxqJ3BRgM6mBWMBgwzAoGA4ZZwWDA6GyFLxwrbenNrPNYtnaJlMw6z8IP/a5gVN/aMq4QdLbC1hwQ90FIEltz4EzfJX0rzzArelrhC8fSatwyrIgXW3OABRBKkBj2pdzv9p4N6ftbdLPCFYzmHvAqaUGupNe6WedKL1zBaPmJPoUmSBeG2InWx4ryE30p1d3qNhnrUJHEFYyWtap8EunRRgcrSlt6+T8ppbq7qSuM/H+HN1LU6GNi6AjJmEDD/ZG0Fb5wLL0WziVSqrsbvsfoStrbgyIJCRuwUo4qSYJxxSBtBX/QKb3WjaUER9IAUnC4R4v6mxvlMuQ1eIVivhSausKlLb38+6Y8N2TfHIlagRx06r8Uk31AhzciEjRYxMDCF45J6anyb2qVzotKTqIUJPai+SX3gNcXxq4bUSv4gSKzzqPwmOJisN6URHzhGO6QIBkfJCJyGRQ1+nCPRtQKfr1l9J34JL2RsNFbEST2mqhyAImIGMVNeGefqBWqBwqIgsM94h1NNkiVSFIfFCYJ5BG5P2KdfT2tUCVQJNLmj+TUnxcRw9YcUPcbDUpSH+QNgVCC0GUg/ezraYVG3yLuRmlLL83dAAKIZ9W4o+TUktcAp0kp1d0S+1HkrPCFY2SsiCMUT3MPeBNbJ3LKGdq1J7huQ3DdhtCuPZFTTq0rpiPiWXV6rdtYXSYRkFOKoFMvBDkr+ANQZL63uMkv1MuMBQK9v/+DN2MSVAL3/+7Stx1kqkcMc/eahODPSZHyIIucFfzxATLfe6bvEvLumFnncS94lK8EV/wF98RC5rlExHtNpvSBAzkAkzTtJmcF/6Ik9tWA18sc8a+zbzywREgJroQPHSZZQ00Reo/FxD5wtPkj/PCYNO3WzQrCJyMxBR/79rfv5j8kroQ3Y1LvQ4vMkWkgpxSYJqtOCl+MlOpu8Y8QsoJ8qo3E4Y2Mt3e8d8cDSZUwTaaBTK/NlFVLoc0fwbr8CFnBnz1O5nshYqHQD8WCuYR4MVymIZJeUx0lAh+BM2Xg5DTwyRh0OTkNtD8OBvAuIRqtgCK4jKkpqnBh6XJ5Shgx0xDKJbAzuoEu0FkhdpnqUtrmY/0IclZYpAOdm5vvwPisSswbmapECW/GpOVjriVZ4YLpV9vmD3vhjyOaNqWe2TcK66LxfZyRVv0tIr3e/mXDf+brf02rUcRbTx8r8M4wdHrkMjR12HVP3jJ+811Z9VbccixvqkIrgktv0P1SkFhs9W8iosSOz3SvGDErLIPFMKcVSnzIqrcWbSxUqISxrOAHCjNFCVNYMXacciuufzpXng9c+cfTd15RVhg3SvgaR9ufH1k8+2rEVU6/FRhiLFo5qE6vtmL5wJG5/V4lVqz9U96VY4Xv4wx40ElZlHAdHF22cHjKcBnnTU2wrICvVdrGoKDXcCudF2UcRIkSWfXWFU/dbjwrTk4DbfPBuX8C9zYQ+Eh6W1EyDq4+UPvgQJ0VUIXkTeSGrvJZh0qOdh+X/vGBpqMqWHHfZFCRDSqyQeUcULsU9BGdtCIdSsbB1cfEVsg7CGQF7sdjoZDv9gKFVoQevelHK7iy0UqhGPxpBOZ5jM2sgFBoBVAcLnomTIr+fbAVFdlg3WzgoWsmiF4z9klgGisc3kFTUNJq3PKOo9wKAIC/4B7ZSoRKeErEy64yeoKGXjP2SWAaKyqdFxNrU9zkl3GQwMAFVayIdp6T148KPSbgQ2LQ8J2TVyt1gcdkyc7Y1xbTWAG9CidvAGqZY70qVgD8flTPjVNDu/YAlxNUPZFEDM4NvbNweEyW5omAuJjGCiigO7wRGQfJPfiIWlZgpd09N04N1e+HD+Fygn9OF3Ojco6OccO03SdgIiu0SLXzjyxWUqXIZw7frxGPL3punHrxhVXcsgbBdRv6N9ujboEsKGnoeLVAryycWYHE/FZgPalAEgsE+jfb4wJwBfu9IilBY2854bjBrEBifivUraEiXE6wZWHyfIOgG8wKJMwK4ricYM3M5G4QiR7MCiTMCj2QOEgVL/srQEST0SFmBRJmhX64nGDlrRhuqD2lipJVI7RCrhW4zcKsUBt7CZ4VqpSf1DLtbFkOuVbgNguzQm08HeD1uTqIUZFd/tq6lH+fTWxt88yW5ZBrBe4kYmaFNhB3o/SNt6GmtmztatpZSc8ELRWQawXcLMkmETMriKCxJL4VM9LtTqipc7f8N7FzpXcTqIFKViT/fwV11KRCfNSaGqg/uONUCgJFut3pWG29/D+6TkJRDWZFHBWnBtKIow5UzuGu3cCLU2xVc8Rftc0/sniZY33nxcsrpfo6v0rb+r/ERi54+1D/C7fA8rxyp+GDBrMijopTA+nF0wEq5yyzz5b+Jvoyx3p3qAe5jGzT2kcEA4u9RO+fqgBmRRx1pwbSi6cjdy/2Kg037H4XauGiRl+SNMa44YJZEUf1qYF0wk+fkpa0nfYhVZ2JzZtSPXiABTkVxaA5RrSfWXEZ83efAAAAPPf5Rtj/zT/e73dvmJlfWwT9dUzNTv5QbMNLJfCgE/JxuxHFaH+cWfEj5hmAEiUwcAFKn2zHKgBADOnu3jAzt25u5r6Hr9r2NdS2w6tb82uLltlnH371NrCp+LIYyMftmx82Ulfq/G7EelmSod0KiVu7xuHfQTWqp44EBi5YP1gC/cwWzxeD/ilhVLflpTuurfoEatirtn2dUfcXOAfbM3/Z3kWubxrRaYZRMu+BLnBiMqzEyWnSD0C7FVJ2sIwjeAc1EUe7j886VAJdzWI/09NRuqUGatWR249O3PegeBJirSkMrciBxTDEWO135bASJyYD/xHpB6DOCv7WrtI/yw8U8B3UyISiYf6jmKx66837F4j/TGhWz5Cqzhvq/iYlO295JRcRMRL7WnQCBYqvFuAegDor+Fu7Sv+suQPFy853kEqID7K5glGoPQvf3yJxzKpw5z2dq6cZTIyBLjhQYO79BSi0Anejvjj8PNtMgcId6rl5/wLoB+YefERcCf4zO2i5pxbPF88dWzVr7/0iYgRenMIXo3P1tId3WZe0rHSHMLq4mnPJD768U3Y6EYc6K2TUicPEeTYyvbYdqxC/IpGPsQXX1/J0gNfnIod0rTWF7Wt480EqsjtXT8uvvTer3pq/78Fln65NnFSiD3wlPhkDXBtlHIlGK6DUYu9ZSW9mmrX75A718JVY/1V10g/yX51Jr3VjLPDucoKqJzhPhLpS7lVT9q+fMWv33Kx6669q5m5d+pvzT8wNrlkDLYbCFc13Ikcm2dF+GUei0Qpo+cC8Bq+UT5mv++QO9aw8tZnfcZp1qCQUTb5sOJRky99G3l6ye8PM4h13IyMGqMh2r5jyzd1TJC4kp9VO5ANdoHXcICVax2GNOyVC2gpJe9TcNheqlpQPQZeOpC+ilaGpw659LGdi7Tx+R39i7bxrpl8v6ShQG976W3mVyblueNtTE0+vvdVWNcdaUwilGZG/Zl+YcxPWoqMt6eNHDBkirzJI0kYPcVSlJirR/9GYotsRe4JJRfjyU98KVaolhGmsGJo6LGN9PjL3xVDCoto+tBDFOaMuPZ8NKrJjz2b35k2Wt2b7vJGpatXHYrHsWDUS6juVLVS2+5ho0xnYiqt+NgLj62jiuidvQSox4Z1CDCWuGauRFRaLJTd9RMOijN6ZMpXwqroT+cLCYZASroOjlW7JZ1Yrsuqt4zffNe6Z6cbSA9lxmvBO4dj7Jg4ZPhTjQLaXtbPCYrHMGJ4iWwlvxqRPi8el/1xpJypt9JBNy1N8jaPV7DtxkLQCQwz8M4rshXOXlCHcGJo6LL1iFr/+2D5wvPXNoAZ8Zoe6tS0dlabECiX7aJ7ZN2rHqpE5E4ZCuQRXbPOHqfDzSOYVGPLgP7J4tPnZpA9r848sXnL8ZboePP0EcjaH9YMl8o4GNaDqW90F123Qywqxgj+5AwmNI7NAlhXtfZ35RxYnFYNCSQIDF577fCNyBPa0X84gJoEVAWm04vgvZUzuQGIeKwAA7X2dhe+XYomhoxucDEIm5x9ZLOWhBB9fOAY98KHQitDaX6ivBM4W4+KYyopETvs7bMcqcA3JQi2KoQXISRyJUUL2i7X8PVG1WBEw+MZbspXoybop+l6aaj4oeFqHREakNYwVHLLd0LEknRkuDn9PVC32z46ccspUArlJmkSCX4MvZgxS4vRdKoYIDhlr7xrMikQMYcisQyWylfCFY/wzqt2eqBK3XbbPL5W0SRo14C4yC/Sy4kzfJXWPLy8DIaCEkhVJ+H0ni5Z7okrZdvmHzCnj3jyt+unTFBmRlpAV0LTZzDqPRi1LQwBRa8Uqft9Jizw7kajbfWHpchElHnxmm2Vrl605oGk11EVGAxKygv9GHrGW3f1dI+4Ir47xgQPZd9K0+5RItPNc/9btiZPGNz31UumfXxv35mmuGinV3birUugIvVa0+SP8idDGCsTEQL5dZNnalV7r1mtLef4LlVirUugLvVYAABzeCL8ftfBDv4HuOgQQUkLwnTtSKFmVQl+otgKg+lHGuusQoKy1DxklMN650wb+uTPEHU3etACiVrT54XDBFfoblwBcLsFvn5z68w5vRO/aITpRhoj2/HE8KZ8iagUQCBeZdZ7Sll5fWOfboY4gO07y30HVBuQdjeZo7wvH+ON4Uj5I2oo2fySn/jyycc22taFkqM0lIJB3NGp7U8hWlTiIR9oKDqH2lbj8h5lwBaNCI0665xIQInc0CntTyCVRJMZefaxo80cy6zzIS4GqltWa8hN9yG4JJbkEkqRu6D7gjszQUqq7pc8f08cKINq4uQe8V4IY5ScQw0205RJC8B9AJYphaw6Qd4OTAXm3tWDOlNHNijh5DYj+A23hWF184RgyShhFCQ6HVyxoEPakqSuM7IjKS1n1t0LkrkPt4IYSGr4Ppdcifq+Oj65lI96boqRg9Z049LcCiN51TBMxxON7WWsfbbk1FiLDU/qWvAavjNdRqLACCOffFjoSOIUIjb1afooShlYCUBk05PnAQYsVQLRljSiGKxgtP9EnpHq80DzcJA97ezDpr9aupNe6lb+rSJEVHOKx2BBZuFAyDZWiRh/lP0QtCHiSVuO2NQfUet5FnRVSYnF6rZvCGSISgwPntr09qHd9GYJQZ0Uch1dwbCp+r9W7jpeREhwsRht7vWKh1wogQQwdO1TSI0O8KMn/GCSh2goAgMMbKWr0Je2QkMzFXcFoWavUyFDpvGj08aUrENqtSCSpIaqEDhlBgEUGk2EkKziQM0ToKZl1HhYcjI7xrBCaek1DMeKsDQYf41kRJ2kuTsABljaYEgNbAaTl4swHBi7GtiIRFQ1hF/0VjnmsYDDUglnBYMAwKxgMGGYFgwHDrGAwYJgVDAYMs4LBgGFWMBgwzAoGA4ZZwWDAMCsYDBhmBYMBw6xgMGCYFQwGDLOCwYBhVjAYMP8H3zTWjlYwLFoAAAAASUVORK5CYII=" alt="技术分享" />

  而我们怎么维护这个东西呢?考虑用线段树。每个节点表示区间[s,t]的矩形,并且记录8个变量:U,D,l,r,u,d,p,q。

  其中,mid为(s+t)/2:

  U:第一行mid,mid+1两列之间是否联通

  D:第二行mid,mid+1两列之间是否联通

  l:s1,s3是否联通

  r:s2,s4是否联通

  u:s1,s2是否联通

  d:s3,s4是否联通

  q:s1,s4是否联通

  p:s3,s2是否联通

  发现如果s=t的话,也就是说只有上下2个城市,那么U,D,u,d这4个变量就没有意义了,我们将它们全部赋值为1,避免一些不必要的麻烦。

  于是,线段树的操作就变得很显然了。另外注意线段树中的每一个节点只维护这个矩形四个角上的点的连通性,并且我们并不关心它的路径是什么,只考虑使其连通的路径存在于当前矩形的情况。

细节

  分类讨论有点多,别犯些奇奇怪怪的错误。

代码

// bzoj1018
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
struct tree {int l,r;}tr[maxn<<2];
struct data {int U,D,l,r,u,d,p,q;}w[maxn<<2];
int c; void merge(data &k,data l,data r) {
k.l=l.l | (l.u & k.U & r.l & k.D & l.d);
k.r=r.r | (r.u & k.U & l.r & k.D & r.d);
k.u=(l.u & k.U & r.u) | (l.q & k.D & r.p);
k.d=(l.d & k.D & r.d) | (l.p & k.U & r.q);
k.q=(l.u & k.U & r.q) | (l.q & k.D & r.d);
k.p=(l.d & k.D & r.p) | (l.p & k.U & r.u);
}
void build(int k,int s,int t) {
tr[k].l=s;tr[k].r=t;
if (s==t) {w[k].U=w[k].D=w[k].u=w[k].d=1;return;}
int mid=(s+t)>>1;
build(k<<1,s,mid);
build(k<<1|1,mid+1,t);
}
void updater(int k,int x,int T,int val) {
int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
if (x==mid) {
if (T==1) w[k].U=val;
else w[k].D=val;
merge(w[k],w[k<<1],w[k<<1|1]);
return;
}
if (x<=mid) updater(k<<1,x,T,val);
else updater(k<<1|1,x,T,val);
merge(w[k],w[k<<1],w[k<<1|1]);
}
void updatec(int k,int x,int val) {
int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
if (l==r) {w[k].l=w[k].r=w[k].p=w[k].q=val;return;}
if (x<=mid) updatec(k<<1,x,val);
else updatec(k<<1|1,x,val);
merge(w[k],w[k<<1],w[k<<1|1]);
}
data query(int k,int s,int t) {
int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
if (s<=l && r<=t) return w[k];
if (t<=mid) return query(k<<1,s,t);
else if (s>mid) return query(k<<1|1,s,t);
else {
data res=w[k];
merge(res,query(k<<1,s,t),query(k<<1|1,s,t));
return res;
}
}
int main() {
scanf("%d",&c);
build(1,1,c);
char s[10];
int r1,r2,c1,c2;
while (scanf("%s",s)!=EOF) {
if (s[0]=='E') break;
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
if (c1>c2) swap(c1,c2),swap(r1,r2);
if (s[0]=='O') {
if (r1==r2) updater(1,c1,r1,1);
else updatec(1,c1,1);
}
if (s[0]=='C') {
if (r1==r2) updater(1,c1,r1,0);
else updatec(1,c1,0);
}
if (s[0]=='A') {
data l=query(1,1,c1),x=query(1,c1,c2),r=query(1,c2,c);
int ans;
if (r1==1 && r2==1)
ans=x.u | (l.r & x.p) | (x.q & r.l) | (l.r & x.d & r.l);
if (r1==1 && r2==2)
ans=x.q | (l.r & x.d) | (x.u & r.l) | (l.r & x.p & r.l);
if (r1==2 && r2==1)
ans=x.p | (l.r & x.u) | (x.d & r.l) | (l.r & x.q & r.l);
if (r1==2 && r2==2)
ans=x.d | (l.r & x.q) | (x.p & r.l) | (l.r & x.u & r.l);
puts(ans ? "Y" : "N");
}
}
return 0;
}

  

上一篇:DOS命令(系统错误5,拒绝访问)的解决方法


下一篇:Java封装 properties文件操作