1.9 KiB

Raw Permalink Blame History

线段树查询

题目背景

对于 n^2 次对于所有区间的最值查询，居然有很多同学使用了线段树成功实现 O(n^2logn) 复杂度，可见大家对线段树的喜爱之情溢于言表。

题目描述

sophie写了一棵线段树，建树和查询部分的代码如下：

int tot = 0;
node* buildT(int l, int r){
	node *p = new node;
	p->l = l; p->r = r;
    p->t = ++tot;//dfs序
	if(l==r) return p;

	int mid = (l + r)/2;
	p->ls = buildT(l, mid);
	p->rs = buildT(mid+1, r);
	return p;
}
void query(node* p, int l, int r){
	if(p->l==l && p->r==r){
        //到达终止结点
		return;
	}
	
	int mid = (p->l + p->r)/2;
	if(r <= mid) query(p->ls, l, r);
	else if(l >= mid+1) query(p->rs, l, r);
	else{
        query(p->ls, l, mid);
        query(p->rs, mid+1, r);
	}
}

对序列 [1,n] 建完树之后，sophie在上面进行了所有 n(n+1)/2 次区间查询 $[l,r]$，即 $[1,1],[1,2],...,[n,n]$（成功通过了 n=500 的数据，获得12分！）

for(int l=1;l<=n;++l){
   for(int r=l;r<=n;++r){
      query(rt, l, r);
   }
}

现在sophie想知道，对于线段树上的一个节点，其在多少次查询中是终止节点。

输入格式

第一行1个整数 n,q

接下来 q 行，每行2个整数 t 代表询问线段树上dfs序为 t 的节点在多少次查询中是终止节点

输出格式

输出 q 行，每行1个整数代表答案

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

见下发样例

样例输出 #3

提示

对于所有数据，1\le n,q \le 10^6, 1\le t\le 2n-1

子任务1（20分）：n,q\le 1000

子任务2（20分）：n,q\le 10000

子任务3（60分）：无特殊限制

1.9 KiB Raw Permalink Blame History Unescape Escape