[BZOJ] [P2243] [SDOI 2011] [염색] [문제 풀이] [나무 사슬 분할]
http://www.lydsy.com/JudgeOnline/problem.php?id=2243
와 조 는 오전 내 내......................................................................
Code:
#include<cstdio>
#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
using namespace std;
const int maxn=1e5+5;
int top[maxn],fa[maxn],dep[maxn],son[maxn],siz[maxn],w[maxn],z=0;
vector<int>G[maxn];
int n,m,root=1;
int c[maxn],col[maxn];
int U[maxn],V[maxn];
void add(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
struct node{
int l,r,sum,lazy;
node(){
l=-1;r=-1;sum=0,lazy=-1;
}
node(int _l,int _r,int _sum){
l=_l;r=_r;sum=_sum;
}
};
node operator+(node a,node b){
if(a.sum==0)return b;
if(b.sum==0)return a;
node res;
res.l=a.l;
res.r=b.r;
res.sum=a.sum+b.sum-(a.r==b.l);
return res;
}
struct seg_tree{
node t[maxn<<2];
/*void build(int i,int l,int r){
if(l>r)return;
if(l==r){
t[i].l=t[i].r=c[l];
t[i].sum=1;
}
int mid=(l+r)>>1;
build(lson);build(rson);
t[i]=t[L]+t[R];
}*/
void pushdown(int i){
if(t[i].lazy==-1)return;
t[L].l=t[L].r=t[R].l=t[R].r=t[i].lazy;
t[L].sum=t[R].sum=1;
t[L].lazy=t[R].lazy=t[i].lazy;
t[i].lazy=-1;
}
void updata(int i,int l,int r,int l0,int r0,int c){
if(l>r)return;
if(l0<=l&&r0>=r){
t[i].l=t[i].r=c;
t[i].sum=1;
t[i].lazy=c;
//if(l0==l&&r0==r)t[i].lazy=-1;
return;
}
int mid=(l+r)>>1;
pushdown(i);
if(l0<=mid)updata(lson,l0,r0,c);
if(r0>mid)updata(rson,l0,r0,c);
t[i].l=t[L].l;
t[i].r=t[R].r;
t[i].sum=t[L].sum+t[R].sum-(t[L].r==t[R].l&&t[L].r!=-1);
}
node query(int i,int l,int r,int l0,int r0){
if(l>r)return node(-1,-1,0);
if(l0<=l&&r0>=r)return t[i];
int mid=l+r>>1;
pushdown(i);
if(r0<=mid)return query(lson,l0,r0);
if(l0>mid)return query(rson,l0,r0);
return query(lson,l0,mid)+query(rson,mid+1,r0);
}
}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];
if(v!=fa[u]){
fa[v]=u;
dep[v]=dep[u]+1;
dfs(v);
if(siz[v]>siz[son[u]])son[u]=v;
siz[u]+=siz[v];
}
}
}
void build(int u,int tp){
w[u]=++z;top[u]=tp;
if(son[u]!=0)build(son[u],tp);
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v!=son[u]&&v!=fa[u])
build(v,v);
}
}
void change(int u,int v,int c){
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.updata(1,1,n,a,b,c);
u=fa[top[u]];
}else{
int a=w[v],b=w[top[v]];
if(a>b)swap(a,b);
T.updata(1,1,n,a,b,c);
v=fa[top[v]];
}
}
if(w[u]<w[v])
T.updata(1,1,n,w[u],w[v],c);
else
T.updata(1,1,n,w[v],w[u],c);
}
int query(int u,int v){
node Left,Right,ans;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
int a=w[u],b=w[top[u]];
ans=T.query(1,1,n,min(a,b),max(a,b));
if(a>b)swap(ans.l,ans.r);
Left=Left+ans;
u=fa[top[u]];
}else{
int a=w[v],b=w[top[v]];
ans=T.query(1,1,n,min(a,b),max(a,b));
if(a<b)swap(ans.l,ans.r);
Right=ans+Right;
v=fa[top[v]];
}
}
ans=T.query(1,1,n,min(w[u],w[v]),max(w[u],w[v]));
if(w[u]>w[v])swap(ans.l,ans.r);
Left=Left+ans;
return (Left+Right).sum;
}
void deb(){
//DEB
for(int i=1;i<=14;i++)
printf("#%d l:%d r:%d sum:%d lazy:%d
",i,T.t[i].l,T.t[i].r,T.t[i].sum,T.t[i].lazy);
//end DEB
}
int main(){
freopen("1.txt","r",stdin);
freopen("3.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);U[i]=u;V[i]=v;
}
dep[root]=1;
dfs(root);build(root,root);
for(int i=1;i<=n;i++)
change(i,i,c[i]);//,deb();
char opt[5];
while(m--){
scanf("%s",opt);
if(opt[0]=='Q'){
int u,v;
scanf("%d%d",&u,&v);
printf("%d
",query(u,v));
}else{
int u,v,C;
scanf("%d%d%d",&u,&v,&C);
change(u,v,C);
}//deb();
}
return 0;
}
데이터 생 성기:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
int main(){
freopen("1.txt","w",stdout);
srand(time(0));
int n=10,m=10;
cout<<n<<" "<<m<<endl;
for(int i=1;i<=n;i++)
cout<<rand()%3<<" ";
cout<<endl;
for(int i=2;i<=n;i++){
int u=i;
int v=rand()%u+1;
if(u==v){
i--;
continue;
}
cout<<u<<" "<<v<<endl;
}
while(m--){
if(rand()%2){
int a=rand()%n+1,b=rand()%n+1,c=rand()%3;
cout<<'C';
cout<<" "<<a<<" "<<b<<" "<<c<<endl;
}
else{
cout<<'Q';
cout<<" "<<rand()%n+1<<" "<<rand()%n+1<<endl;
}
}
return 0;
}
대조 bat:
@echo off
:loop
pai.exe
2.exe
3.exe
fc 2.txt 3.txt
if %errorlevel%==0 goto loop
pause
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.