LOJ \ # 2116 Luogu P3241 "HNOI 2015" 오픈
보충한다
역시 글 을 쓸 때 생각 이 혼 란 스 러 워 서...
LOJ #2116 Luogu P3241
제목
$Q $회 질문, 트 리 의 색상 이 $[L, R] $의 모든 지점 에서 질문 지점 까지 의 거 리 를 구 합 니 다. 강제 온라인
횟수 문의, 트 리 포인트 약 $2 · 10 ^ 5 $
$ Solution$
먼저
$ dist(x,y)=deep(x)+deep(y)-2·deep(lca(x,y))$
분명히 이 등식 의 앞 두 가 지 는 접두사 와 어떤 것 으로 유지 하기 쉽다.
세 번 째 만 생각하면 변 권 이 있 고 온라인 을 강제 하 는 LNOI 2014 LCA 에 해당 합 니 다.
같은 방법 으로 $deep (lca (x, y) $를 모든 구간 에 있 는 점 으로 바 꾸 고 루트 구간 에 추가 합 니 다.
그리고 질문 점 에서 루트 까지 의 거 리 를 조회 합 니 다.
모든 점 을 색 으로 정렬 합 니 다. 나무 쪼 개 기 + 주석 나무 유지 보수
현재 색상 의 가장 작은 점 을 주석 트 리 에 삽입 할 때마다 최대 영향 $log ^ 2 $개 선분
태그 영구 화 필요
글 을 쓸 때 생각 이 잘 안 나 서 가짜 주석 트 리 를 쓴 것 같 아 요.
$my \ code$
#include
#include
#include
#include
#include
#include
#include
#include
#define M 150010
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x=0;char zf=1;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-1,ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('
');}
int k,m,n,x,y,z,cnt,ans;
int dfn[M],top[M],size[M],fa[M],to[M];ll deep[M];
vectorint,int>>e[150010];
void dfs(int x,int pre){
size[x]=1;fa[x]=pre;
for(auto i:e[x])if(i.first!=pre){
deep[i.first]=deep[x]+i.second;
dfs(i.first,x);size[x]+=size[i.first];
}
}
void dfs2(int x,int chain){
int heavy=0;dfn[x]=++cnt;top[x]=chain;to[cnt]=x;
for(auto i:e[x])if(size[i.first]>size[heavy]&&i.first!=fa[x])heavy=i.first;
if(!heavy)return;
dfs2(heavy,chain);
for(auto i:e[x])if(i.first!=heavy&&i.first!=fa[x])dfs2(i.first,i.first);
}
struct segment{
int ls,rs,tag;ll sum;
}a[10000010];
int Root[150010];
#define up a[x].sum=(ll)a[a[x].ls].sum+a[a[x].rs].sum+(ll)a[x].tag*(deep[to[R]]-deep[fa[to[L]]])
void change(int x,int L,int R,int LL,int RR){
const int mid=L+R>>1;
if(L>=LL&&R<=RR){
a[x].tag++;
up;return;
}
if(mid>=LL){
if(a[x].ls)a[cnt+1]=a[a[x].ls];
change(a[x].ls=++cnt,L,mid,LL,RR);
}
if(mid+1<=RR){
if(a[x].rs)a[cnt+1]=a[a[x].rs];
change(a[x].rs=++cnt,mid+1,R,LL,RR);
}
up;
}
ll query(int x,int LL,int RR,int L,int R,int cs){
if(!x)x=++cnt;if(LL>R||RRreturn 0;
if(LL>=L&&RR<=R)return a[x].sum+(ll)cs*(deep[to[RR]]-deep[fa[to[LL]]]);
const int mid=LL+RR>>1;
return query(a[x].ls,LL,mid,L,R,cs+a[x].tag)+query(a[x].rs,mid+1,RR,L,R,cs+a[x].tag);
}
void upd(int id,int x){
while(x){
change(Root[id],1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
}
ll query(int id,int x){
if(!id)return 0;
ll ans=0;
while(x){
ans+=query(Root[id],1,n,dfn[top[x]],dfn[x],0);
x=fa[top[x]];
}
return ans;
}
struct peri{
int x,id;
bool operator const peri s){
return x<s.x;
}
}q[200010];
ll s[150010];
int main(){
n=read();m=read();int A=read();
for(rt i=1;i<=n;i++)q[i].x=read(),q[i].id=i;
sort(q+1,q+n+1);fa[1]=0;
for(rt i=2;i<=n;i++){
x=read();y=read();z=read();
e[x].push_back({y,z});e[y].push_back({x,z});
}
dfs(1,0);dfs2(1,1);cnt=0;
for(rt i=1;i<=n;i++)s[i]=s[i-1]+deep[q[i].id];// i deep
for(rt i=1;i<=n;i++){
Root[i]=++cnt;
a[Root[i]]=a[Root[i-1]];
upd(i,q[i].id);
}
ll las=0;
while(m--){
z=read();int aa=read(),bb=read();
int L=min((aa+las)%A,(bb+las)%A);
int R=max((aa+las)%A,(bb+las)%A);
L=lower_bound(q+1,q+n+1,(peri){L,0})-q;
R=lower_bound(q+1,q+n+1,(peri){R+1,0})-q-1;
las=(ll)(R-L+1)*deep[z]+s[R]-s[L-1]-(query(R,z)-query(L-1,z))*2;
writeln(las);
}
return 0;
}
다음으로 전송:https://www.cnblogs.com/DreamlessDreams/p/10145790.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.