「fjWC2015」当小威遇上经济危机
格式问题比较大题面就不贴了
tex搞的pdf太酷炫
大意
给定一棵树，支持修改点权，询问某个点子树内最大值是否超过根
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include<map> #include<cmath> #include<queue> #include<vector> #include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int root,n,m,cnt,size,top,ind; int p[200005],v[200005],last[200005]; int mx[1600005],ls[1600005],rs[1600005]; int st[200005],inq[200005],ouq[200005],dfsq[400005]; bool mark[200005]; struct data{int to,next;}e[200005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } void update(int k) { mx[k]=max(mx[ls[k]],mx[rs[k]]); } void modify(int &k,int l,int r,int pos,int val) { if(!k)k=++size; if(l==r){mx[k]=val;return;} int mid=(l+r)>>1; if(pos<=mid)modify(ls[k],l,mid,pos,val); else modify(rs[k],mid+1,r,pos,val); update(k); } int query(int k,int l,int r,int x,int y) { if(!k)return -inf; if(l==x&&y==r)return mx[k]; int mid=(l+r)>>1; if(y<=mid)return query(ls[k],l,mid,x,y); else if(x>mid)return query(rs[k],mid+1,r,x,y); else return max(query(ls[k],l,mid,x,mid),query(rs[k],mid+1,r,mid+1,y)); } void dfs() { st[++top]=0; while(top) { int now=st[top]; if(mark[now]){ouq[now]=++ind;dfsq[ind]=now;top--;continue;} else {mark[now]=1;inq[now]=++ind;dfsq[ind]=now;} for(int i=last[now];i;i=e[i].next) st[++top]=e[i].to; } } int main() { freopen("fry.in","r",stdin); freopen("fry.out","w",stdout); n=read();mx[0]=-inf; for(int i=1;i<=n;i++)p[i]=read(),v[i]=read(); for(int i=1;i<=n;i++)insert(p[i],i); dfs(); for(int i=1;i<=n;i++)modify(root,1,ind,inq[i],v[i]); m=read(); char ch[5];int x; for(int i=1;i<=m;i++) { scanf("%s",ch+1);x=read(); if(ch[1]=='Q') { int tmp=query(root,1,ind,inq[x],ouq[x]); if(tmp>v[x])puts("Yes"); else puts("No"); } else { v[x]=read(); modify(root,1,ind,inq[x],v[x]); } } return 0; } |
计数器 9319361
OI 课件=>
OI 课件=>
黄学长，从哪个网站能提交这道题呢
似乎fjwc的题没有传到OJ上
哦这样啊，谢谢
哪能提交这些题，或者数据在哪呢
这题数据太坑了……有环