wata 哥 的 vectorMAX G 第一次不能用 POJ 3321 树状数组

本文主要是介绍wata 哥 的 vectorMAX G 第一次不能用 POJ 3321 树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关键是括号序列啊

还有，括号序列上一段代表一棵树，一个点还是代表一个点。

用指针表示图

#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
using namespace std;#define ll long long
#define P pair<int,int>
#define PDI pair<double,int>
#define fst first
#define sec second
#define MS(x) memset(x,0,sizeof(x))
#define INF 0x3f3f3f3f
#define MAX 400000
struct edge
{int to;edge * next;
}e[MAX];
int head;
int sz[MAX];
edge* G[MAX];
void addEdge(int f,int t)
{edge *te=&e[head++];te->to=t;te->next=G[f];G[f]=te;te=&e[head++];te->to=f;te->next=G[t];G[t]=te;
}
int n;int bit[MAX];
int L[MAX];
int R[MAX];
int cnt;
void add(int i,int x)
{while(i<=cnt){bit[i]+=x;i+=(i&(-i));}
}int sum(int i)
{int res=0;while(i>0){res+=bit[i];i-=(i&(-i));}return res;
}
bool used[MAX];
void dfs(int x,int fa)
{used[x]=1;L[x]=++cnt;edge* te=G[x];while(te){int v=te->to;if(v!=fa&&!used[v])dfs(v,x);te=te->next;}R[x]=++cnt;
}
bool visit[MAX];
int main()
{//freopen("acm.in","r",stdin);scanf("%d",&n);for(int i=0;i<n-1;i++){int f,t;scanf("%d%d",&f,&t);addEdge(f,t);}dfs(1,0);for(int i=1;i<=n;i++)add(L[i],1);int m;scanf("%d",&m);for(int i=0;i<m;i++){char c[3];int node;scanf("%s%d",c,&node);if(c[0]=='Q'){printf("%d\n",sum(R[node])-sum(L[node]-1));}if(c[0]=='C'){if(!visit[node]){add(L[node],-1);visit[node]=1;}else{add(L[node],1);visit[node]=0;}}}return 0;
}

这篇关于wata 哥 的 vectorMAX G 第一次不能用 POJ 3321 树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---