1- SDOI 染色
给定一棵有 n 个节点的无根树和 m 个操作，操作共两类。
将节点 a 到节点 b 路径上的所有节点都染上颜色；
询问节点 a 到节点 b 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221 由三段组成：11 、 222、1。
请你写一个程序依次完成操作。
分析：合并两个区间时，如果左区间的右端点等于右区间的左端点，那么color【u】=color【lson】+color【rson】-1，否则直接加。所以记录每一个区间的左和右，合并时直接判断。
代码：
#include<bits/stdc++.h>
#define M 100005
#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
using namespace std;
int bok,n,m,pr[M*5],h[M*2],cnt,ct,siz[M],son[M],fa[M],dep[M],topf[M],id[M],sm[M*5],lazy[M*5],res,co[M],lc[M*5],rc[M*5];
inline int gi(){
int re=0,f=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')f=0,c=getchar();
while(c>='0'&&c<='9')re=re*10+c-'0',c=getchar();
return f?re:-re;
}
struct ee{
int t,nxt;
}e[M*2];
void add(int fr,int t){
e[++ct].t=t;
e[ct].nxt=h[fr];
h[fr]=ct;
}
void dfs1(int u,int ff,int dp){
dep[u]=dp;
siz[u]=1;
fa[u]=ff;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].t;
if(v!=ff){
dfs1(v,u,dp+1);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
}
void dfs2(int u,int top){
++cnt;
id[u]=cnt;
pr[cnt]=co[u];
topf[u]=top;
if(!son[u])return;
dfs2(son[u],top);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].t;
if(v!=fa[u]&&v!=son[u]){
dfs2(v,v);
}
}
}
void built(int k,int l,int r){
if(l==r){
lc[k]=rc[k]=pr[l];
sm[k]=1;
return;
}
built(lson);
built(rson);
lc[k]=lc[k<<1];
rc[k]=rc[k<<1|1];
sm[k]=sm[k<<1]+sm[k<<1|1]-(rc[k<<1]==lc[k<<1|1]);
}
void pushdown(int k,int len){
lazy[k<<1|1]=lazy[k<<1]=lazy[k];
sm[k<<1]=1;
sm[k<<1|1]=1;//****1
lc[k<<1]=rc[k<<1|1]=lazy[k];
rc[k<<1]=lc[k<<1|1]=lazy[k];
lazy[k]=0;
}
void upd(int k,int l,int r,int L,int R,int chang){
if(L<=l&&R>=r){
lc[k]=rc[k]=chang;
sm[k]=1;
lazy[k]=chang;return;
}
if(lazy[k])
pushdown(k,r-l+1);
if(L<=mid)//***
upd(lson,L,R,chang);
if(R>mid)//***
upd(rson,L,R,chang);
lc[k]=lc[k<<1];
rc[k]=rc[k<<1|1];
sm[k]=sm[k<<1]+sm[k<<1|1]-(rc[k<<1]==lc[k<<1|1]);
}
void query(int k,int l,int r,int L,int R){
if(L<=l&&R>=r){
res+=sm[k];
return;
}
if(lazy[k])
pushdown(k,r-l+1);
if(L<=mid)
query(lson,L,R);
if(R>mid)//***
query(rson,L,R);
res-=(L<=mid&&R>mid&&rc[k<<1]==lc[k<<1|1]);
}
void query2(int k,int l,int r,int L,int R){
if(l==r){
bok=lc[k];
return;
}
if(lazy[k])
pushdown(k,r-l+1);
if(L<=mid)
query2(lson,L,R);
if(R>mid)//***
query2(rson,L,R);
}
void wk1(int a,int b,int c){
while(topf[a]!=topf[b]){
if(dep[topf[a]]>dep[topf[b]])
swap(a,b);
upd(1,1,n,id[topf[b]],id[b],c);
b=fa[topf[b]];
}
if(dep[a]>dep[b])swap(a,b);
upd(1,1,n,id[a],id[b],c);
}
void wk2(int a,int b){
res=0;
while(topf[a]!=topf[b]){
if(dep[topf[a]]>dep[topf[b]])
swap(a,b);
query(1,1,n,id[topf[b]],id[b]);
int b1,b2;
query2(1,1,n,id[topf[b]],id[topf[b]]),b1=bok;
query2(1,1,n,id[fa[topf[b]]],id[fa[topf[b]]]),b2=bok;
if(b1==b2)--res;
b=fa[topf[b]];
}
if(dep[a]>dep[b])swap(a,b);
query(1,1,n,id[a],id[b]);
printf("%d
",res);
}
int main(){
n=gi();m=gi();
for(int i=1;i<=n;i++)
co[i]=gi();
for(int i=1;i<n;i++){
int u=gi(),v=gi();
add(u,v);
add(v,u);
}
dfs1(1,0,1);
dfs2(1,1);
built(1,1,n);
char op;
for(int i=1;i<=m;i++){
cin>>op;
if(op=='C'){
int a,b,c;
a=gi();b=gi();c=gi();
wk1(a,b,c);
}else{
int a,b;
a=gi();b=gi();
wk2(a,b);
}
}
}
2- Tree
wls 有一棵树，树上每个节点都有一个值 ai，现在有 2 种操作：
- 将一条链上的所有节点的值开根号向下取整；
- 求一条链上值的和；
链的定义是两点之间的最短路。
分析：一个数最多被根4/5次，所以开方的时候直接开方，但是如果发现该区间的sum等于该区间长度就说明不用开了。
代码：
#include<bits/stdc++.h>
#define M 100005
#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define ll long long
#define rson k<<1|1,mid+1,r
using namespace std;
int n,m,pr[M*5],h[M*2],cnt,ct,siz[M],son[M],fa[M],dep[M],topf[M],id[M],sf[M];
ll sum[M*5],co[M*5],res;
inline int gi(){
int re=0,f=1;
char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')f=0,c=getchar();
while(c>='0'&&c<='9')re=re*10+c-'0',c=getchar();
return f?re:-re;
}
struct ee{
int t,nxt;
}e[M*2];
void add(int fr,int t){
e[++ct].t=t;
e[ct].nxt=h[fr];
h[fr]=ct;
}
void dfs1(int u,int ff,int dp){
dep[u]=dp;
siz[u]=1;
fa[u]=ff;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].t;
if(v!=ff){
dfs1(v,u,dp+1);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
}
void dfs2(int u,int top){
++cnt;
id[u]=cnt;
topf[u]=top;
sf[cnt]=pr[u];
if(!son[u])return;
dfs2(son[u],top);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].t;
if(v!=fa[u]&&v!=son[u]){
dfs2(v,v);
}
}
}
void built(int k,int l,int r){
if(l==r){
co[k]=sf[l];
return;
}
built(lson);
built(rson);
co[k]=co[k<<1]+co[k<<1|1];
}
void upd(int k,int l,int r,int L,int R){
if(co[k]==r-l+1)return;
if(l==r){
co[k]=(long long)(sqrt(co[k]));
// cout<<"wk1!"<<l<<" "<<r<<" "<<co[k]<<endl;
return;
}
if(L<=mid)//***
upd(lson,L,R);
if(R>mid)//***
upd(rson,L,R);
co[k]=co[k<<1]+co[k<<1|1];
// cout<<"wk1"<<l<<" "<<r<<" "<<co[k]<<endl;
}
void wk1(int a,int b){
while(topf[a]!=topf[b]){
if(dep[topf[a]]>dep[topf[b]])
swap(a,b);
upd(1,1,n,id[topf[b]],id[b]);
b=fa[topf[b]];
}
if(dep[a]>dep[b])swap(a,b);
upd(1,1,n,id[a],id[b]);
}
void query(int k,int l,int r,int L,int R){
// cout<<"Q"<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
if(l>=L&&r<=R){
// cout<<l<<"&"<<r<<endl;
res+=co[k];
return;
}
if(L<=mid)//***
query(lson,L,R);
if(R>mid)//***
query(rson,L,R);
}
void wk2(int a,int b){
res=0;
// cout<<"2!"<<a<<" "<<b<<endl;
while(topf[a]!=topf[b]){
if(dep[topf[a]]>dep[topf[b]])
swap(a,b);
query(1,1,n,id[topf[b]],id[b]);
b=fa[topf[b]];
}
if(dep[a]>dep[b])swap(a,b);
query(1,1,n,id[a],id[b]);
printf("%lld
",res);
}
int main(){
n=gi();m=gi();
for(int i=1;i<=n;i++)scanf("%d",&pr[i]);
for(int i=1;i<n;i++){
int u=gi(),v=gi();
add(u,v);
add(v,u);
}
dfs1(1,0,1);
dfs2(1,1);
built(1,1,n);
int op;
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(!op){
int a,b;
a=gi();b=gi();
wk1(a,b);
}else{
int a,b;
a=gi();b=gi();
wk2(a,b);
}
}
return 0;
}
3- Codechef：Dynamic GCD
------------恢复内容结束------------