【BZOJ 1018】 [SHOI2008]堵塞的交通traffic

2019-11-06 06:56:50

字体：大中小

来源：转载

供稿：网友

【题目链接】:http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1018

【题意】

【题解】按照这里的题解写的http://blog.csdn.net/popoQQq/article/details/44116729 主要思路就是根据最小单元的合并方式推出整个线段的合并. 其中要往左走和往右走的过程,可以一开始让那个点往左移动,看看最远能到哪里,右边的点也一样,一直向右移动看看最远能到哪; 然后在最左和最右之间求联通性; a[x][y]表示这个区间的左端点的上下方和右端点的上下方的连通性; 可以根据这个合并区间; 线段树操作特别是往最左找的过程不好写; 【完整代码】

#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int, int> pii;typedef pair<LL, LL> pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };const double pi = acos(-1.0);const int N = 110;const int M = 1e5 + 100;int n;bool a[M][2];struct abcd{ bool a[2][2]; abcd(bool _ = false) { a[0][0] = a[1][1] = true; a[0][1] = a[1][0] = _; } bool* Operator [] (int x) { return a[x]; } friend abcd merge(bool sta[2], abcd x, abcd y) { abcd re; re[0][0] = (x[0][0] & sta[0] & y[0][0]) | (x[0][1] & sta[1] & y[1][0]); re[1][1] = (x[1][1] & sta[1] & y[1][1]) | (x[1][0] & sta[0] & y[0][1]); re[0][1] = (x[0][0] & sta[0] & y[0][1]) | (x[0][1] & sta[1] & y[1][1]); re[1][0] = (x[1][0] & sta[0] & y[0][0]) | (x[1][1] & sta[1] & y[1][0]); return re; }};struct segtree{ segtree *ls, *rs; abcd status; segtree() :ls(0x0), rs(0x0) {}#define push_up(); status = merge(a[mid],ls->status,rs->status); void Build_Tree(int x, int y) { if (x == y) return; int mid = (x + y) >> 1; ls = new segtree, rs = new segtree; ls->Build_Tree(x, mid); rs->Build_Tree(mid + 1, y); push_up(); } void refresh(int x, int y, int pos) { int mid = (x + y) >> 1; if (pos == mid) { push_up(); return; } if (pos < mid) ls->refresh(x, mid, pos); else rs->refresh(mid + 1, y, pos); push_up(); } void modify(int x, int y, int pos, int flag) { int mid = (x + y) >> 1; if (x == y) { new(&status) abcd(flag); return; } if (pos <= mid) ls->modify(x, mid, pos, flag); else rs->modify(mid + 1, y, pos, flag); push_up(); } void _get_left(int x, int y, int &pos, abcd &sta, int flag) { int mid = (x + y) >> 1; if (x == y) return; abcd temp = merge(a[y], rs->status, sta); if (temp[0][flag] || temp[1][flag]) pos = mid + 1, sta = temp, ls->_get_left(x, mid, pos, sta, flag); else rs->_get_left(mid + 1, y, pos, sta, flag); } void get_left(int x, int y, int &pos, abcd &sta, int flag) { if (x == y) return; int mid = (x + y) >> 1; if (pos <= mid) ls->get_left(x, mid, pos, sta, flag); else { //pos > mid rs->get_left(mid + 1, y, pos, sta, flag); if (pos != mid + 1) return; //pos==mid+1; abcd temp = merge(a[mid], ls->status, sta); if (temp[0][flag] || temp[1][flag]) pos = x, sta = temp; else ls->_get_left(x, mid, pos, sta, flag); } } void _get_right(int x, int y, int &pos, abcd &sta, int flag) { int mid = (x + y) >> 1; if (x == y) return; abcd temp = merge(a[x - 1], sta, ls->status); if (temp[flag][0] || temp[flag][1]) pos = mid, sta = temp, rs->_get_right(mid + 1, y, pos, sta, flag); else ls->_get_right(x, mid, pos, sta, flag); } void get_right(int x, int y, int &pos, abcd &sta, int flag) { if (x == y) return; int mid = (x + y) >> 1; if (mid < pos) rs->get_right(mid + 1, y, pos, sta, flag); else { //pos <= mid ls->get_right(x, mid, pos, sta, flag); if (pos != mid) return; //pos==mid abcd temp = merge(a[mid], sta, rs->status); if (temp[flag][0] || temp[flag][1]) pos = y, sta = temp; else rs->_get_right(mid + 1, y, pos, sta, flag); } } abcd get_ans(int x, int y, int l, int r) { if (x == l && y == r) return status; int mid = (x + y) >> 1; if (mid < l) return rs->get_ans(mid + 1, y, l, r); if (r <= mid) return ls->get_ans(x, mid, l, r); return merge(a[mid], ls->get_ans(x, mid, l, mid), rs->get_ans(mid + 1, y, mid + 1, r)); }} *tree = new segtree;void modify(int x1, int y1, int x2, int y2, bool flag){ if (x1 == x2) { if (y1 > y2) swap(y1, y2); a[y1][x1 - 1] = flag; tree->refresh(1, n, y1); return; } //y1 == y2 tree->modify(1, n, y1, flag);}void query(int x1, int y1, int x2, int y2){ if (y1 > y2) { swap(x1, x2); swap(y1, y2); } abcd temp(false); tree->get_left(1, n, y1, temp, x1 - 1); x1 = temp[0][x1 - 1] ? 1 : 2; abcd temp1(false); tree->get_right(1, n, y2, temp1, x2 - 1); x2 = temp1[x2 - 1][0] ? 1 : 2; abcd temp2 = tree->get_ans(1, n, y1, y2); puts(temp2[x1 - 1][x2 - 1] ? "Y" : "N");}int main(){ //freopen("F://rush.txt", "r", stdin); rei(n); tree->Build_Tree(1, n); int x1, y1, x2, y2; char p[10]; while (1) { scanf("%s", p); rei(x1), rei(y1), rei(x2), rei(y2); if (p[0] == 'C') modify(x1, y1, x2, y2, false); if (p[0] == 'O') modify(x1, y1, x2, y2, true); if (p[0] == 'A') query(x1, y1, x2, y2); if (p[0] == 'E') break; } return 0;}

上一篇：Comparable和Comparator的区别

下一篇：malloc()函数和free()函数源代码