[supplementary question] 2021 Niuke summer multi school training camp 9-N

E.Eyjafjalla

The question ：

Give me a tree ,q A query , Each query gives (u, l, r) Represents the virus in u Point burst , stay [l, r] The temperature of can spread

The root node is 1, Ensure that you are closer to the root node , Higher temperature , The root node temperature is the highest .

Ideas ：

For any node , The temperature of its parent node increases （ Are bigger than it ）, The temperature of the child nodes decreases （ All smaller than it ）. Because the parent node temperature increases , So it can be multiplied logn The temperature found is less than or equal to r The largest parent node of x, At this point, the problem turns into , stay x And its subtree l Number of nodes of temperature .

First according to dfs Xu Jian n A chairman tree , Multiply and find x, Again

Law 1： Two points + Interval No k Big (nlognlogn)： The second of the interval k Large values are monotonic , Two points find the first k Great value , Make it the smallest interval greater than l Of the k Big ,ans=size[x]-k+1

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int q,n,tot,tim,len,root[maxn],a[maxn],b[maxn],c[maxn],L[maxn],R[maxn],fa[maxn][25];
vector<int>mp[maxn];
struct node{
    
	int l,r,val;
}tr[maxn*4+maxn*17];//log(1e5)=17
int build(int l,int r){
    
	int rt=++tot;
	if(l==r)return tot;
	int mid=(l+r)>>1;
	tr[rt].l=build(l,mid);
	tr[rt].r=build(mid+1,r);
	return rt;
}
int update(int pre,int l,int r,int x){
    
	int now=++tot;
	tr[now]=tr[pre];
	if(l==r){
    
		tr[now].val++;
		return now;
	}
	int mid=(l+r)>>1;
	if(x<=mid)tr[now].l=update(tr[pre].l,l,mid,x);
	else tr[now].r=update(tr[pre].r,mid+1,r,x);
	tr[now].val=tr[tr[now].l].val+tr[tr[now].r].val;
	return now;
}
int query(int last,int first,int l,int r,int k){
    
	if(l==r)return r;
	int mid=(l+r)>>1,cha=tr[tr[last].l].val-tr[tr[first].l].val;
	if(k<=cha)return query(tr[last].l,tr[first].l,l,mid,k);
	else return query(tr[last].r,tr[first].r,mid+1,r,k-cha);
}
void dfs(int x,int f){
    
	++tim;
	root[tim]=update(root[tim-1],1,len,c[x]);
	
	L[x]=tim;
	for(auto y:mp[x]){
    
		if(y==f)continue;
		dfs(y,x);
		fa[y][0]=x;
	}
	R[x]=tim;
}

int main(){
    
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++){
    
		scanf("%d%d",&x,&y);
		mp[x].push_back(y),mp[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)c[i]=lower_bound(b+1,b+1+n,a[i])-b;
	root[0]=build(1,len);
	dfs(1,0);
	for(int i=1;i<=20;i++)
	    for(int j=1;j<=n;j++)
	        fa[j][i]=fa[fa[j][i-1]][i-1];
	scanf("%d",&q);
	while(q--){
    
		int d,s,t;
		scanf("%d%d%d",&d,&s,&t);
		if(a[d]<s||a[d]>t){
    
			printf("0\n");
			continue;
		}
		for(int i=20;i>=0;i--){
    
			if(fa[d][i]&&a[fa[d][i]]<=t)d=fa[d][i];
		}
		s=lower_bound(b+1,b+1+len,s)-b;
		t=lower_bound(b+1,b+1+len,t)-b;
		int l=1,r=R[d]-L[d]+1,ans=0,sum=R[d]-L[d]+1;
		while(l<=r){
    
			int mid=(l+r)>>1;
			int bat=query(root[R[d]],root[L[d]-1],1,len,mid);// It means the first one mid Large number  
			if(bat<s)l=mid+1;
			else ans=mid,r=mid-1;
		}
		printf("%d\n",sum-ans+1);
	}
}

Law 2： Directly find the interval greater than l The number of （nlogn）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int q,n,tot,tim,len,root[maxn],a[maxn],b[maxn],c[maxn],L[maxn],R[maxn],fa[maxn][25];
vector<int>mp[maxn];
struct node{
    
	int l,r,val;
}tr[maxn*4+maxn*17];//log(1e5)=17
int build(int l,int r){
    
	int rt=++tot;
	if(l==r)return tot;
	int mid=(l+r)>>1;
	tr[rt].l=build(l,mid);
	tr[rt].r=build(mid+1,r);
	return rt;
}
int update(int pre,int l,int r,int x){
    
	int now=++tot;
	tr[now]=tr[pre];
	if(l==r){
    
		tr[now].val++;
		return now;
	}
	int mid=(l+r)>>1;
	if(x<=mid)tr[now].l=update(tr[pre].l,l,mid,x);
	else tr[now].r=update(tr[pre].r,mid+1,r,x);
	tr[now].val=tr[tr[now].l].val+tr[tr[now].r].val;
	return now;
}
int query(int pre,int now,int l,int r,int k){
    
	if(l==r)return tr[now].val-tr[pre].val;
	int mid=(l+r)>>1,cha=tr[tr[now].r].val-tr[tr[pre].r].val;
	if(k<=mid)return query(tr[pre].l,tr[now].l,l,mid,k)+cha;
	else return query(tr[pre].r,tr[now].r,mid+1,r,k);
}
void dfs(int x,int f){
    
	++tim;
	root[tim]=update(root[tim-1],1,len,c[x]);
	
	L[x]=tim;
	for(auto y:mp[x]){
    
		if(y==f)continue;
		dfs(y,x);
		fa[y][0]=x;
	}
	R[x]=tim;
}

int main(){
    
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++){
    
		scanf("%d%d",&x,&y);
		mp[x].push_back(y),mp[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)c[i]=lower_bound(b+1,b+1+n,a[i])-b;
	root[0]=build(1,len);
	dfs(1,0);
	for(int i=1;i<=20;i++)
	    for(int j=1;j<=n;j++)
	        fa[j][i]=fa[fa[j][i-1]][i-1];
	scanf("%d",&q);
	while(q--){
    
		int d,s,t;
		scanf("%d%d%d",&d,&s,&t);
		if(a[d]<s||a[d]>t){
    
			printf("0\n");
			continue;
		}
		for(int i=20;i>=0;i--){
    
			if(fa[d][i]&&a[fa[d][i]]<=t)d=fa[d][i];
		}
		s=lower_bound(b+1,b+1+len,s)-b;
		t=lower_bound(b+1,b+1+len,t)-b;
		//int l=1,r=R[d]-L[d]+1,ans=0,sum=R[d]-L[d]+1;
		printf("%d\n",query(root[L[d]-1],root[R[d]],1,len,s));
	}
}

Law 3： offline + Tree heuristic + Tree array

#include<cstdio>
constexpr int N = 1e5 + 5;
int n, dn = 3e5;
int T[N], c[N * 3], son[N], siz[N];
int ans[N], l[N], r[N], tt[N << 2];
int fa[N][20];
bool go[N];
vector<int> vt[N], id[N];
int lowbit(int x) {
    
    return x & -x;
}
void add(int x, int v) {
    
    while(x <= dn) {
    
        c[x] += v;
        x += lowbit(x);
    }
}
int ask(int x) {
    
    int ret = 0;
    while(x) {
    
        ret += c[x];
        x -= lowbit(x);
    }
    return ret; 
}
void dfs(int u, int f) {
    
    fa[u][0] = f;
    for(int i = 1; i < 20; ++i) {
    
    	fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	siz[u] = 1;
    for(int v : vt[u]) {
    
        if(v == f)  continue;
        dfs(v, u);
        siz[u] += siz[v];
        if(son[u] == 0 || siz[son[u]] < siz[v]) son[u] = v;
    }
}
int fd(int u, int up) {
    
	for(int i = 19; i >= 0; --i) {
    
        if(T[fa[u][i]] <= up)  u = fa[u][i];
    }
    return u;
}
void dfs3(int u, int f) {
    
    add(T[u], -1);
    for(int v : vt[u]) {
    
        if(v != f)  dfs3(v, u);
    }
}
void dfs2(int u, int f, bool vis) {
    
    for(int v : vt[u]) {
    
        if(v == f || v == son[u])  continue;
        dfs2(v, u, 0);
    }
    if(son[u])  dfs2(son[u], u, 1);
    for(int v : vt[u]) {
    
        if(v == f || v == son[u])  continue;
        dfs2(v, u, 1);
    }
    add(T[u], 1);
    if(go[u] == 0)
    for(int v : id[u]) {
    
		go[u] = 1;
        int L = l[v], R = r[v];
        ans[v] = ask(R) - ask(L - 1);
	}
    if(!vis) dfs3(u, f);
}

int main() {
    
    scanf("%d", &n);
    for(int i = 1, u, v; i < n; ++i) {
    
        scanf("%d%d", &u, &v);
        vt[u].push_back(v);
        vt[v].push_back(u);        
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i)  scanf("%d", &T[i]), tt[++cnt] = T[i];
    dfs(1, 1);
    int q, x;
    scanf("%d", &q);
    for(int i = 1; i <= q; ++i) {
    
        scanf("%d%d%d", &x, &l[i], &r[i]);
        tt[++cnt] = l[i];
        tt[++cnt] = r[i];
        if(T[x] < l[i] || T[x] > r[i])  continue;
        int gf = fd(x, r[i]);
        id[gf].push_back(i);
    }
    sort(tt + 1, tt + 1 + cnt);
    int len = unique(tt + 1, tt + 1 + cnt) - tt - 1;    dn = len;
    for(int i = 1; i <= n; ++i)  T[i] = lower_bound(tt + 1, tt + len + 1, T[i]) - tt;
    for(int i = 1; i <= q; ++i) {
    
        l[i] = lower_bound(tt + 1, tt + 1 + len, l[i]) - tt;
        r[i] = lower_bound(tt + 1, tt + 1 + len, r[i]) - tt;
    } 
    dfs2(1, 0, 1);
    for(int i = 1; i <= q; ++i)  printf("%d\n", ans[i]);
}