【补题】2021牛客暑期多校训练营9-n

E.Eyjafjalla

题意：

给出一棵树，q 个查询，每次查询给出 (u, l, r) 代表病毒在 u 点爆发，在 [l, r] 的温度可以传播

根节点为 1，保证离根节点越近，温度越高，根节点温度最高。

思路：

对于任意一节点，它的父节点的温度递增（都大于它），子节点的温度递减（都小于它）。因为父节点温度递增，所以可以倍增logn的找到小于等于温度r的最大的父节点x，此时问题转化为，在x及其子树下查询大于l温度的节点数。

先按照dfs序建n棵权值主席树，再倍增找到x，再

法1：二分+区间第k大(nlognlogn)：区间的第k大值具有单调性，二分找第k大值，使其是区间最小的大于l的第k大，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);//表示第mid大的数 
			if(bat<s)l=mid+1;
			else ans=mid,r=mid-1;
		}
		printf("%d\n",sum-ans+1);
	}
}

法2：直接找区间大于l的数的个数（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));
	}
}

法3：离线+树上启发式+树状数组

#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]);
}