@[Saint_ying_xtf](/user/1073995) 菜就多练
by cccyyymmm @ 2024-03-23 16:31:43
@[cccyyymmm](/user/1017322) 我调题怎么了?
举报了 wyy
by Saint_ying_xtf @ 2024-03-23 16:32:20
@[Saint_ying_xtf](/user/1073995)
这并不是对劲的cdq分治……
如果想看更不对劲的,点这里-> :-)
cdq分治每次计算前一半对后一半的影响。具体地, 假设三维分别是x,y,z,先按x排序。分治时每次将前半边、后半边分别按y排序。虽然现在x的顺序被打乱了,但是前半边还是都小于后半边的,所以要是只计算前半边对后半边的偏序关系,是不会受到x的影响的。维护后一半的指针i,前一半的指针j,每次将i后移一位时,若y[j]<=y[i]则不断后移j,并不断将z[j]加入树状数组。然后再查询树状数组中有多少数小于等于z[i]。 最后要清空树状数组。
它有那么一些些眼熟,解一维偏序时就是归什么排序。
```cpp
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
#define maxk 200010
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(isdigit(ch)==0 && ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(int x)
{
int f=0;char ch[20];
if(!x){puts("0");return;}
if(x<0){putchar('-');x=-x;}
while(x)ch[++f]=x%10+'0',x/=10;
while(f)putchar(ch[f--]);
putchar('\n');
}
typedef struct node
{
int x,y,z,ans,w;
}stnd;
stnd a[maxn],b[maxn];
int n,cnt[maxk];
int k,n_;
bool cmpx(stnd u,stnd v)
{
if(u.x==v.x)
{
if(u.y==v.y)
return u.z<v.z;
return u.y<v.y;
}
return u.x<v.x;
}
bool cmpy(stnd u,stnd v)
{
if(u.y==v.y)
return u.z<v.z;
return u.y<v.y;
}
struct treearray
{
int tre[maxk],kk;
int lwbt(int x){return x&(-x);}
int ask(int i){int ans=0; for(;i;i-=lwbt(i))ans+=tre[i];return ans;}
void add(int i,int k){for(;i<=kk;i+=lwbt(i))tre[i]+=k;}
}t;
void cdq(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
sort(a+l,a+mid+1,cmpy);
sort(a+mid+1,a+r+1,cmpy);
int i=mid+1,j=l;
for(;i<=r;i++)
{
while(a[j].y<=a[i].y && j<=mid)
t.add(a[j].z,a[j].w),j++;
a[i].ans+=t.ask(a[i].z);
}
for(i=l;i<j;i++)
t.add(a[i].z,-a[i].w);
}
int main()
{
n_=read(),k=read();t.kk=k;
for(int i=1;i<=n_;i++)
b[i].x=read(),b[i].y=read(),b[i].z=read();
sort(b+1,b+n_+1,cmpx);
int c=0;
for(int i=1;i<=n_;i++)
{
c++;
if(b[i].x!=b[i+1].x || b[i].y!=b[i+1].y || b[i].z!=b[i+1].z )
a[++n]=b[i],a[n].w=c,c=0;
}
cdq(1,n);
for(int i=1;i<=n;i++)
cnt[a[i].ans+a[i].w-1]+=a[i].w;
for(int i=0;i<n_;i++)
write(cnt[i]);
return 0;
}
```
by cccyyymmm @ 2024-03-23 16:33:13
@[cccyyymmm](/user/1017322) ?
你在说啥?
by Saint_ying_xtf @ 2024-03-23 16:34:45
@[cccyyymmm](/user/1017322) 帅哥你那里copy的文字?而且你好像这题没有AC?
我只是想找人调一下题
你发啥?为啥不对劲,你倒是说啊
by Saint_ying_xtf @ 2024-03-23 16:38:48
@[cccyyymmm](/user/1017322) 神金
by 2020luke @ 2024-03-23 16:40:49
哦,刚才有人盗了我号。
不是我本人发的 @[Saint_ying_xtf](/user/1073995)
by cccyyymmm @ 2024-03-23 16:41:10
@[cccyyymmm](/user/1017322) az
by Saint_ying_xtf @ 2024-03-23 16:41:54
@[cccyyymmm](/user/1017322) 我就说你不可能100秒码了500中文+一份代码,肯定是哪里copy,说的不明不白...
by Saint_ying_xtf @ 2024-03-23 16:42:44
@[Saint_ying_xtf](/user/1073995) ac乐,此贴结
by Saint_ying_xtf @ 2024-03-23 17:14:34