本文主要是介绍线段树模板（lazy标记）ZOJ 3686，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题解：先搜索用将树上的点给定时间戳，以此当做该节点的区间。
#include <cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define N 150005
bool vis[N], check[N];
int dep, k, n;struct treeNode
{int id;treeNode *brother;treeNode *son;
} node[N], store[N];struct range
{int low, high;
} ran[N];struct NODE
{int l, r, val, upcnt;
} nd[N*3];#define L(u) (u<<1)
#define R(u) (u<<1|1)void build ( int u, int l, int r )
{nd[u].l = l;nd[u].r = r;nd[u].val = nd[u].upcnt = 0;if ( l == r ) return;int mid = ( l + r ) >> 1;build ( L(u), l, mid );build ( R(u), mid+1, r );
}void down(int u)
{if(nd[u].upcnt == 1){nd[u].upcnt = 0;nd[L(u)].upcnt = (nd[L(u)].upcnt + 1) % 2;nd[L(u)].val = nd[L(u)].r - nd[L(u)].l + 1 - nd[L(u)].val;nd[R(u)].upcnt = (nd[R(u)].upcnt + 1) % 2;nd[R(u)].val = nd[R(u)].r - nd[R(u)].l + 1 - nd[R(u)].val;}
}void update(int u, int l, int r)
{if(nd[u].l == l && nd[u].r == r){nd[u].upcnt = (nd[u].upcnt + 1) % 2;nd[u].val = r - l + 1 - nd[u].val;return;}if(nd[u].l != nd[u].r) down(u);int mid = ( nd[u].l + nd[u].r ) >> 1;if ( r <= mid )update ( L(u), l, r );else if ( l > mid )update ( R(u), l, r );else{update ( L(u), l, mid );update ( R(u), mid+1, r );}nd[u].val = nd[L(u)].val + nd[R(u)].val;
}int query(int u, int l, int r)
{if(nd[u].l == l && nd[u].r == r)return nd[u].val;if(nd[u].l != nd[u].r) down(u);int mid = ( nd[u].l + nd[u].r ) >> 1;if ( r <= mid )return query ( L(u), l, r );else if ( l > mid )return query ( R(u), l, r );elsereturn query ( L(u), l, mid ) + query ( R(u), mid+1, r );
}void dfs ( int r )
{vis[r] = true;ran[r].low = ++dep; //时间戳从1开始treeNode *temp = node[r].son;while ( temp != NULL ){if ( vis[ temp->id ] == false )dfs ( temp->id );temp = temp->brother;}ran[r].high = dep;
}int main()
{int m, u, v, i;while(scanf("%d%d",&n,&m) != EOF){dep = k = 0;memset(node,NULL,sizeof(node));memset(store,NULL,sizeof(store));memset(ran,0,sizeof(ran));memset(vis,0,sizeof(vis));for ( i = 2; i <= n; ++i ){scanf("%d",&u);v = i;if ( node[u].son == NULL ){node[u].son = &store[k++];node[u].son->id = v;}else{treeNode *temp = &store[k++];temp->id = v;temp->brother = node[u].son->brother;node[u].son->brother = temp;}}dfs(1);// for(int i = 1; i <= n; i++)// printf("@@@ %d %d\n", ran[i].low, ran[i].high);build(1, 1, dep);char str[3];while(m--){scanf("%s %d", str, &u);if(str[0] == 'q')printf("%d\n", query(1, ran[u].low, ran[u].high));elseupdate(1, ran[u].low, ran[u].high);}printf("\n");}return 0;
}
这篇关于线段树模板（lazy标记）ZOJ 3686的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
