poj-3237(ツリーチェーン分割) 4902 ワード 木の鎖が分断する ツリーには3つの操作があります.Q~a bは、a~b経路の最大値を問い合わせる.N~a bは、a~b経路上の数を反転操作する.(a=-a) C~a b第a条辺の値をbに変更する.反転操作については、区間の最大値と最小値とマークkを記録し、線分を更新すればよい.//#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define eps 1e-8 #define pii pair #define inf 0x3f3f3f3f #define rd(x) scanf("%d",&x) #define rd2(x,y) scanf("%d%d",&x,&y) #define ll long long int #define mod 1000000007 #define maxn 100005 #define maxm 1000005 struct edge{ int to,next; }edge[maxn*2]; int head[maxn],tot; int top[maxn];//v int fa[maxn]; int deep[maxn]; int num[maxn];// v int p[maxn];// v int fp[maxn];// int son[maxn];// int pos; int maxx(int a,int b){return a>b?a:b;} int mixx(int a,int b){return anum[son[u]]) son[u]=v; } } } // dfs top p void getpos(int u,int sp){ top[u]=sp; p[u]=pos++; fp[p[u]]=u; if(son[u]==-1) return; getpos(son[u],sp); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v!=son[u]&&v!=fa[u]) getpos(v,v); } } struct node{ int l,r,ma,mi,k;//k=1 }tree[maxn*3]; void build(int i,int l,int r){ tree[i].l=l;tree[i].r=r; tree[i].k=0; // tree[i].ma=-inf; // tree[i].mi=inf; if(l==r) return; int mid=(l+r)>>1; build(i<<1,l,mid); build((i<<1)|1,mid+1,r); } void push_down(int i){// if(tree[i].l==tree[i].r) return; if(tree[i].k){ tree[i].k^=1; tree[i<<1].k^=1;tree[(i<<1)|1].k^=1; tree[i<<1].mi=-tree[i<<1].mi;tree[i<<1].ma=-tree[i<<1].ma; tree[(i<<1)|1].mi=-tree[(i<<1)|1].mi;tree[(i<<1)|1].ma=-tree[(i<<1)|1].ma; swap(tree[i<<1].ma,tree[i<<1].mi); swap(tree[(i<<1)|1].ma,tree[(i<<1)|1].mi); } } void push_up(int i){ tree[i].ma=maxx(tree[i<<1].ma,tree[(i<<1)|1].ma); tree[i].mi=mixx(tree[i<<1].mi,tree[(i<<1)|1].mi); } int query(int i,int l,int r){ if(tree[i].l==l&&tree[i].r==r) return tree[i].ma; push_down(i); int mid=(tree[i].l+tree[i].r)>>1; if(r<=mid) return query(i<<1,l,r); else if(l>mid) return query((i<<1)|1,l,r); else return maxx(query(i<<1,l,mid),query((i<<1)|1,mid+1,r)); } void change(int i,int l,int r){ if(tree[i].l==l&&tree[i].r==r){ tree[i].k^=1; tree[i].ma=-tree[i].ma;tree[i].mi=-tree[i].mi; swap(tree[i].ma,tree[i].mi); return; } push_down(i); int mid=(tree[i].l+tree[i].r)>>1; if(r<=mid) change(i<<1,l,r); else if(l>mid) change((i<<1)|1,l,r); else{ change(i<<1,l,mid); change((i<<1)|1,mid+1,r); } push_up(i); } void update(int i,int k,int val){ if(tree[i].l==tree[i].r) { tree[i].ma=tree[i].mi=val; return; } push_down(i); int mid=(tree[i].l+tree[i].r)>>1; if(k<=mid) update(i<<1,k,val); else update((i<<1)|1,k,val); push_up(i); } int findma(int u,int v){// int f1=top[u],f2=top[v]; int tmp=-1000000000; while(f1!=f2){ if(deep[f1]deep[v]) swap(u,v); return maxx(tmp,query(1,p[son[u]],p[v])); } void change(int u,int v){// int f1=top[u],f2=top[v]; // int tmp=-1000000000; while(f1!=f2){ if(deep[f1]deep[v]) swap(u,v); //return maxx(tmp,query(1,p[son[u]],p[v])); change(1,p[son[u]],p[v]); } int t,n,a,b,c; int e[maxn][3]; int main() { rd(t); while(t--){ rd(n); init(); for(int i=1;ideep[e[i][1]]) swap(e[i][0],e[i][1]); update(1,p[e[i][1]],e[i][2]); } char op[10]; while(scanf("%s",op)){ if(op[0]=='D') break; scanf("%d%d",&a,&b); if(op[0]=='Q') printf("%d",findma(a,b)); else if(op[0]=='N') change(a,b); else update(1,p[e[a][1]],b); } } return 0; } while文をforeachに変換する 進捗どうですかを遅ればせながらC#で(LINQ)