Reincarnation

正因为梦易碎，才格外美好。

CF1045G AI robots

发表于 更新于 分类于
本文字数： 5.7k 阅读时长 ≈ 5 分钟

就这么不待见树套树？？？

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1045/G

形式化题意：有一根无限长的数轴，有 个点，坐标为 ，每一个点有一个二元参数 ，求出所有的无序二元组 满足 。

数据范围：

时空限制：

一种方法是将 映射到二维平面上，然后转化为二维数点问题，用 分治等方法来解决。但彩笔我不会 分治，就老老实实码了树套树。

第一层线段树维护这根数轴，即 维，每个结点维护一棵二层线段树记录 维，但都是 级别，所以进行离散化，第二层用动态开点。但即便如此，也需要 的结点数，需要 的空间，这是行不通的。

注意到 ，所以可以舍去 维并进行暴力计算，逆转一二层，第一层维护一棵动态线段树表示权值为 的点的数轴分布形态，则至多会存在 棵线段树。第二层维护数轴。但 不需要离散化的话，用 std::map 来记录一下即可。

空间复杂度 ，时间复杂度 。

AC Code
 
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
// ----- Eternally question-----
// Problem: G. AI robots
// Contest: Codeforces - Bubble Cup 11 - Finals [Online Mirror, Div. 1]
// URL: https://codeforces.com/problemset/problem/1045/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-01-26 15:36:29
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
const int MAXN=1e5+10;
const int INF=1e9;
int N,K,rL,rR,qL,qR;
std::vector<int>Nums;
std::vector<int>Iq;
struct Rob
{
	int x,r,q;
	bool operator<(const Rob &x) const
	{ return r>x.r; }
}a[MAXN];
int al[MAXN],ar[MAXN];
// int lq[MAXN],rq[MAXN];
std::map<int,int>Rt;
struct Segment
{
	#define ls(p) (Tr[p].lc)
	#define rs(p) (Tr[p].rc)
	int Idx;
	struct St
	{ int lc,rc,val; }Tr[MAXN*80];
	void modifyX(int &p,int l,int r,int x)
	{
		if(!p) p=++Idx;
		++Tr[p].val;
		if(l==r) return ;
		int mid=(l+r)>>1;
		if(x<=mid) modifyX(ls(p),l,mid,x);
		else modifyX(rs(p),mid+1,r,x);
	}
	int querySum(int p,int l,int r,int ql,int qr)
	{
		if((!p)||(ql>qr)) return 0;
		if(ql<=l&&r<=qr) return Tr[p].val;
		int mid=(l+r)>>1,res=0;
		if(ql<=mid) res+=querySum(ls(p),l,mid,ql,qr);
		if(mid<qr) res+=querySum(rs(p),mid+1,r,ql,qr);
		return res;
	}
	#undef ls
	#undef rs
}Tre;
#define ls(p) Tr[p].lc
#define rs(p) Tr[p].rc
int Idx;
struct St
{
	int lc,rc;
}Tr[MAXN<<3];
void modifyAdd(int &p,int l,int r,int x,int q)
{
	if(!p) p=++Idx;
	// Tre.modifyX(Tr[p].rt,qL,qR,q);
	// ++Mp[(Pir){p,q}];
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(x<=mid) modifyAdd(ls(p),l,mid,x,q);
	else modifyAdd(rs(p),mid+1,r,x,q);
}
int querySum(int p,int l,int r,int ql,int qr,int id)
{
	if((!p)||(ql>qr)) return 0;
	// if(ql<=l&&r<=qr) return Tre.querySum(Tr[p].rt,qL,qR,lq[id],rq[id]);
	if(ql<=l&&r<=qr)
	{
		int res=0;
		// for(int i=a[id].q-K;i<=a[id].q+K;++i) res+=Mp[(Pir){p,i}];
		return res;
	}
	int mid=(l+r)>>1,res=0;
	if(ql<=mid) res+=querySum(ls(p),l,mid,ql,qr,id);
	if(mid<qr) res+=querySum(rs(p),mid+1,r,ql,qr,id);
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);
	for(int i=1;i<=N;++i) read(a[i].x,a[i].r,a[i].q);
	std::sort(a+1,a+N+1);
	for(int i=1;i<=N;++i)
	{
		Nums.push_back(a[i].x);al[i]=a[i].x-a[i].r,ar[i]=a[i].x+a[i].r;
		Nums.push_back(al[i]),Nums.push_back(ar[i]);
		// checkMin(qL,a[i].q),checkMax(qR,a[i].q);
		// Iq.push_back(a[i].q),Iq.push_back(a[i].q-K),Iq.push_back(a[i].q+K);
		// lq[i]=a[i].q-K,rq[i]=a[i].q+K;
	}
	std::sort(Nums.begin(),Nums.end());
	// std::sort(Iq.begin(),Iq.end());
	Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
	// Iq.erase(std::unique(Iq.begin(),Iq.end()),Iq.end());
	for(int i=1;i<=N;++i)
	{
		a[i].x=std::lower_bound(Nums.begin(),Nums.end(),a[i].x)-Nums.begin()+1;
		al[i]=std::lower_bound(Nums.begin(),Nums.end(),al[i])-Nums.begin()+1;
		ar[i]=std::lower_bound(Nums.begin(),Nums.end(),ar[i])-Nums.begin()+1;
		// a[i].q=std::lower_bound(Iq.begin(),Iq.end(),a[i].q)-Iq.begin()+1;
		// lq[i]=std::lower_bound(Iq.begin(),Iq.end(),lq[i])-Iq.begin()+1;
		// rq[i]=std::lower_bound(Iq.begin(),Iq.end(),rq[i])-Iq.begin()+1;
	}
	rL=1,rR=Nums.size();
	// qL=1,qR=Iq.size();
	// write(rL,' ',rR,'\n',qL,' ',qR,'\n');
	// build(1,rL,rR);
	ll ans=0;
	for(int i=1;i<=N;++i)
	{
		for(int j=a[i].q-K;j<=a[i].q+K;++j)
			ans+=Tre.querySum(Rt[j],rL,rR,al[i],ar[i]);
		Tre.modifyX(Rt[a[i].q],rL,rR,a[i].x);
	}
	write(ans);
	return 0;
}
/*

*/
相关文章