http://codeforces.com/contest/877/problem/E

真的菜的不行,自己敲一个模板,到处都是问题。哎

 #include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+;
#define lson (q<<1)
#define rson ((q<<1)|1)
struct node
{
int l,r,mid;
int v,lazy;
}tree[maxn*];
int L[maxn],R[maxn],index;
int vis[maxn] = {};
int a[maxn];
vector<int> g[maxn];
void dfs(int x)
{
L[x] = index;
for(int i=;i<g[x].size();i++)
{
int v = g[x][i];
if(!vis[v])
{
vis[v] = ;
index++;
dfs(v);
}
}
R[x] = index;
}
void push_up(int q)
{
tree[q].v = tree[lson].v+tree[rson].v;
}
void build(int l,int r,int q)
{
tree[q].l = l,tree[q].r = r,tree[q].mid = (l+r)/;
tree[q].lazy = ;
if(l==r)
{
tree[q].v = a[l];
//printf("%d %d\n",l,tree[q].v);
return;
}
build(l,tree[q].mid,lson);
build(tree[q].mid+,r,rson);
push_up(q);
}
void push_down(int q)
{
if(tree[q].lazy)
{
tree[lson].v = (tree[lson].r-tree[lson].l+)-tree[lson].v;
tree[rson].v = (tree[rson].r-tree[rson].l+)-tree[rson].v;
tree[q].lazy ^= ;
tree[lson].lazy ^= ;
tree[rson].lazy ^= ;
}
}
void update(int l,int r,int q)
{
if(tree[q].l>=l&&tree[q].r<=r)
{
tree[q].lazy ^= ;
tree[q].v = (tree[q].r-tree[q].l+)-tree[q].v;
return;
}
push_down(q);
if(l<=tree[q].mid) update(l,r,lson);
if(r>=tree[q].mid+) update(l,r,rson);
push_up(q); ///v值由下往上更新
}
int query(int l,int r,int q) ///由上及下
{
if(tree[q].l>=l&&tree[q].r<=r)
{
// printf("%d %d %d %d\n",tree[q].l,tree[q].r,tree[q].v,tree[q].lazy);
return tree[q].v;
}
push_down(q);
int sum = ;
if(l<=tree[q].mid) sum += query(l,r,lson);
if(r>=tree[q].mid+) sum += query(l,r,rson);
return sum;
}
int main()
{
int n;scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x;scanf("%d",&x);
g[x].push_back(i);
g[i].push_back(x);
}
index = ;vis[] = ;
dfs();
for(int i=;i<=n;i++)
{
int cc;
scanf("%d",&cc);
a[L[i]] = cc; ///按dfs序来赋值
}
build(,n,);
int q;scanf("%d",&q);
while(q--)
{
char s[];
int v;
scanf("%s %d",s,&v);
if(s[]=='g')
{
printf("%d\n",query(L[v],R[v],));
}
else
{
update(L[v],R[v],);
}
}
return ;
}
/*
10
1 2 3 3 5 5 7 7 8
0 0 0 0 1 1 1 1 0 0
10
pow 3
get 3
*/

最新文章

  1. codeforces Simple Molecules
  2. HTML学习笔记——head、body及简单标签
  3. font-size单位换算
  4. spring 方法注入
  5. 基于KVM的虚拟化研究及应用
  6. Python的列表排序
  7. C++ Primer 练习7.32(C++ Primer读书笔记)
  8. Windows Azure上的Odoo(OpenERP)-2.在Ubuntu虚拟机上部署Odoo(OpenERP)
  9. Kate Spade_百度百科
  10. linq to entity asp.net mvc 多字段排序
  11. openui5的资料比较少
  12. sort函数使用的基本知识
  13. Python Click 学习笔记(转)
  14. NLP —— 图模型(一)隐马尔可夫模型(Hidden Markov model,HMM)
  15. LINUX 笔记之常用打包压缩命令
  16. MVC-1(javabean+jsp+servlet+jdbc)
  17. final和static关键字
  18. Virtualization
  19. JS操作MongoDB
  20. LeetCode 题解之Add Two Numbers II

热门文章

  1. 示例vue 的keep-alive缓存功能的实现
  2. PHP函数详解:call_user_func()使用方法
  3. 【php】【特殊案例】数组调用方法
  4. Head First Python (二)
  5. nw335 debian sid x86-64 -- 1 需求介绍
  6. Splay的用法
  7. POJ 3057 网络流 Evacuation
  8. git仓库删除所有提交历史记录
  9. luogu1251 餐巾计划问题
  10. TensorFlow学习笔记(6):TensorBoard之Embeddings