Problem
有\(n\)个元素，每个元素有三个属性：\(a_i\),\(b_i\),\(c_i\)
定义\(f[i]\)为满足\(a_j < a_i\) 且 \(b_j < b_i\) 且 \(c_j < c_ i\)的\(j\)的个数
\(ans[i] = \sum_{j = 1}^{j \leq n} f[j] = i\)
求所有的\(ans[i]\);
陌上花开，心忧梓桑。
Solution
\(CDQ\)分治模板题
首先以\(a\)为关键字排序，省略一维
再以\(b\)为关键字用类似于归并排序求逆序对的方法进行归并
最后用树状数组统计\(c\)这一维
简单来说就是归并排序套树状数组。
有点像点分治？
调了不知道多久，最后发现树状数组范围打错了(原地爆炸.jpg)
Code
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
inline int read(){
int res = 0, fl = 1;
char r = getchar();
for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 2e5 + 10;
vector <pii> G[Maxn];
map <pii, int> Map;
struct node{
int fst, snd, val, id;
bool operator < (const node &T) const{
if(fst == T.fst) return snd < T.snd;
return fst < T.fst;
}
}P[Maxn], tmp[Maxn];
int cnt, f[Maxn], val[Maxn], top, num, ans[Maxn], K, v[Maxn];
pii del[Maxn];
bool ok;
namespace BIT{
inline int lowbit(int x) {return x & -x;}
int tre[Maxn];
inline void Modify(int pos, int v){
for (; pos <= K; pos += lowbit(pos)) tre[pos] += v;
}
inline int Query(int pos){
int sum = 0;
for (; pos >= 1; pos -= lowbit(pos)) {
sum += tre[pos];
}
return sum;
}
}
void CDQ_div(int L, int R){
if(L == R) return;
int mid = L + R >> 1;
num = L - 1;
CDQ_div(L, mid), CDQ_div(mid + 1, R);
int l = L, r = mid + 1;
while(l <= mid && r <= R){
if(P[l].fst <= P[r].fst){
BIT::Modify(P[l].snd, P[l].val);
del[++top] = mp(P[l].snd, P[l].val);
l++;
}
else {
f[P[r].id] += BIT::Query(P[r].snd);
r++;
}
}
while(r <= R) {
f[P[r].id] += BIT::Query(P[r].snd);
r++;
}
sort(P + L, P + R + 1);
while(top){
BIT::Modify(del[top].fst, -del[top].snd);
top--;
}
}
int id[Maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
int n = read(), k = read();
K = k;
for (int i = 1; i <= n; ++i){
int a = read(), b = read(), c = read();
G[a].push_back(mp(b,c));
}
for (int i = 1; i <= k; ++i) {
sort(G[i].begin(), G[i].end());
for (pii j : G[i]) Map[j]++;
int sum = unique(G[i].begin(), G[i].end()) - G[i].begin();
for (int j = 0; j < sum ; ++j) {
pii nxt = G[i][j];
P[++cnt].fst = nxt.fst, P[cnt].snd = nxt.snd;
P[cnt].val = Map[nxt], P[cnt].id = cnt;
v[cnt] = P[cnt].val;
}
Map.clear();
}
CDQ_div(1, cnt);
for (int i = 1; i <= cnt; ++i) ans[f[P[i].id] + P[i].val - 1] += P[i].val;
for (int i = 0; i < n; ++i) printf("%d\n", ans[i]);
return 0;
}
转载于:https://www.cnblogs.com/LZYcaiji/p/10601349.html
相关资源：JAVA上百实例源码以及开源项目
