首页 > 其他分享 >P2163 [SHOI2007] 园丁的烦恼

P2163 [SHOI2007] 园丁的烦恼

时间:2024-09-18 21:03:42浏览次数:10  
标签:园丁 val int lowbit pos ret P2163 SHOI2007

中学的时候年轻气盛,应该拿主席树把这道题艹过去了。正好复习离线二维数点,再做了一遍。

我们把询问差分安排到x轴上,然后y轴用树状数组统计即可。注意到此题要离散化,但是询问中的x可能不在原序列中。不过这不要紧,记得二分完减一就好。

const int N = 5e5 + 5, S = 1e7 + 5;
int n, m, t, ans[N], x[N];
pair <int, int> a[N];

struct Query {
	int p, q, x, y;
	Query(int p = 0, int q = 0, int x = 0, int y = 0) : p(p), q(q), x(x), y(y) {}
};

int c[S];
inline void update(int pos, int val) {
	for (; pos < N; pos += lowbit(pos)) c[pos] += val;
}

inline int query(int pos) {
	int ret = 0;
	for (; pos; pos -= lowbit(pos)) ret += c[pos];
	return ret;
}

vector <Query> v[N];

signed main(void) {
	read(n), read(m);
	for (int i = 1; i <= n; i++) read(a[i].first), read(a[i].second), x[i] = a[i].first;
	sort(a + 1, a + n + 1); sort(x + 1, x + n + 1); t = unique(x + 1, x + n + 1) - (x + 1);
	
	for (int i = 1; i <= m; i++) {
		int l, r, _x, _y;
		read(l), read(_x), read(r), read(_y);
		int _l = lower_bound(x + 1, x + t + 1, l) - x - 1;
		int _r = upper_bound(x + 1, x + t + 1, r) - x - 1;
		v[_l].push_back(Query(i, -1, _x, _y));
		v[_r].push_back(Query(i, 1, _x, _y));
	}
	
	for (int i = 1, j = 1; i <= t; i++) {
		while (a[j].first == x[i] && j <= n) update(a[j].second + 1, 1), j++;
		for (auto u : v[i]) ans[u.p] -= u.q * query(u.x), ans[u.p] += u.q * query(u.y + 1);
	}
	
	for (int i = 1; i <= m; i++) writeln(ans[i]);
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

标签:园丁,val,int,lowbit,pos,ret,P2163,SHOI2007
From: https://www.cnblogs.com/EternalEpic/p/18419316

相关文章

  • P2163 [SHOI2007] 园丁的烦恼 题解
    题目传送门题目大意:在一个平面直角坐标系上,给定\(n\)个点的坐标\((x,y)\),\(m\)次询问,每次询问一个矩形范围内的点的数量,此矩形用\(\{a,b,c,d\}\)来描述,其中\((a,b)\)为左下角,\((c,d)\)为右上角。思路:不难将题目转化为:给定一个长度为\(n\)的序列,序列中的每个元......
  • [SHOI2007] 园丁的烦恼
    二维数点问题我们通过扫描线可以将静态的二维问题转换为动态的一维问题维护动态的一维问题就使用数据结构维护序列点击查看代码#include<bits/stdc++.h>usingnamespacestd;structt1{ intx,y;}t[500005];structq1{ intx1,y1,x2,y2;}q[500005];structl1{......
  • [SHOI2007]书柜的尺寸 题解
    题目链接设\(f_{i,t1,t2}\)表示前\(i\)本书,第一层的宽度为\(t1\),第二层的宽度为\(t2\),所需要的最小高度。第三层宽度\(t3=\sum_{i=1}^{i}t_i-t1-t2\)。但本题还有一个重要限制:每层的高度取决于该层最高的书,如果直接按照顺序加入书本,从\(dp\)的状态来看,无法确定新书本......
  • P2163 [SHOI2007] 园丁的烦恼 题解
    题目链接:园丁的烦恼挺经典的题目,转化成二维数点去做这玩意和常规的偏序计数问题有区别:转化为求\(a\lex\leb\\&\&\c\ley\led\)的数量,这种就别想着拆来拆去了,这种权值类带偏序计数类问题,是经典的可差性问题,我们计:\(ans(x,l,r)\)表示\(t\lex,l\ley\ler\)的数......
  • [SHOI2007] 园丁的烦恼
    [SHOI2007]园丁的烦恼题目背景很久很久以前,在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者,在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里,若有所思,他问一个园丁道:“最近我在思索一个问题,如果我们把花坛摆成六个六角形,那么……”......
  • 缎蓝园丁鸟优化算法(SBO)文章复现(非均匀变异策略+非线性权重改进位置更新+互利因子改进
    缎蓝园丁鸟优化算法(SBO)文章复现(非均匀变异策略+非线性权重改进位置更新+互利因子改进位置更新)——ISBO。复现内容包括:改进算法实现、23个基准测试函数、文中相关因子分析、文中相关图分析、与SBO对比等。代码基本上每一步都有注释,非常易懂,代码质量极高,便于新手学习和理解......
  • P2057 [SHOI2007] 善意的投票
    传送门思路我们考虑将原本想同意的人连向源点,原本不同意的人连向汇点,流量皆为\(1\)。对于一对好朋友\(x,y\),我们连接\((x,y)\)和\((y,x)\)双向边,流量皆为\(1\)......
  • [luogu p2160] [SHOI2007]书柜的尺寸
    [P2160SHOI2007]书柜的尺寸-洛谷|计算机科学教育新生态(luogu.com.cn)把书按高度从大到小排序,依次考虑放置,每一层第一个被放置的书的高度就是这一层的高度。设\(f......