Codeforces Round #442 (Div. 2) Danil and a Part-time Job
2024-08-26 03:13:25
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
*/
最新文章
- codeforces Simple Molecules
- HTML学习笔记——head、body及简单标签
- font-size单位换算
- spring 方法注入
- 基于KVM的虚拟化研究及应用
- Python的列表排序
- C++ Primer 练习7.32(C++ Primer读书笔记)
- Windows Azure上的Odoo(OpenERP)-2.在Ubuntu虚拟机上部署Odoo(OpenERP)
- Kate Spade_百度百科
- linq to entity asp.net mvc 多字段排序
- openui5的资料比较少
- sort函数使用的基本知识
- Python Click 学习笔记(转)
- NLP —— 图模型(一)隐马尔可夫模型(Hidden Markov model,HMM)
- LINUX 笔记之常用打包压缩命令
- MVC-1(javabean+jsp+servlet+jdbc)
- final和static关键字
- Virtualization
- JS操作MongoDB
- LeetCode 题解之Add Two Numbers II