# 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; }
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)
else
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;
}```

## 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

## 【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