libreoj 6270 数据结构板子题 题解

发表于 | 阅读次数：
本文字数： 801 字 | 阅读时长 ≈ 4 分钟

题意简述

给定 $n$ 个区间 $[l_i,r_i]$，和 $Q$ 个询问，每次给你三个整数 $[l,r,k]$，求被 $[l,r]$ 完全包含且长度 $\ge k$ 的区间数量。

注：定义一个区间 $[l,r]$ 的长度是 $r-l$。

$n,q\le 10^6$，$1\le l_i,r_i,l,r,k\le n$，$l_i<r_i,l<r$

思路

如果没有 $k$ 的限制，只是要求完全包含的区间数量，可以用两个树状数组，然后计算右端点在 $[1,r]$ 中的数量减去左端点在 $[1,l-1]$ 中的数量。

然后现在有了 $k$ 的限制，我们把一个询问拆成 $[l,r,r-l]$ 减去 $[l,r,k-1]$。然后把询问和区间都按长度排序，一个一个处理即可。还有就是记录一下这个答案属于第几个询问，带正号还是带负号

（$[l,r,r-l]$ 带正号，$[l,r,k-1]$ 带负号，看上面答案是怎么算的）

然后就做完了。

代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 1666666
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
	#define p_b push_back
	#define sz(a) ((int)a.size())
	#define iter(a,p) (a.begin()+p)
	int I()
	{
	    int x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    return (x=(f==1)?x:-x);
	}
	void Rd(int cnt,...)
	{
	    va_list args; va_start(args,cnt);
	    F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
	    va_end(args);
	}
	class BIT
	{
	public:
	    int tree[N],len;
	    void Build(int _len) {FK(tree); len=_len;}
	    void Add(int pos,int x)
	    {
	        while(pos<=len) tree[pos]+=x,pos+=(pos&(-pos));
	    }
	    int Query(int pos)
	    {
	        int ans=0;
	        while(pos>0) ans+=tree[pos],pos-=(pos&(-pos));
	        return ans;
	    }
	}L,R;
	struct seg{int l,r;}a[N]; bool operator<(seg a,seg b){return a.r-a.l<b.r-b.l;}
    // 给定的线段，按长度排序
	struct que{int l,r,k,id,tp;}q[N]; bool operator<(que a,que b){return a.k<b.k;}
	// 询问，也是按长度排序
    
	int n,m; int cnt=0;
	void Input()
	{
		Rd(2,&n,&m);
		F(i,1,n) {a[i].l=I(); a[i].r=I();}
		F(i,1,m) 
		{
			int l,r,k; Rd(3,&l,&r,&k);
			if (k>r-l) continue;
			q[++cnt]=(que){l,r,r-l,i,1}; // 记录编号和符号
			q[++cnt]=(que){l,r,k-1,i,-1};
		}
	}

	int ans[N];
	void Soviet()
	{	
		sort(a+1,a+n+1); sort(q+1,q+cnt+1);
		L.Build(n); R.Build(n); // 两颗树状数组，记录左端点和右端点

		int pos=1;
		F(i,1,cnt)
		{
			while(pos<=n and a[pos].r-a[pos].l<=q[i].k) 
			{
				L.Add(a[pos].l,1); R.Add(a[pos].r,1); ++pos;
			}
			ans[q[i].id]+=q[i].tp*(R.Query(q[i].r)-L.Query(q[i].l-1));
		} 
		F(i,1,m) printf("%d\n",ans[i]); 
	}

	#define Flan void
	Flan IsMyWife()
	{
		Input();
		Soviet();
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w