UVA11402 - Ahoy, Pirates!(线段树)

题目链接

题目大意：给你n个01串，每个串拼接m次得到新串，最后在把这n个新串拼接起来得到最终的目标串。
然后给你四种操作：
F a b :把位置a到b都置为1；
E a b :把位置a到b都置为0；
I a b :把位置a到b上的数字翻转(0,1互换)；
S a b :查询位置a到b有多少个1.

解题思路:线段树节点内部附加信息：setv：标记这个结点范围内有set值，并且需要传递到这个节点的孩子。resv：标记这个节点范围内有翻转，并且也需要传递到这个节点的孩子。注意：setv和resv标记的范围是节点u的孩子，并不包括本身，所以还需要根据父亲节点附加信息处理这个节点的值。还有这题的时间很紧，对于那些经常需要调用的函数加上inline可以加快速度。

代码：

#include 
   
     #include 
    
      #define lson(x) (x<<1) #define rson(x) ((x<<1) + 1) const int maxn = 1100000; int v[maxn]; struct Node { int l, r, v; int setv, resv; void set (int l, int r, int v, int setv, int resv) { this->l = l; this->r = r; this->v = v; this->setv = setv; this->resv = resv; } }node[4 * maxn]; inline void pushup (int u) { node[u].set(node[lson(u)].l, node[rson(u)].r, node[lson(u)].v + node[rson(u)].v, -1, 0); } inline void set_node(int u, int v) { node[u].setv = v; node[u].resv = 0; node[u].v = v * (node[u].r - node[u].l + 1); } inline void res_node(int u) { node[u].resv ^= 1; node[u].v = node[u].r - node[u].l + 1 - node[u].v; } inline void pushdown (int u) { if (node[u].setv >= 0) { set_node(lson(u), node[u].setv); set_node(rson(u), node[u].setv); node[u].setv = -1; } if (node[u].resv) { res_node(lson(u)); res_node(rson(u)); node[u].resv = 0; } } void build (int u, int l, int r) { if (l == r) node[u].set(l, r, v[l - 1], -1, 0); else { int m = (l + r) / 2; build (lson(u), l, m); build (rson(u), m + 1, r); pushup(u); } } void update (int u, int l, int r, int v) { if (node[u].l >= l && node[u].r <= r) { set_node(u, v); return; } int m = (node[u].l + node[u].r) / 2; pushdown(u); if (l <= m) update (lson(u), l, r, v); if (r > m) update (rson(u), l, r, v); pushup(u); } void reserve (int u, int l, int r) { if (node[u].l >= l && node[u].r <= r) { res_node(u); return; } int m = (node[u].l + node[u].r) / 2; pushdown(u); if (l <= m) reserve(lson(u), l, r); if (r > m) reserve(rson(u), l, r); pushup(u); } int query (int u, int l, int r) { if (node[u].l >= l && node[u].r <= r) return node[u].v; int m = (node[u].l + node[u].r) / 2; int ret = 0; pushdown(u); if (l <= m) ret += query (lson(u), l, r); if (r > m) ret += query (rson(u), l, r); pushup(u); return ret; } int main () { int T, n, t, q; int x, y; int N, len; char s[100]; scanf ("%d", &T); for (int i = 1; i <= T; i++) { printf ("Case %d:\n", i); memset (v, 0, sizeof (v)); len = 0; scanf ("%d", &n); while (n--) { scanf ("%d%s", &t, s); N = strlen (s); for (int j = 0; j < t; j++) for (int k = 0; k < N; k++) { if (s[k] == '1') v[len] = 1; len++; } } build(1, 1, len); scanf ("%d", &q); int cas = 0; while (q--) { scanf ("%s%d%d", s, &x, &y); if (s[0] == 'F') update(1, x + 1, y + 1, 1); else if (s[0] == 'E') update (1, x + 1, y + 1, 0); else if (s[0] == 'I') reserve(1, x + 1, y + 1); else printf ("Q%d: %d\n", ++cas, query(1, x + 1, y + 1)); } } return 0; }