[POJ] [P3237] [Tree] [문제 풀이] [나무 사슬 분할 + 선분 수]
최근 에 데이터 구조 에 중독 되 었 습 니까?맨 날 체인 절개 해.
Code:
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
#include<climits>
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define L i<<1
#define R i<<1|1
#define Clear(x) memset(x,0,sizeof(x))
using namespace std;
int n;
const int maxn=10200;
int rw[maxn],vis2[maxn],w[maxn],dep[maxn],vis[maxn],fa[maxn],son[maxn],siz[maxn],top[maxn],z,sor[maxn];
typedef pair<int,int> pii;
pii edges[maxn];
vector<pii>G[maxn];
void add(int u,int v,int w){
G[u].push_back(pii(v,w));
G[v].push_back(pii(u,w));
}
int getint(){
int res=0,ok=0,f=1;char ch;
while(1){
ch=getchar();
if(ch=='-'){f*=-1;continue;}
if(ch<='9'&&ch>='0'){
res*=10;res+=ch-'0';ok=1;
}else if(ok)break;
}return res*f;
}
struct node{
int maxx,minn,lazy;
void init(){
maxx=INT_MIN,minn=INT_MAX,lazy=0;
}
};
node t[maxn<<2];
struct seg_tree{
void pushdown(int i){
if(!t[i].lazy)return;
int maxx=t[L].maxx,minn=t[L].minn;
t[L].maxx=-minn;
t[L].minn=-maxx;
t[L].lazy^=1;
maxx=t[R].maxx;minn=t[R].minn;
t[R].maxx=-minn;
t[R].minn=-maxx;
t[R].lazy^=1;
t[i].lazy^=1;
}
void maintain(int i){
// if(!vis2[L]){
// vis2[L]=1;t[L].init();
// }
// if(!vis2[R]){
// vis2[R]=1;t[R].init();
// }
t[i].maxx=max(t[L].maxx,t[R].maxx);
t[i].minn=min(t[L].minn,t[R].minn);
}
void Change(int i,int l,int r,int pos,int val){
if(l==r){
// if(!vis2[i]){
// vis2[i]=1;t[i].init();
// }
t[i].maxx=t[i].minn=val;t[i].lazy=0;
return;
}
// if(!vis2[i]){
// vis2[i]=1;t[i].init();
// vis2[L]=vis2[R]=1;
// t[L].init();t[R].init();
// }
pushdown(i);
int mid=(l+r)>>1;
if(pos<=mid)Change(lson,pos,val);
else Change(rson,pos,val);
maintain(i);
}
void Negate(int i,int l,int r,int l0,int r0){
if(l0<=l&&r0>=r){
int maxx=t[i].maxx,minn=t[i].minn;
t[i].maxx=-minn;
t[i].minn=-maxx;
t[i].lazy^=1;
return;
}
pushdown(i);
int mid=(l+r)>>1;
if(l0<=mid)Negate(lson,l0,r0);
if(r0>mid )Negate(rson,l0,r0);
maintain(i);
}
int qmax(int i,int l,int r,int l0,int r0){
if(l0<=l&&r0>=r){
return t[i].maxx;
}
pushdown(i);
int mid=(l+r)>>1,ans=INT_MIN;
if(l0<=mid)ans=max(ans,qmax(lson,l0,r0));
if(r0>mid) ans=max(ans,qmax(rson,l0,r0));
return ans;
}
void debb(){
for(int i=1;i<=15;i++)
cout<<i<<" "<<t[i].maxx<<" "<<t[i].minn<<" "<<t[i].lazy<<endl;
}
}T;
void dfs(int u){
son[u]=0;siz[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i].first;
if(fa[u]!=v){
dep[v]=dep[u]+1;
fa[v]=u;
dfs(v);
if(siz[son[u]]<siz[v])son[u]=v;
siz[u]+=siz[v];
}
}
}
void Change(int u,int val){
if(w[u]!=1)
T.Change(1,1,n,w[u],val);
}
void build(int u,int W,int tp){
w[u]=++z;Change(u,W);top[u]=tp;
if(son[u])
for(int i=0;i<G[u].size();i++)if(G[u][i].first==son[u])build(G[u][i].first,G[u][i].second,tp);
for(int i=0;i<G[u].size();i++){
int v=G[u][i].first;
if(v!=fa[u]&&v!=son[u]){
build(v,G[u][i].second,v);
}
}
}
void Negate(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
int a=w[u],b=w[top[u]];
if(a>b)swap(a,b);
T.Negate(1,1,n,a,b);
u=fa[top[u]];
}else{
int a=w[v],b=w[top[v]];
if(a>b)swap(a,b);
T.Negate(1,1,n,a,b);
v=fa[top[v]];
}
}
int a=w[u],b=w[v];
if(a>b)
swap(a,b);
if(a!=b)
T.Negate(1,1,n,a+1,b);
}
int qmax(int u,int v){
int ans=INT_MIN;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
int a=w[u],b=w[top[u]];
if(a>b)swap(a,b);
ans=max(ans,T.qmax(1,1,n,a,b));
u=fa[top[u]];
}else{
int a=w[v],b=w[top[v]];
if(a>b)swap(a,b);
ans=max(ans,T.qmax(1,1,n,a,b));
v=fa[top[v]];
}
}
int a=w[u],b=w[v];
if(a>b)swap(a,b);
if(a!=b)
ans=max(ans,T.qmax(1,1,n,a+1,b));
return ans;
}
int main(){
int TT=getint();
while(TT--){
Clear(edges);Clear(vis2);Clear(vis);Clear(w);Clear(dep);Clear(fa);Clear(son);Clear(siz);Clear(top);Clear(sor);Clear(t);
n=getint();z=0;//sor[0]=INT_MIN;
for(int i=1;i<=n;i++)G[i].clear();
for(int i=1;i<=(n<<2);i++)t[i].init();
for(int i=1;i<n;i++){
int u=getint(),v=getint(),w=getint();add(u,v,w);edges[i].first=u;edges[i].second=v;
}
dfs(1);
build(1,INT_MIN,1);
//T.debb();
char opt[22];int fuck=0;//n--;
while(scanf("%s",opt)==1){
switch(opt[0]){
case 'D':{
fuck=1;
break;
}
case 'Q':{
int u=getint(),v=getint();
printf("%d
",qmax(u,v));
break;
}
case 'C':{
int u=getint(),val=getint();
if(dep[edges[u].first]>dep[edges[u].second])
u=edges[u].first;
else
u=edges[u].second;
// T.Change(1,1,n,w[u])
Change(u,val);
break;
}
case 'N':{
int u=getint(),v=getint();
Negate(u,v);
break;
}
}
// T.debb();
// cout<<endl;
if(fuck)break;
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.