Rockdu's Blog

题目背景

这是一道模版题

可以使用bitset，CDQ分治，K-DTree等方式解决。

题目描述

有  个元素，第  个元素有 、、 三个属性，设  表示满足  且  且  的  的数量。

对于 ，求  的数量

输入输出格式

输入格式：

第一行两个整数 、，分别表示元素数量和最大属性值。

之后  行，每行三个整数 、、，分别表示三个属性值。

输出格式：

输出  行，第  行表示  的  的数量。

输入输出样例

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

3
1
3
0
1
0
1
0
0
1

说明

            洛谷评测机刷了一上午屏终于搞定了！

            这道题因为会有重复点存在，所以cdq分治离线时一定要把重复的点缩为一个。

            然后树状数组不要清零memset……

            另外，别对拍完不删freopen

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) x&-x
using namespace std;
const int maxn=1e5+100;
const int maxk=2e5+100;
int n,k;
int ans[maxn];
int id[maxn];
int sum[maxn];
struct point{
	int x,y,z,n,id,sum;
}rp[maxn],p[maxn];
 
bool cmp_xyz(const point &a,const point &b){
	return a.x==b.x?(a.y==b.y?a.z<b.z:a.y<b.y):a.x<b.x;
}
 
bool cmp_yzx(const point &a,const point &b){
	return a.y==b.y?(a.z==b.z?a.x<b.x:a.z<b.z):a.y<b.y;
}
 
namespace BIT{
	int tree[maxk];
	void add(int x,int w){while(x<=k)	tree[x]+=w,x+=lowbit(x);}
	int query(int x){int ret=0;while(x) ret+=tree[x],x-=lowbit(x);return ret;}
}
 
void cdq(int l,int r){
	if(l==r)	return ;
	int mid=(l+r)/2;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(p+l,p+r+1,cmp_yzx);
	for(int i=l;i<=r;i++){
		if(p[i].id<=mid)
			BIT::add(p[i].z,p[i].sum);
		else ans[p[i].n] += BIT::query(p[i].z);
	}
	for(int i=l;i<=r;i++)
		if(p[i].id<=mid)
			BIT::add(p[i].z,-p[i].sum);
}
 
int main(){
	freopen("s.in", "r", stdin);
	freopen("s.out", "w", stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&rp[i].x,&rp[i].y,&rp[i].z);
		rp[i].n=i;
	}
	sort(rp+1,rp+n+1,cmp_xyz);
	int cnt=1;
	p[1]=rp[1];p[1].id=1;p[1].sum=1;
	for(int i=2;i<=n;i++){
		if(rp[i].x==rp[i-1].x && rp[i].y==rp[i-1].y && rp[i].z==rp[i-1].z)
			p[cnt].sum++;
		else{
			p[++cnt]=rp[i];
			p[cnt].id=cnt;
			p[cnt].sum=1;
		}
	}
	cdq(1,cnt);
	for(int i=1;i<=cnt;i++)
		id[p[i].n]=i;
	for(int i=1;i<=n;i++)
		sum[ans[i]+p[id[i]].sum-1]+=p[id[i]].sum;
	for(int i=0;i<=n-1;i++)
		printf("%d\n",sum[i]);
	return 0;
} 

++---++---+2018/1/24+---++---++

更新了一版CDQ，发现以前常数大代码丑。这次在洛谷372ms：

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct point {
	int x, y, z, pos, id, cnt;
}rp[maxn], p[maxn], mg[maxn];
int n, k, a, b, c, ans[maxn], sum[maxn], cnt;
int mcnt, pl, pr;
inline char gc(){
    static char buf[5000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int & x) {
    x = 0;static char c = gc();
    while(!isdigit(c)) c = gc();
    while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}
void write(int x) {
    if(x / 10) write(x / 10);
    putchar(x % 10 + '0'); 
} 
bool cmp_xyz(const point &a, const point &b) {
	return a.x == b.x ? (a.y == b.y ? (a.z < b.z) : a.y < b.y) : a.x < b.x;
}
inline bool cmp_yzx(const point &a, const point &b) {
	return a.y == b.y ? (a.z == b.z ? (a.x < b.x) : a.z < b.z) : a.y < b.y;
}
namespace BIT {
	int tree[maxn << 1];
	#define lowbit(x) ((x) & (-(x)))
	void add(int x, int p) {while(x <= k) tree[x] += p, x += lowbit(x);}
	int query(int x) {
		int ans = 0;
		while(x) ans += tree[x], x -= lowbit(x);
		return ans;
	}
}
void cdq(int l, int r) {
	if(l == r) return;
	int mid = l + r >> 1;
	cdq(l, mid), cdq(mid + 1, r);
	mcnt = 0, pl = l, pr = mid + 1;
	while(pl <= mid && pr <= r)
		if(cmp_yzx(p[pl], p[pr])) mg[++mcnt] = p[pl++];
		else mg[++mcnt] = p[pr++];
	while(pl <= mid) mg[++mcnt] = p[pl++];
	while(pr <= r) mg[++mcnt] = p[pr++];
	for(register int i = 1; i <= mcnt; ++i) p[l + i - 1] = mg[i];
	for(register int i = l; i <= r; ++i) {
		if(p[i].id <= mid) BIT::add(p[i].z, p[i].cnt);
		else ans[p[i].pos] += BIT::query(p[i].z);
	}
	for(register int i = l; i <= r; ++i)
		if(p[i].id <= mid) BIT::add(p[i].z, -p[i].cnt);
}
int main() {
	read(n), read(k);
	for(register int i = 1; i <= n; ++i) {
		read(a), read(b), read(c);
		rp[i] = (point) {a, b, c, i, 0, 1};
	}
	sort(rp + 1, rp + n + 1, cmp_xyz);
	for(register int i = 1; i <= n; ++i) {
		if(rp[i].x == rp[i - 1].x && rp[i].y == rp[i - 1].y && rp[i].z == rp[i - 1].z) ++p[cnt].cnt;
		else p[++cnt] = rp[i], p[cnt].id = cnt;
	}
	cdq(1, cnt);
	for(register int i = 1; i <= cnt; ++i)
		sum[ans[p[i].pos] + p[i].cnt - 1] += p[i].cnt;
	for(register int i = 0; i < n; ++i)
		write(sum[i]), putchar('\n');
	return 0;
}