首页 > 代码库 > 仍是下次写
仍是下次写
/* luogu P3797 妖梦斩木棒 建一棵线段树,维护 1.有几段完整的木棍, 2.左边是否有向右边的开口, 3.右边是否有向左边的开口, 4.以及是否完全无开口(全为‘X‘)(便于区间合并)。 */ #include <cstdio> void read (int &now) { now = 0; register char word = getchar (); while (word < ‘0‘ || word > ‘9‘) word = getchar (); while (word >= ‘0‘ && word <= ‘9‘) { now = now * 10 + word - ‘0‘; word = getchar (); } } int N, M; struct S_D { S_D *Left, *Right; bool key; bool Bracket_L, Bracket_R; int value; int l, r; int Mid; inline void F_Updata (bool now_1, bool now_2, bool now) { Bracket_L = now_1; Bracket_R = now_2; key = now; value = 0; } S_D (int __l, int __r) : l (__l), r (__r) { Left = Right = NULL; Mid = __l + __r >> 1; key = false; value = 0; Bracket_L = Bracket_R = false; } S_D () { Left = Right = NULL; Bracket_L = Bracket_R = false; key = false; value = 0; } inline void Up () { this->key = this->Left->key & this->Right->key; this->Bracket_L = this->Left->key ? this->Right->Bracket_L : this->Left->Bracket_L; this->Bracket_R = this->Right->key ? this->Left->Bracket_R : this->Right->Bracket_R; this->value = http://www.mamicode.com/this->Left->value + this->Right->value; if (this->Left->Bracket_R && this->Right->Bracket_L && !this->Right->key && !this->Left->key) this->value ++; } }; S_D *Root; class Segment_Tree_Type { private : S_D* __Query_ (S_D *&now, int l, int r) { if (l <= now->l && now->r <= r) return now; S_D *res = new S_D ; if (l <= now->Mid) res->Left = __Query_ (now->Left, l, r); if (r > now->Mid) res->Right = __Query_ (now->Right, l, r); now->Up (); return res; } public : void Build (S_D *&now, int l, int r) { now = new S_D (l, r); if (l == r) { if (l == 1) now->F_Updata (false, true, false); else if (l == N) now->F_Updata (true, false, false); else now->F_Updata (true, true, true); return ; } Build (now->Left, l, now->Mid); Build (now->Right, now->Mid + 1, r); now->Up (); } void Change (S_D *&now, int pos, int to) { if (now->l == now->r) { if (to == 1) now->F_Updata (true, false, false); else if (to == N) now->F_Updata (false, true, false); else now->F_Updata (true, true, true); return ; } if (pos <= now->Mid) Change (now->Left, pos, to); if (pos > now->Mid) Change (now->Right, pos, to); now->Up (); } int Query (int x, int y) { return __Query_ (Root, x, y)->value; } }; Segment_Tree_Type Tree; int main (int argc, char *argv[]) { read (N); read (M); Tree.Build (Root, 1, N); char type[3]; for (int x, y; M --; ) { read (x); read (y); if (x == 1) { scanf ("%s", type); if (type[0] == ‘X‘) Tree.Change (Root, y, 2); else if (type[0] == ‘(‘) Tree.Change (Root, y, 1); else Tree.Change (Root, y, 0); } else { read (x); printf ("%d\n", Tree.Query (y, x)); } } return 0; }
仍是下次写
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。