동태 점 분할 치료 에 관 한 간단 한 이야기.

동태 점 분할 치료 에 관 한 간단 한 이야기.
선행 지식
동태 적 인 분 치 를 배우 기 전에 분 치 를 하거나 분 치 를 할 줄 아 는 사상 이 있어 야 합 니 다. 여기 제 가 점 에 대한 설명 이 있 습 니 다. 링크 입 니 다.그 다음으로 동태 적 인 분 치 를 배 우려 면 한 걸음 으로 배척 하 는 사상 이 필요 하 다.
평론
우 리 는 점 치 로 할 수 있 는 문제 의 특성 을 고려 했다. 이 문 제 는 수정 할 수 없다.그러면 수정 해 야 할 나무의 문제 에 대해 우 리 는 동태 적 인 분 치 를 고려 할 수 있다.
무엇이 동태 점 분 치 입 니까?동적 점 분 치 는 데이터 구 조 를 활용 하여 트 리 에 있 는 정 보 를 유지 하 는 것 이다.여기에 분수 라 는 개념 이 언급 되 었 다.점 분 수 는 우리 가 점 분 치 를 통 해 구 한 모든 중심 사 이 를 연결 한 후에 얻 은 나무 이다.이 나 무 는 중점 과 점 사이 가 모두 인접 층 의 중심 이기 때문에 분명히 이 나 무 는 $log $층 밖 에 없다. 왜냐하면 이 성질 이 매우 우수 하기 때문에 우 리 는 매번 점수 에서 폭력 적 으로 위로 뛰 어 올 라 답 을 통계 할 수 있다.
답 을 어떻게 통계 할 것 인 가 를 고려 하여 우 리 는 먼저 예 제 를 살 펴 보 자. 링크.
제목 설명: 한 땅 에 N 개의 도시 가 있 는데 N - 1 개의 무방 향 변 을 통 해 서로 연결 되 어 한 그루 의 나무의 구 조 를 형성 하고 두 도시 와 인접 한 거 리 는 1 이 며 그 중에서 i 번 째 도시 의 가 치 는 value [i] 이다.불 행 히 도 이 땅 은 지진 이 자주 발생 하고 시대 의 발전 에 따라 도시 의 가치 도 변동 이 생 긴 다.다음은 온라인 으로 M 차 작업 을 처리 해 야 합 니 다.
0 x k 는 지진 이 발생 했 고 진앙 도 시 는 x 이 며 영향 범 위 는 k 이 며 x 와 거리 가 k 를 초과 하지 않 는 모든 도시 가 영향 을 받 을 것 이 며 이번 지진 으로 인 한 경제적 손실 은 모든 영향 을 받 는 도시 의 가치 와 가 치 를 나타 낸다.
1 x y 는 x 번 째 도시 의 가치 가 y 로 변 했다 는 것 을 나타 낸다.
프로그램의 선형 을 나타 내기 위해 서 는 작업 중의 x, y, k 가 모두 다른 것 이나 프로그램 이 지난번 에 진 것 을 복호화 해 야 합 니 다. 만약 에 이전에 출력 이 없 었 다 면 기본 적 인 출력 은 0 입 니 다.
우 리 는 현재 의 나무 구조 점 에 대해 나 무 를 나눈다. 이 부분의 코드 는 매우 간단 하 다. 바로 점 분할 의 코드 이다.

inline void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
inline void dfs(int p,int from)
{
    dep[p]=dep[from]+1,pos[p]=++tot,f[0][tot]=dep[p];
    for(register int i=head[p];i;i=nxt[i]) if(to[i]!=from)
        dfs(to[i],p),f[0][++tot]=dep[p];
}
inline int getdis(int x,int y)
{
    int tmp=dep[x]+dep[y];x=pos[x],y=pos[y];
    if(x>y) swap(x,y); int k=lg[y-x+1];
    return tmp-(min(f[k][x],f[k][y-(1<>1]+1;
    for(register int i=1;(1< 
 

이 부분의 코드 와 점 분 치 의 차 이 는 $dfs 2 $에서 점 분 치 된 할당 아버지 가 조작 하 는 것 입 니 다.뒤에 거 리 를 사용 해 야 하기 때문에 코드 에 $lca $배가 배열 을 초기 화 하 는 부분 이 있 습 니 다.
우 리 는 거리 와 거 리 를 어떻게 구 하 는 지 를 고려 합 니 다. 우 리 는 점수 에 있 는 모든 점 에 하나의 선분 수 를 놓 습 니 다. 이 선분 수의 모든 노드 는 점수 에 현재 노드 를 뿌리 로 하 는 서브 트 리 의 점 과 현재 노드 의 거 리 는 $[l, r] $범위 내의 점 권 과 같 습 니 다.이렇게 하면 우 리 는 라인 트 리 에서 현재 노드 를 뿌리 로 하 는 서브 트 리 에서 현재 노드 와 거리 가 $x $와 같은 점 권 과 얼마 인지 직접 찾 을 수 있 습 니 다.그러나 우 리 는 이렇게 하면 문제 가 생 길 수 있다 는 것 을 알 게 되 었 다. 우 리 는 반복 할 것 이다. 왜냐하면 한 점 이 현재 점 과 현재 점 의 조상 에 게 여러 번 계산 되 기 때문이다.이렇게 해서 우 리 는 한 걸음 으로 배척 할 것 을 고려한다.
우 리 는 점수 에 있 는 모든 노드 에 선분 수 를 한 그루 더 놓 습 니 다. 이 선분 수의 모든 노드 는 점수 에 현재 노드 를 뿌리 로 하 는 서브 트 리 의 점 과 현재 노드 가 점수 에 있 는 아버지의 거 리 는 $[l, r] $범위 내의 점 권 과 같 습 니 다.이렇게 하면 우 리 는 매번 한 번 만 배척 하면 된다. 아마도 내 가 묘사 한 것 이 잘 이해 되 지 않 을 것 이다. 아래 코드 를 관찰 하면 된다.

#include 
#include 
#include 
using namespace std;
#define N 100010
#define min(i,j) ((ij)?i:j)
#define O2 __attribute__((optimize("-O2")))
inline char nc()
{
    static char buf[1000000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int re=0; char f=0,ch=nc();
    while(!isdigit(ch)) {f|=(ch=='-'); ch=nc();}
    while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
    return f ? -re : re;
}
int n,m,f[18][N<<1],pos[N],mx[N],level[N],dis[N],size[N],num[N],num1[N],ans,lg[N<<1],cnt,tot; 
int root,all,dep[N],head[N],to[N<<1],nxt[N<<1],idx,times;bool vis[N];
int root1[N],root2[N],fa[N],son[N*35][2],sum[N*35];
inline void add(int a,int b) {nxt[++idx]=head[a],to[idx]=b,head[a]=idx;}
inline void dfs(int p,int from)
{
    dep[p]=dep[from]+1,pos[p]=++tot,f[0][tot]=dep[p];
    for(register int i=head[p];i;i=nxt[i])
        if(to[i]!=from) dfs(to[i],p),f[0][++tot]=dep[p];
}
inline int getdis(int x,int y)
{
    int tmp=dep[x]+dep[y];x=pos[x],y=pos[y];
    if(x>y) swap(x,y); int k=lg[y-x+1];
    return tmp-(min(f[k][x],f[k][y-(1<>1]+1;
    for(register int i=1;(1<>1,tmp=0;
    if(x<=mid) tmp+=find(son[p][0],l,mid,x,y);
    if(y>mid) tmp+=find(son[p][1],mid+1,r,x,y);
    return tmp;
}
inline void find(int x,int y)
{
    for(register int i=x;i;i=fa[i])
    {
        if(getdis(x,i)<=y) ans+=find(root1[i],0,dis[i]-1,0,y-getdis(x,i));
        if(fa[i]&&getdis(x,fa[i])<=y) ans-=find(root2[i],0,dis[fa[i]]-1,0,y-getdis(x,fa[i]));
    }
}
inline void change(int &p,int l,int r,int x,int y)
{
    if(!p) p=++cnt; sum[p]+=y;
    if(l==r) return; register int mid=(l+r)>>1;
    if(x<=mid) change(son[p][0],l,mid,x,y);
    else change(son[p][1],mid+1,r,x,y);
}
inline void change(int x,int y)
{
    for(register int i=x;i;i=fa[i])
    {
        change(root1[i],0,dis[i]-1,getdis(i,x),y-num[x]);
        if(fa[i]) change(root2[i],0,dis[fa[i]]-1,getdis(x,fa[i]),y-num[x]);
    } num[x]=y;
}
inline void lots_of_changes() {for(register int i=1;i<=n;i++) change(i,num1[i]);}
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n;i++) num1[i]=read();
    for(register int i=1,a,b;i