HDU 5126 stars cdq分治+树状数组

题目链接:点击打开链接

题意:

T个case

n个操作

1、 (x,y,z) 在三维平面的点上增加1

2、询问区间范围内的权值和。

思路:

cdq分治套cdq分治,然后套树状数组即可。。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <vector>
#include <string>
#include <time.h>
#include <math.h>
#include <iomanip>
#include <queue>
#include <stack>
#include <set>
#include <map>
const int inf = 1e8;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T>
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != '-' && (c<'0' || c>'9')) c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
	ret *= sgn;
	return 1;
}
template <class T>
inline void pt(T x) {
	if (x <0) { putchar('-'); x = -x; }
	if (x>9) pt(x / 10);
	putchar(x % 10 + '0');
}
using namespace std;
const int N = 50010 << 3;
int maxn, c[N];
int lowbit(int x){ return x&-x; }
void add(int x,int val){
	while (x <= maxn)c[x] += val, x += lowbit(x);
}
int sum(int x){
	int ans = 0;
	while (x)ans += c[x], x -= lowbit(x);
	return ans;
}
typedef long long ll;
typedef pair<int, int> pii;
class Node{
public:
	int op, x, y, z, id, add, ans;
	Node(){}
	Node(int _op, int _x, int _y, int _z, int _id, int _add) : op(_op), x(_x), y(_y), z(_z), id(_id), add(_add), ans(0){}
};
int ans[N];
bool cmp(const Node &e1, const Node & e2) {
	if (e1.x == e2.x)return e1.id < e2.id;
	return e1.x < e2.x;
}
bool cmp2(const Node &e1, const Node & e2) {
	if (e1.y == e2.y)return e1.id < e2.id;
	return e1.y < e2.y;
}
Node q[N], t[N], v[N];
int n, top, tt;
void cal(int l, int r){ //x有序
	if (l == r)return;
	int mid = (l + r) >> 1;
	tt = 1;
	for (int i = l; i <= mid; i++)if (t[i].op == 1)v[++tt] = t[i];
	for (int i = mid + 1; i <= r; i++)if(t[i].op == 2)v[++tt] = t[i];
	sort(v + 1, v + tt + 1, cmp2);
	for (int i = 1; i <= tt; i++)
	if (v[i].op == 1)
		add(v[i].z, 1);
	else
		ans[v[i].id] += sum(v[i].z) * v[i].add;
	for (int i = 1; i <= tt; i++)if (v[i].op == 1)add(v[i].z, -1);
	cal(l, mid); cal(mid + 1, r);
}
void solve(int l, int r){
	if (l == r)return;
	int mid = (l + r) >> 1;
	top = 1;
	for (int i = l; i <= mid; i++)if (q[i].op == 1)t[++top] = q[i];
	for (int i = mid + 1; i <= r; i++)if (q[i].op == 2)	t[++top] = q[i];
	sort(t + 1, t + top + 1, cmp);
	cal(1, top);
	solve(l, mid); solve(mid + 1, r);
}
vector<int>G;
int main(){
	int T; rd(T);
	while (T-- > 0){
		rd(n);
		G.clear();
		int siz = 0;
		for (int i = 1, op, x1, x2, y1, y2, z1, z2; i <= n; i++)
		{
			rd(op);
			if (op == 1)
			{
				q[++siz].op = 1;
				ans[i] = -1;
				rd(q[siz].x); rd(q[siz].y); rd(q[siz].z); G.push_back(q[siz].z);
			}
			else {
				rd(x1); rd(y1); rd(z1); rd(x2); rd(y2); rd(z2);
				G.push_back(z2); G.push_back(z1); G.push_back(z1 - 1);
				ans[i] = 0;
				q[++siz] = Node(2, x2, y2, z2, i, 1);
				q[++siz] = Node(2, x1 - 1, y2, z2, i, -1);
				q[++siz] = Node(2, x2, y1 - 1, z2, i, -1);
				q[++siz] = Node(2, x1 - 1, y1 - 1, z2, i, 1);

				q[++siz] = Node(2, x2, y2, z1 - 1, i, -1);
				q[++siz] = Node(2, x1 - 1, y2, z1 - 1, i, 1);
				q[++siz] = Node(2, x2, y1 - 1, z1 - 1, i, 1);
				q[++siz] = Node(2, x1 - 1, y1 - 1, z1 - 1, i, -1);
			}
		}
		sort(G.begin(), G.end());
		G.erase(unique(G.begin(), G.end()), G.end());
		maxn = G.size();
		for (int i = 1; i <= siz; i++)q[i].z = lower_bound(G.begin(), G.end(), q[i].z) - G.begin() + 1;
		solve(1, siz);
		for (int i = 1; i <= n; i++)if (ans[i] >= 0)pt(ans[i]), putchar('\n');
	}
	return 0;
}
时间: 05-09

HDU 5126 stars cdq分治+树状数组的相关文章

HDU 5618:Jam&#39;s problem again(CDQ分治+树状数组处理三维偏序)

http://acm.hdu.edu.cn/showproblem.php?pid=5618 题意:-- 思路:和NEUOJ那题一样的.重新写了遍理解了一下,算作处理三维偏序的模板了. 1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 #d

BZOJ 2683 简单题 cdq分治+树状数组

题意:链接 **方法:**cdq分治+树状数组 解析: 首先对于这道题,看了范围之后,二维的数据结构是显然不能过的,于是我们可能会考虑把一维排序之后另一位上数据结构什么的,然而cdq分治却能够很好的体现它的作用. 首先,对于每一个询问求和,显然是x在它左边的并且出现时间在它之前的所有的change对他可能会有影响. 我们按照x第一关键字,y第二关键字,操作第三关键字来排序所有的询问,然后在cdq的时候,每次递归处理左半区间,按照x动态的将y这一列的值加到树状数组里,来更新右半边的所有询问,注意这

XJOI NOIP2015模拟赛Day1 T2 ctps bitset优化 或 排序+cdq分治+树状数组+平衡树

题意: 4维空间中有1个点集A,|A|=n,用(a,b,c,d)表示每个点. 共有m个询问,每次询问输入一个点(a,b,c,d),求最大的S,其中S={p|p∈A且ap<=a,bp<=b,cp<=c,dp<=d},输出|S| 输入格式: 第一行n 接下来n行有n个4维点对 第n+2行有一个数m 再接下来m行每行有一个四维点对,表示每个询问 输出格式: 对于每个询问输出一个数 **方法:**bitset优化 或 排序+cdq分治+树状数组+平衡树 解析: 神题,考场不会,暴力骗40,

【BZOJ4553】[Tjoi2016&amp;Heoi2016]序列 cdq分治+树状数组

[BZOJ4553][Tjoi2016&Heoi2016]序列 Description 佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他.玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化.现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可.注意:每种变化最多只有一个值发生变化.在样例输入1中,所有的变化是: 1 2 3 2 2 3 1 3 3 1

BZOJ2683: 简单题(CDQ分治 + 树状数组)

BZOJ2683: 简单题(CDQ分治 + 树状数组) 题意: 你有一个\(N*N\)的棋盘,每个格子内有一个整数,初始时的时候全部为\(0\),现在需要维护两种操作: 命令 参数限制 内容 \(1\ x\ y\ A\) \(1\le x,y \le N\),A是正整数 将格子\(x,y\)里的数字加上\(A\) \(2\ x1\ y1\ x2\ y2\) \(1\le x1\le x2\le N,1\le y1\le y2\le N\) 输出\(x1\ y1\ x2\ y2\)这个矩形内的数字

[cdq分治][树状数组] Bzoj P3262 陌上花开

Description 有n朵花,每朵花有三个属性:花形(s).颜色(c).气味(m),用三个整数表示. 现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量. 定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb. 显然,两朵花可能有同样的属性.需要统计出评出每个等级的花的数量. Input 第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值. 以下N

BZOJ1176---[Balkan2007]Mokia (CDQ分治 + 树状数组)

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1176 CDQ第一题,warush了好久.. CDQ分治推荐论文: 1 <从<Cash>谈一类分治算法的应用> 陈丹琦 2 <浅谈数据结构题的几个非经典解法>  许昊然 关于CDQ分治,两种要求:①操作不相互影响  ②可以离线处理 题目描述是有问题的,,初始时 全部为0,不是s 题意:二维平面内,两种操作,1 x y v ,位于(x,y)的值加上v...2 x1,

bzoj2716 [ Violet 3 ] --cdq分治+树状数组

树状数组打错调了一个小时... 对于点(x,y),其它点只会在他的左下.右下.左上.右上四个方向上.我们只需求在左下方向上就可以了,因为其他方向可以通过改变相对位置求得. 考虑cdq分治.先按x坐标排序,然后将区间[l,r]分为[l,mid],[mid+1,r],因为只求左下方向上的点,所以可以去掉绝对值:dis=x+y-(x'+y') 只需求x'+y'最大的点就可以了.求(X,Y)时将[l,mid]中x值小于X的点的x+y值在树状数组中更新,然后查询y小于Y的最大的x+y,更新答案. 代码:

hdu_5324_Boring Class(cdq分治+树状数组)

题目链接:hdu_5324_Boring Class 题意: 给出n个二维点对,求LIS长度和编号字典序最小的LIS(x非增,y非减) 题解: dp[i]=max(dp[j]) (i>j,l[i]>=l[j],r[i]<=r[i]) 一看就是三维偏序问题. 如果树套树写的好,空间开的大的话,一样可以过,不过这里还是用cdq分治套树状数组好写一点. 用lowbit来维护dp[j]的最大值,然后因为要字典序最小,所以从后往前dp. 1 #include<bits/stdc++.h>