| 记录编号 |
255333 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
2288.[HZOI 2015]疯狂的魔法树 |
最终得分 |
100 |
| 用户昵称 |
 Aglove |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.760 s |
| 提交时间 |
2016-04-27 16:46:15 |
内存使用 |
9.25 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
const int maxn=200010;
int n,m,u,v,blo,a,b,now,val;
int c[maxn],tot=1;
int fa[maxn];
int pos[maxn];
int add[100010],vis[100010];
vector<int>V[50010];
int ans=0;
struct Graph{
int h[maxn],cnt;
int next[maxn<<1],to[maxn<<1];
void add(int x,int y){++cnt;next[cnt]=h[x];h[x]=cnt;to[cnt]=y;}
}G,T;
bool cmp(const int &a,const int &b){return c[a]<c[b];}
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void Get_block(int u,int f){
fa[u]=f;
if(V[pos[f]].size()==blo){
tot++;pos[u]=tot;
T.add(pos[f],tot);
V[tot].push_back(u);
}else pos[u]=pos[f],V[pos[f]].push_back(u);
for(int i=G.h[u];i;i=G.next[i]){
int v=G.to[i];
if(v==f)continue;
Get_block(v,u);
}return;
}
int Get_up(vector<int>&V,int v){
int L=0,R=V.size()-1;
if(c[V[0]]>v)return -1;
while(L<R){
int mid=L+((R-L+1)>>1);
if(c[V[mid]]<=v)L=mid;
else R=mid-1;
}return L;
}
int Get_low(vector<int>&V,int v){
int L=0,R=V.size()-1;
if(c[V[R]]<v)return -1;
while(L<R){
int mid=(L+R)>>1;
if(c[V[mid]]>=v)R=mid;
else L=mid+1;
}return R;
}
int judge(int u){
if(vis[u]){
if(vis[u]>=a&&vis[u]<=b)return V[u].size();
else return 0;
}
int L=Get_low(V[u],a-add[u]);
int R=Get_up(V[u],b-add[u]);
if(L==-1||R==-1)return 0;
return (R-L+1);
}
void DFS_Block(int u){
ans+=judge(u);
for(int i=T.h[u];i;i=T.next[i]){
int v=T.to[i];
DFS_Block(v);
}return;
}
void DFS_Point(int u){
if(c[u]+add[pos[u]]>=a&&c[u]+add[pos[u]]<=b)ans++;
for(int i=G.h[u];i;i=G.next[i]){
int v=G.to[i];
if(v==fa[u])continue;
if(pos[v]==pos[u])DFS_Point(v);
else DFS_Block(pos[v]);
}return;
}
void push_down(int u){
int sz=V[u].size();
for(int i=0;i<sz;++i)c[V[u][i]]=vis[u];
vis[u]=0;
}
void Block_add(int u){
if(vis[u])vis[u]+=val;
else add[u]+=val;
for(int i=T.h[u];i;i=T.next[i]){
int v=T.to[i];
Block_add(v);
}return;
}
void Point_add(int u){
c[u]+=val;
for(int i=G.h[u];i;i=G.next[i]){
int v=G.to[i];
if(v==fa[u])continue;
if(pos[v]==pos[u])Point_add(v);
else Block_add(pos[v]);
}return;
}
void Block_modify(int u){
add[u]=0;vis[u]=val;
for(int i=T.h[u];i;i=T.next[i]){
int v=T.to[i];
Block_modify(v);
}return;
}
void Point_modify(int u){
c[u]=val-add[pos[u]];
for(int i=G.h[u];i;i=G.next[i]){
int v=G.to[i];
if(v==fa[u])continue;
if(pos[v]==pos[u])Point_modify(v);
else Block_modify(pos[v]);
}return;
}
void debug(){
for(int i=1;i<=tot;++i){
if(vis[i])push_down(i);
sort(V[i].begin(),V[i].end(),cmp);
}
for(int i=1;i<=n;++i){
printf("%d ",c[i]+add[pos[i]]);
}printf("\n");
}
int main(){
freopen("H_Tree.in","r",stdin);
freopen("H_Tree.out","w",stdout);
read(n);read(m);
for(int i=1;i<=n;++i)read(c[i]);
for(int i=1;i<n;++i){
read(u);read(v);
G.add(u,v);G.add(v,u);
}blo=250;pos[0]=1;Get_block(1,0);
for(int i=1;i<=tot;++i)sort(V[i].begin(),V[i].end(),cmp);
//for(int i=1;i<=n;++i)printf("%d ",pos[i]);
//printf("\n");
while(m--){
char ch=getchar();
while(ch<'!')ch=getchar();
if(ch=='Q'){
read(u);read(a);read(b);
ans=0;now=pos[u];
if(vis[now])push_down(now);
DFS_Point(u);
printf("%d\n",ans);
}else if(ch=='M'){
read(u);read(val);
now=pos[u];
if(vis[now])push_down(now);
c[u]=val-add[now];
sort(V[now].begin(),V[now].end(),cmp);
}else if(ch=='C'){
read(u);read(val);
now=pos[u];
if(vis[now])push_down(now);
Point_add(u);
sort(V[now].begin(),V[now].end(),cmp);
}else if(ch=='W'){
read(u);read(val);
now=pos[u];
if(vis[now])push_down(now);
Point_modify(u);
sort(V[now].begin(),V[now].end(),cmp);
}else{
read(u);read(v);
++n;fa[n]=u;c[n]=v;
G.add(u,n);
if(V[pos[u]].size()==blo){
++tot;pos[n]=tot;
T.add(pos[u],tot);
V[tot].push_back(n);
}else{
now=pos[u];
if(vis[now])push_down(now);
pos[n]=pos[u];c[n]=v-add[now];
V[now].push_back(n);
sort(V[now].begin(),V[now].end(),cmp);
}
}
}return 0;
}